Comments on Test 2
==================
(by Mohammad Mahdian)


Problem 1:
	(a): correct answer worths 2 points.
	(b): stating that P(error)=0  worths 1 point
	     proving that P(error)=0  worths 2 points
	(c): stating that P(error)<=1/2 worths 0.5 point
	     using the Shwartz-Zipple theorem to prove the above: 2.5
	     points

	     Some students have written the (correct) solution of part
	     (b) in part (c), and/or the solution of part (c) in part (b).
	     I've deducted 0.5 point for each such mistake.
	(d): executing the algorithm k times: 1.5 points
	     specifying the rule for getting the answer, from the k
	     answers that we get from k executions of the algorithm
	     (i.e. YES if all k executions return with YES, and NO if at
	     least one of the returns NO): 0.5 point

	     an alternative solution for this part is to choose r
	     uniformly at random from {1,2,...,2^kd}. This solution is
	     correct (although not good) and worths 2 points

Problem 2: 
	(a): Trying (in the right direction) to find a "guess and check"
	     algorithm or a certificate worths 2 points
	     complete solution: 4 points
	(b): writing the definition of the reduction from 4-SAT to 3-SAT:
	     2 points
	     proving the reduction in the wrong direction (i.e. from 3-SAT
	     to 4-SAT): 1 point (for correct reductions)
	     A solution which has clauses of less than 4 literals loses 1
	     point (note that according to the definition of 4-SAT, every
	     clause of 4-SAT must have EXACTLY 4 literals)
	     
	     comment about the solution: For reducing 4-SAT to 3-SAT, it
	     is sufficient to replace each clause of the form (L1 or L2 or
	     L3 or L4) with two clauses (L1 or L2 or P) and (not P or L3
	     or L4). It's easy to verify that the conjunction of these two
	     clauses is logically equivalent to the original clause.

Problem 3: 
	(a): 4 points for the correct answer. For each wrong bit in the
	     answer, I've deduced 1 point (i.e. an answer with more than
	     3 wrong bits worths 0).
	(b): filling the first and the second empty line: 1.5 points each
	     filling the third empty line with (q_4, print b, left) 3
	     points (each of the q_4, print b, and left worths 1 point)