Quiz 2- Grading Standards/Common Mistakes

Question 1-

(a) This was graded as was described in the quiz: 
-5 points if correct counter-example using <= 4 monitors.  
-3 points if correct coutner-example using > 4 monitors.

Common Mistakes:
-Most mistakes in this problem related to not understanding 
what the problem was asking.

(b)  Again this was graded as described on the quiz: 
-5 points if you had the correct greedy solution, and had
O(n log n) runtime
-3 points if you had the correct greedy solutioon, but had
O(n^2) runtime.

Common Mistakes:
- Not sorting, this lead to a O(n^2) runtime
- Making a greedy choice which essentially reduces to that of 
part a.
- Making a greedy choice which attempted to minimize the overlap 
of the monitors, the overlap didn't matter!
- Making a greedy choice which attempted to find a monitor which 
had it's l_i closest to the current LeftBound.  This is will lead 
to the minimization of the overlap again.

Question 2-

(a)
-3 points for saying what the definition of m[i,j] is correctly.  If you
said anything related to the maximum value achieved by using the optimal
set of parenthesis between i and j.

(b)
-2 points for the correct base case xi.  You were also given credit if you
put xi + xj or xi * xj.  

Common Mistakes:

- Many people just said i, which is not correct.

(c)
-3 points for the correct recurrence relation.  There was little partial
credit given for this problem.

Common Mistakes:

- Many people used a recurrence of a form resembling the form of the
recurrence used for question #5 on homework #4, which is not correct.

(d)
-1 point for knowing that the recursion resembled Matrix Chain 
Multiplication (MCP) problem
-1 point for saying that it runs in O(n^3).