*************************
Problem Set #3          *
*************************

******************************************************************************
Question #1) All problems were worth 5 marks (including the s-t HP reduction
done in tutorial)
******************************************************************************


**************************************************
Case 1) If the problem was NP-Complete were marked as follows.
**************************************************

All problems received 1 mark for showing that the problem was in NP (normally
through a guess and check algorithm, but other arguments were accepted).

All problems received 4 marks for showing that the problem was NP-Hard via a 
reduction from one the problems mentioned on the list.

Reductions which were completely wrong received 0 marks. Reductions which were
technically incorrect in a few locations had appropriate marks removed.

For saying an NPC problem was in P received 0 marks (This is to say, 
none of you proved P=NP).

******************************************************
Case 2) If the problem is known to be in P and not NPC it was marked as follows
******************************************************

You received 1 mark for saying it was in P _AND_ ATTEMPTING SOME ALGORITHM (no
matter how wrong it was). This is to say you didn't receive any marks if you
said it was in P and left it there.

For saying the problem was NPC received 0 marks (This again implies that none
of you proved P=NP).

You then received up to 4 more marks for your algorithm. Algorithms which
were completely wrong, or which ran in super polynomial time received 0 marks.
Other than that marks were deducted for small errors as needed.


Note: For the question on ST-HP, it was not enough to refer to tutorial or
online notes. You had to include it in you assignment.


******************************************************************************
Question 2)
******************************************************************************

The general trick here was to try and combine different weights into one
weight, and run this altered problem on partition. Using this information you
could determine the appropriate sets. (See solutions for more details).
I tried to give marks to algorithm which seemed to try and implement
something like the above idea. 

Note that some people had solutions which seemed to work but which
used negative weights. The Partition problem only allows positive weights.
You lost 4 marks for using what might be negative weights.
You lost up to 3 marks for calling Partition with an input other than the one
defined by the problem.

Marks were reduced for other mistakes as appropriate. There is normally a 
comment along with the mistake to explain the reduction in mark.

Many people had algorithms which were not even close to correct. They received
a mark of 0.

******************************************************************************
Question 3)
******************************************************************************

a) 5 Marks) Was mostly all or nothing. (ie. You understood it or you didn't).
In a few specific cases marks were deducted, and comments were given as 
explanation. 

Basically you had to explain there was no guarantee that the 
simulation of the machines would halt, and therefore you may never enumerate
all of the elements s_i.

b)  5 Marks) Was mostly all or nothing. (ie. You understood it or you didn't).
In a few specific cases marks were deducted, and comments were given as 
explanation

Basically, you had to explain that you could initially print a special symbol
at the left of the initial input to represent the end of the tape, and then
you could simulate the machine which used a one-way infinite tape.

Note: Many people gave a simulation of a two way infinite tape by a one way
infinite tape. This was worth 0 marks. Further, it was previously done in 
class.

c) 5 marks for each part.

Common mistakes.
	-1 for not stating what the inputs were to the various machines.
	-2 for not making proper distinctions between machines and languages.
	-2 for using nondeterminism, but not saying so.

A note on nondeterminism. Many people used this to answer the first part of 
this question. You should have included a theorem stating that any 
non-deterministic machine can be simulated by a deterministic machine. I
let the absence of this theorem slide.


d) 5 marks for each direction of the proof.


> 
> 
> Steve,
> 	I need your comments for PS3,
> 
> Michael
> 
>