Some comments on Assignment 2
=============================

General:

I was fairly strict about the marking.  If an answer showed no sign of
a correct idea, and looked like someone was just trying to bamboozle
me, I had no compunctions about awarding it a mark of zero.  The
correct idea was worth most of the marks, and minor mistakes resulted
in minor deductions.

Question 1:
a)
1 mark for Pr[DR=0]=0 AND a good explanation,
1 mark for a GOOD explanation (i.e. some algebra with the matrix elements),
1 mark for a correct example,
1 mark for a GOOD explanation of the 1/3 probability (i.e. why do
	EXACTLY 1/3 of the values of R work, no more, no less).
b)
4 marks if you derive something like r_i=foo and then argue the 1/|S|
	from that.  No marks if I didn't see where the 1/|S| came from.
	MANY students just pulled it out of thin air, which is where
	their marks went to.
c)
2 marks if I could see that you were doing Freivald with C=I.  Very few
	otherwise.

Question 2:
A Half mark off if you used 2^k-1.  The question said "decimal places"
	instead of "significant digits" so I didn't deduct anything if
	your answer came out to 0.00 (but what good is that answer?),
No marks if your formula was wrong.  (Maybe a few if it was only a
	LITTLE bit wrong.)

Question 3:
No marks for a defective algorithm.  Full marks for any working one
	AND a GOOD explanation of why it works, including why there are
	no extra edges left over and why no edges are missing.  A half
	mark off if this explanation was absent.

Question 4:
1 mark for a formulation of TSPD which had something to do with TSP,
	was a DECISION PROBLEM, AND that I could see was NP-complete.
	Some answers were in P and were not strong enough to reduce
	TSP to them (unless you are REALLY smart!),
1 mark for the question corresponding to your problem,
3 marks for the reduction: 1 for the binary search, 2 for the "remove
	edges 1 at a time" part (assuming your TSPD and reduction
	were as in the solutions),
A half mark off if you didn't properly explain the correctness of the
	reduction.

Questions 5&6: not marked.

Question 7:
0 if you asserted that NSP was not in NP,
5 marks for any valid explanation why NSP is in NP, but the word "Kruskal"
	by itself would probably have been worth 5 marks.

Question 8:
a)
Full marks for the guess&check answer.  I didn't deduct any marks if
	you neglected to mention that the S had to be nonempty, since
	almost everybody made this mistake.
b)
Full marks for any reduction which I thought was correct.  (There were
	at most 2 correct ones which weren't like the one in the
	solutions).  No marks if the reduction was in the wrong direction,
	if you gave an algorithm which called a ZERO SUM "black box"
	multiple times, if you didn't EXPLICITLY describe the function f
	(just saying "choose f such that I in PARTITION iff f(I) in
	ZERO SUM" did NOT cut it), if f was not poly-time, etc.,
A mark off if you didn't deal with the case where the total weight was odd.