Marker's comments on Test 2 (CSC 365S, winter, 2008)

(SEE SOLUTIONS ON COURSE WEB PAGE)

Question 1: Students generally did well.

In constructing G', some students added only one new vertex
to G instead of two.  This works, provided the new vertex is
connected to ALL vertices in G by new edges.  It does NOT work if
it is connected to only one or two vertices in G.  This is because
a vertex cover of size k+1 for G' need not include the new
vertex if it includes all vertices in G connected to the new
vertex.

Question 2:  Students generally did well on this.  For the
CORRECTNESS proof, some made the mistake of asserting that
the formulas $\varphi$ and $\varphi'$ are equivalent, where
$\varphi'$ is the smooth version of $\varphi$.  This is not
correct, since an assignment could satisfy $\varphi$ but
falsify $\varphi'$ by not giving opposite values to $x_i$
and $x'_i$.  (Equivalent formulas take on the same truth
value for all possible assignments.)

The correct assertion is that $\varphi$ is satisfiable iff
$\varphi'$ is satisfiable.

Question 3: Students had more trouble with this question,
although most did pretty well.  

One common mistake is to confuse the index set S, which
is a subset of {1,...,m}, with the set A' of weights a_i such that
i is in S.  Your program is supposed to find S, rather than A'.

The posted solutions give two methods of computing S.
Some students gave a solution which mixes the two methods,
and that does not work.