Problem Set 2: Marking Scheme and Common Problems

General: Every question was worth 10 marks for a total of 50. For
all questions you needed to have a basically valid approach to get
more than 1/2 marks. Style etc. was a consideration. For questions
1, 2, 3, and 5 this may mean a mark or two, for question 4 it was
more important.

Q1: There was only one valid way of doing this, by adapting the
dynamic algorithm for the knapsack problem. In particular, brute
force search is NOT guaranteed to finish in a time polynomial in
the size of the input.

6-10: Needed correct answer up to style or minor flubs. These were
flagged: use of the same index variable in two different senses in
a single expression, use of the K(S) notation from the knapsack
example without definition, strict for non-strict inequalities.

5-6: More fundamental problems like missing base cases etc.

< 5: Didn't use the dynamic algorithm (or the right one anyways).
Common problems: attempt to use what looked like a greedy algorithm
to solve the problem; and algorithms that looked for a partition
made up of _consecutive_ weights.


Q2: Establishing the parameter B and finding the set S were worth
roughly equal marks; proof that MSSD was in NP was worth 2 marks.
For finding S the essential method was to repeatedly query the MSSD
solver while removing weights from the original problem. There were
basically two ways to do this properly: one was to put the weight
back if it was found to be necessary for the solution (as in the
solution handout), the other was to modify the other parameters so
that the weight was no longer needed.

8-10: Correct up to style. Common stylistic quibble: using binary
search to find B.

6-8: Seemingly correct but riddled with ambiguity etc. As well, any
type of assertion that linear search for B was _not_ polytime.

4-6: Correct approach but marred by explicit problems with indexing
etc. Also, insisting on using binary search and then screwing it up.
Common problem: using MSSD = TRUE as criterion for adding weight to
S.

< 4: Way off base or too garbled to make out.


Q3: As above, NP proof was worth 2 marks. What was again desired was
a repeated query while removing edges, and as above there were
essentially two ways to pull it off: if the edge is necessary, either
put it back into the edge set, or remove its end-vertices. Breakdown
is the roughly the same as for Q2.

Common problems:
- Checking all n-sets of edges until a matching is found (!)
- Trying to find a matching by starting with E empty and then adding
edges one at a time.


Q4: Since the department expects me to spend < 15 minutes on each
problem set in total, there was no way for me to confirm that the
TM's handed in did in fact work properly (>= 20 states were needed,
so the average table was >= 2 pages long). Hence the mark here is
based largely on aesthetic judgements: about half for presenting a
plausible TM itself (e.g. large enough etc.), and about half for
the quality of the accompanying commentary/documentation (which is
the usual scheme in programming courses).


Q5: In general this question was done very badly. The basic idea,
which most of the class figured out, was to add/remove one or two
weights to/from the original problem. Letting W be the sum of all
the weights in the original instance of PARTITION, the two valid
variations I encountered were:
a) adding two weights x and y such that x > 1/3 * (W+x+y) and
   x+y > 2/3 * (W+x+y), with x + 1/2 W = 2 * (y + 1/2 W) e.g.
   5/2 W and W as in the solution handout, or
b) adding one weight x = 1/2 W + w_i for some weight w_i in the
   original problem, and removing w_i from the weight set.
As well, some students tried reducing knapsack to Double-Partition
and then invoking transitivity, which should work in principle, but
nobody was able to pull it off (it looked like they were trying to
adapt the PARTITION <=p SKD proof...)

>= 7: You needed to add/remove the correct weights.

~ 6: Things like adding a (1/2 W + e) weight and then shaving e off of
one of the w_i's, or adding e.g. e/2 to the original set as well
(this won't really work, but these students seemed to at least realize
the problem with...

~ 5: Adding 1/2 W to the weight set. This was the most popular answer,
though of course it results in the instance of DP being always "yes";
but it's better than...

~ 3: Adding 1/3 W to the weight set. In most cases I couldn't exactly
make out the justification, but it seemed that were sort of doing the
same thing as immediately above, but going in the wrong direction
(trying to reduce DP to PARTITION).

WORSE: Not modifying the instance in any way; generally accompanied by
several lines of random equations.