Marking remarks for Test 2, by Greg Kondrak:

In grading Test 2, I was looking specifically at the following:

Questions 1a and 1b
-------------------
- knowledge of the definition
- correct idea 
- proof of its correctness 

Question 2a
-----------
- formally defined V', E', and B'
- the distinction between the "easy" case and the "hard" case
- correct reduction idea

Question 2b
-----------
- implication in both directions

Question 2c
-----------
- correct proofs in both directions
- the distinction between the "easy" case and the "hard" case
- clarity of the argument

Question 3
-----------
- correct pseudocode of the algorithm
- statement about its polynomial time complexity
- the initial check for the existence of a solution
- clarity

General note: If you have not proposed any reduction,
you can't claim marks for proving it. If an implication
is false, you can't claim marks for proving it true.