Posted by: jeff | September 14, 2010

Here are some coarse-grained guidelines that we will be using to grade your homework assignments this week. This is a rough breakdown of points, however, and the more detailed partial credit assignments will be subjectively determined by Alex and myself once we’ve seen the spectrum of answers. Keep in mind, it is better to err on the side of caution when writing up your assignments: explain your thoughts/arguments thoroughly, don’t assume that we will “know what you mean” unless you explicitly say what you mean.

1. For both Ex.1 and 2: 4 pts for choosing T or F correctly, 6 pts for a proof idea, and 10 pts for a valid counterexample or proof, so 20 pts. total for each problem. (40 pts.)
2. For Ex. 3: 20 pts for a proof/counterexample idea explaining the insight behind why you think the property holds or not, and how you intend to prove or disprove it. 25 pts for a detailed proof or counterexample (45 pts.)
3. 4 pts. for outlining the proof idea. 2 pts. for illustrating at least one example for some specific n. For the proof of the general case (any n>= 2): 4 pts. for setting up an instance of SMP that works for any n, and 5 points for proving that this instance satisfies the property that the while loop of the algorithm runs $\Omega(n^2)$ times. (15 pts.)