Here are my comments on ass 2

1 	a) 1 for the correct probability and 1 for explanation.
	1 for correct example and 1 explanation

	b) 3 for general explanation. 1 for dij unequal to 0.

	c) 1 for noting C = I. 1 for properly using Freivald's technique

2 	1 for stating Scwartz-Zippel Thm. 1 for d = n, and 2 for 
	|S| = 2^k. 1 for correct decimal value.

3 	2 for considering the case when G has no perfect matching.
	3 for proper algorithm. I had trouble understanding some
	notations. I took some marks off when the notations got out of
	hand. 

4	1 for proper defn of TSPD. 2 for showing that TSPD is in NP.
	1 for showing proper algorithm and 1 for using binary search.

7 	3 for using Kruskals. 2 for showing that the answer depends on
	the MIN tree of the graph G. Note, usually the Decision
	problems ask for existence of something, ie. "Is there a
	..?" In this case we need to answer the question, "Is every ..?"
	So, to show that it is in NP directly you must guess the whole
	graph G and check that EVERY tree has cost > B.   

8	a) 1 for guessing and 1 for checking
	b) 2 for proper transformation. 1 for considering the case when
	the sum of weights is odd.