Marking report for CSC364 Problem Set 3 Summer 2001

Alan Skelley

Total: 50 marks, 10 per question.

1:
	a)	/7
		5 for the algorithm, 2 for the runtime.
		Very incorrect algorithms generally got around 2 total
		Algorithms with small errors got around 5 total
		Not using the FACT got 0.
		Note: Many people incorrectly discarded used clauses or did
		      not do enough passes over the clauses.
		      Many estimated running time wrong.

	b)	/3
		0-3 depending on how precisely students talked about the
		    exponential number of clauses.

2:
	a)	/5
		Almost everyone got 5 except for big algorithm errors

	b)	/5
		5 for a correct reduction
		4 for an almost correct reduction with the right idea
		2 for a slightly correct reduction
		Note:  Need edges amongst new edges AND to original graph.

3:	2 per part.
	0 for incorrect assertion.
	2 for correct alg/reduction
	1 for almost correct alg/reduction
	0 for bad alg/reduction

	a) Note:  Can't just assert a variable's value, need clauses
	   to force it.
	b) Note:  Can't reduce TSP directly since binary lengths
	   blow up to exponential size
	e) Note:  Many people got the reduction backwards.  Given
	   graph, construct diplomats.

4.	3 for the finite case, 7 for the infinite one.
	Question VERY poorly done.  Please read solution before
		 complaining.  You can't just assume a size-order
		 enumerator exists!

5.	a)	 /5
	b)	 /5
	Note:  Also poorly done.  Please read solutions.