Test 2 notes from the marker:

Question 1:
(a) Poorly done.
-1 for choosing "... languages that are ..." or "... problems that can
be..."
1/2 for choosing only "... nondeterministic..."
1 1/2 for choosing "... nondeterministic ..." and the correct one.

(b) well-done.

(c) Most people forgot that for A in NPc, it must also be in NP. Some
reason that since SAT<=p A and SAT in NP, A is in NP, which is wrong.

(d) Some people do not provide a clear explanation.

Question 2: In general, this question is very poorly done.

(a) Many people reason that TAUT is a special case of SAT and since
SAT in NP, TAUT is in NP. Some misunderstand the question, thinking that
they are given a truth assignment and have to check if F is true under that
assignment.

(b) Many choose coNP reasoning that this language is in ~CLIQUE and do
not realize that k is a constant independent of G (hence the language is
in P). For this choice, students get at most 2 marks.
For choice of NP, at most  1 1/2 marks.

Questions 3: Few got this correctly.
Students seem to know  the steps for this type of problem. However, many
have difficulty with the reduction D <=p TSP. For a correct overall
format of an incorrect reduction, get at most 4 marks (out of 10 - see below)

Correct proof TSP in NP: 4 marks
Correct reduction D <=p TSP (D is NP-hard) and justification: 10 marks.