Question 1: 20 Points total
------------

Common Error 1.A1: Do not say that n choose 10 is approximately O(n^10) and is
                   therefore polytime in n. -1

Common Error 1.B2: No proof was given that the language in question is in NP. -2

Common Error 1.B3: No argument given that reduction is polytime. -1 

There are mistakenly two different 1.B4:

Common Error 1.B4: Gloss over the in NP argument saying just that "we
                   can easily see that". -1

AND

Common Error 1.B4: Case in which k < |v|/2 is dealt with even though it is not
                   needed. In this case you can just do nothing. Shows a lack
                   of understanding that if a graph has a vertex cover of size
                   k, then it has one of a larger size. -1


Question 2: 10 Points total
------------

Common Error 2.1: No proof that the language is in NP. -2

Common Error 2.2: No iff proof given to show that the reduction works. Up to -4

Common Error 2.3: No check to see if the total is even. -1

Common Error 2.4: Backwards. Trying to reduce the language in the question to 
                  a known NP Complete problem. Up to -9

Common Error 2.5: When reducing from Subset Sum. Subset Sum only requires a 
                  subset of the values to sum up to the given value, call it T.
                  Scheduling requires ALL of the jobs to be schedule. If this
                  was no dealt with the student was penalized -7.

Question 3: 10 Points total
------------

Common Error 3.1: No iff proof given to show that the reduction works. -2



Question 4: 10 Points total
------------

Common Error 4.1: No iff proof given to show that the reduction works. -2

Common Error 4.2: Did not say for all sizes i: 1 to infinity. -3

Common Error 4.3 Did not dove tail. (Like 4.2 and 4.4 together) -6

Common Error 4.4: Did not run on all inputs of size less than or equal to i
                  during each iteration. -3

Common Error 4.5: When reducing from ATM, if <M, w> is in ATM then we only 
                  know that M halts on w. Similarly is <M, w> is not in ATM
                  we only know that M does not halt on w. On any other string
                  we do not know how M will perform. So cannot use any x. -6