Marking report for test 3 (day section)
---------------------------------------

Note: Some discretion used to assign marks between the categories
listed below.

1.	3 for saying SKS can be solved in polytime
	2 for explaining it properly (2 reductions, one <=p, one ->p)
	-1 if the explanation was not exactly right (e.g. saying 
	   SKS is in P)

COMMON PROBLEMS: Most common problem involved assumption that SKS was in
NP (which consists only of decision problems) and therefore <=p reduction
followed directly.

2.	1 for making the correct assertion
	0 for making incorrect assertion
	if correct:
	a)	4 for a correct reduction
		2 for a correct reduction with small errors
		0 for a bad reduction
		-2 for reducing from a problem not on the back

COMMON PROBLEMS: Reductions of HC to st-HP which involved adding vertices
s and t to graph and connecting them to all vertices, or removing
arbitrary edge in the graph (neither are iff). Also, reductions which
involved adding a vertex which is connected only to s and t, even though
s and t are not specified in the original instance of HC (these reductions
seem to be going in the wrong direction).

	b)	4 for a good algorithm
		2 for an almost good algorithm
		-1 for minor calculation errors
		0 for a bad algorithm

COMMON PROBLEMS: Not realizing that the graph could be made up of several
disjoint cycles; also, using a greedy-ish algorithm that is not guaranteed
to find a large enough IS even if one exists. More students then I would
have expected in fact said this problem was NP-Complete.

3.	a)	3 for giving the algorithm
		2 for justifying it (explaining why it halts)
		-1 if explanation was bungled

COMMON PROBLEMS: Overall OK.

	b)	5 for the correct algorithm
		-2 if explanation was bungled
		1 for some valid hand-waving explanation with no algorithm

COMMON PROBLEMS: In this and (c) some people seemed to be confused between
undecidable and not-semi-decidable (undecidability and semi-decidability
are not incompatible).

	c)	5 for a correct reduction
		2 if the reduction only worked in one direction

COMMON PROBLEMS: Some reductions of A_{TM} to L_U did not take into 
account that if M does not accept some string w it may well accept some
other string w' anyways. Also, some people seemed to be operating on the
idea that the L_U is the _intersection_ of L(M1) and L(M2), even though
the definition is restated in ordinary language for those who do not yet
know their set notation.