Partial credit scheme for the final
===================================
Ultimately, all partial credit is somewhat arbitrary. It was pretty straightforward for most
of the questions. For multiple choice, I generally took a point off for each choice missed.
For the straight true/false questions, if you gave the completely wrong answer and a tiny bit
of justification (or none at all) then you generally got 0 points. The rest of the credit was
given based on the particularities of the question (whether or not the argument was valid,
etc.)
Here are two problems where the grading scheme was particularly hairy:
-------
For the heap problem:
If the subset of {A,B,C} you gave was disjoint from the correct set, then you got 0.
If the subset of {A,B,C} you gave had a member in common with the correct set, you got 1.
If you gave the correct subset of {A,B,C}, you got 2.
Notice this made those answers where "none" was the correct answer all-or-nothing (0 or 2
points). This made sense because those two seemed easier than the others. Ideally the
question should have been 3 points each, and we would give a point for each one that you
correctly identified (if you correctly identified that A is or is not an answer, etc.)
Alas, it was not so. I suppose I could have given fractional points out of 2 instead of 3,
e.g. 2/3, 4/3, and 2. If you really think it will help your score, I'll do it, but the
toll for my undertaking such pain will be 1 point. (Just kidding-- I won't do it.)
--------
The TG problem was bad, because the solution given out was wrong. As far as we know, no
slight modification of the algorithm will work. So despite the fact that this was a
multiple-choice test, because it is also an algorithms test, I gave more points when
people showed their work. I basically ignored the difference between the polytime and
linear time questions, except when it was especially unclear to me what you were thinking.
Roughly, this is how I graded the TG problem. There were grades between these as well, like
4 and 7.
0 if you left it blank, or: you said it was NP-hard and put no marks on the other answers
1 if you wrote a lot of x's and o's but their correlation to the problem was minimal
3 typically when people identified it is NP-hard but stated that the algorithm was correct
and could be modified to run in linear time but gave no explanation
5 if you said it was NP-hard, claimed the algorithm could be modified but proposed an
well-thought but incorrect modification or one that was somewhat not understandable.
6 typically when people identified it was NP-hard, stated that the algorithm could not be
modified easily, but did not justify why in a clear way
9 if you identified that it isn't NP-hard, found a killer counter-example to the stated
algorithm, but did not propose a modification to the algorithm, or a correct modification
10 if you identified that it isn't NP-hard, found a proper counter-example, and gave a
correct algorithm
I also took off a point for deliberately ambiguous answers, like circles within X's, etc.