Marker's comments for PS 4 (CSC 365h winter, 2008)
================

Generally well done.  Everybody seems to understand how to
do reductions and show that problems are NP complete.


Question 1 and 2
================

This question was well done.  Not much to say.


Question 3
==========

Most people had the right idea, but this was a harder
problem.  A common mistake was to simply assume that the
entries for the vector X are only 0 and 1.  You either had
to enforce this by adding appriate rows to A, or give a more
complicated proof of correctness.  Some people gave correct
reductions, but I had to take 10 mins before I proved it was
correct.  I cannot give full marks for answers like this.

Question 4
==========

This problem was generally well done.  The trick is to find
a formula that forces the set to have a least k nodes.  The
one common ommision is the assumption that k is small
relative to the size of the graph.  Many poeple gave a
construction that was exponential in the size of k and
claimed it was polynomial-time.  The only reason this is
true is because we can assume k <= n.  If it is larger, then
there is no independent set.  A small detail, but I felt it
was worth half a mark.