****************************************
Marking Guide for Quiz #2
CSC 364, Summer, Day Section, 1999
****************************************

1a) 2 Marks for giving the correct matrix
    -1 Mark for each mistake

b) 2 Marks for giving the determinant
   1 Mark for making a small calculational mistake in figuring out the
	  determinant
c) 1 mark for each correct matching
   -1 mark for each incorrect mathing or stating an improper number of 
    mathchings.

d) 2 Marks for giving a correct matrix with a determinant of zero.
   -1 for making caculational mistakes (ie. You though the determinant was
   zero, but you made a mistake in the calculation of the determinant, etc..)

e) 2 Marks for stating that the probability was  1/2, and for giving a 
   _valid_ argument as to why it was the case. Invalid arguments received a 0.
   
   1 Mark for a small mistake in the argument given above.

$$$$$$$$$$$$$$$$$$$$

2a) 2 Marks for attempting to give a function f which transforms an input I
    for partition into an input I' for SKD, such that I is in Partition iff
    I' is in SKD.

    1 Mark for leaving d,w_1,...,w_d unchanged.

    3 Marks for setting b=c= (1/2)(\sum_{1=1}^d w_i

b) 1 Mark for stating the you need to know that SKD is in NP, or that it is 
   known that SKD is in NP based on lectures or by giving a guess and check
   algorithm.

   3 Marks for Arguing that SKD is NP-Hard based on the following facts
	1) 3-Sat is NPC   (1 marks)
	2) 3-Sat <_p SKD by transitivity and the two facts mentioned in the
	   question.  (2 marks)


$$$$$$$$$$$$$$$$$$$$

3a)  -1 Mark for each letter on the tape which differed from the correct 
      solution.

b)   2 marks for each of the entries. Part marks were not given for each 
     of the entries.