Question 1:
Generally well done.
Points were deducted if you didn't follow the instructions correctly,
or if your maximum independent set was wrong.

Question 2:
* 5 points for a creative, sensible heuristic choice (e.g. pick
  vertex of max. degree first)
* 15 points for a correct algorithm
* 5 points for proving your algorithm runs in polynomial time
* 5 points for providing an example where your alg fails
Fairly well done all around. The biggest mistake was that people
provided an example in which your algorithm sometimes failed; this
is not sufficient. You need to provide an example in which your
algorithm *always* fails (note that this might be an impossible
feat if you didn't employ some heuristic vertex selection tactic
like maxdegree).

Question 3:
* 8 points for correctly determining the size of the max.
independent set
* 17 points for having an algorithm that works correctly in
polynomial time
* 5 points for polynomial time justification
Overall, very well done by most. Some problems students used
exponential time algorithms, which resulted in a huge penalty.

Question 4:
* 3 points for realizing the structure of the graph (a family of
one or more disjoint cycles)
* 15 points for the algorithm
* 7 points for your correctness proof
* 5 points for complexity analysis
The biggest problem here was that students didn't realize that
such a graph may be more than one cycle. Apart from this, many
students relied on their algorithms from part (2), which was fine
if your alg from part (2) worked, and quite bad if it didn't.

Question 5:
* 2 points for showing HalfClique in NP
* 5 points for a working reduction algorithm
* 2 points for showing correctness
* 1 point for complexity analysis of reduction
Those who did this question did it fairly well all around.
Problems included insufficient complexity analyses, and
incorrect or partially correct algorithms. Some of you also
assumed we could take k-subsets in polytime or even solve
Clique in poly-time, which is incorrect.

General Notes:
PLEASE be careful about your mathematical notation. A graph
is an ordered pair G=(V,E), with V a set of vertices and
E = {{x,y}|x, y in V, x != y}.
If you tell me that you remove v1 from G, this doesn't *really*
make sense, because I don't know if you're just removing it
from V or if you're also removing all edges that contain v1.
And in certain problems, you're expected to return a vertex set,
where some of you returned a whole graph, or vice versa.
Note that I didn't take any marks off for this if I got the jist
of what you were doing and it seemed to work correctly, but in the
future, please try to be more precise.