Marking scheme for Test 4

Question 1:  20' 


(a) 5'

(b) 5'      2' for answer, 3' for explanation

(c) 5'      2' for answer, 3' for explanation

(d) 5'      2' for answer, 3' for explanation


Question 2:  20'

(a)  10'

  P    5'      2' for answer, 3' for explanation
  
 NP    5'      2' for answer, 3' for explanation

(b)  10'

  P    5'      2' for answer, 3' for explanation

 NP    5'      2' for answer, 3' for explanation


< some polular mistakes >

* for 1.d, 1' was deducted if the explanation is just " P is a subset of
NP" instead of " L(M) is in P and P is a subset of NP"

* for 2.a in Wednesday test, depth-first-search will not work here since
it doesn't guarantee to find the longest path, the length of which was 
used to compare with 5 in some of you's solution. In fact, depth-first
-search is P and Longest Path is NP-Complete.

* for 2.b, 3-Composite(Tuesday) and HC(Wednesday) are NP, and no one knows
whether they're in P or not since no polytime algorithm has been found.
For solutions such as "HC is not in P, since there's no polytime algorithm
available", about 1' was deducted.