Marking scheme for Test 1:

Remark: No 20% for "I don't know"'s was offered for the bonus question
(because it is already a bonus question!). 
No 20% was offered for any other problem, unless you mentioned clearly "I 
don't know how to solve this".


Q1:
 (a)

2 marks for defining the "promising" solution (note that you must
provide a mathematical expression). At most 1 mark was given for this part
if you did not use the word "every" in the definition--this is crucial
in showing the right result.

2 marks for explaining why proving that T_i is promising is enough (see
comment "ENOUGH"). This part must be as in the solutions-- no other
explanations were accepted.

(b) This is easy, as long as you mention that T_0 is the empty set. You must
show the work (that' s why giving an expression in (a) is important)

(c)  1-2 marks if you show that you know what this case is about
(i.e. edge e_{i+1} is rejected). -1 mark if you do not say
*explicitly* that e_{i+1} is not in T_{opt}. You have to show the work; again
you have to show that the expression is satisfied.

(d) This is the standard Exchange Lemma in the notes. -1 mark for mistaken
assumptions on T_1, T_2, G, -1 mark for wrong quantifiers in the statement.
-1 mark if instead of "spanning trees" you mention MST's. These were the most
common mistakes; there might have been others.

(e)

In most cases the proof was a copy of the proof that Kruskal's algorithm is
optimal. You should talk about "every" MST (case 2a) or "some" MST (case 2b).
See comment "KR" meaning "Kruskal-like". As far as I recall no student got
this part right (I think the highest mark was 7/8 for this part). At most 5/8
if the proof was in this category. You must provide sufficient detail in the
proof (show how to use the Exchange Lemma), and how you deduce the cost of the
new (optimal) tree (-2 if the last case was missing). Case 2a counts for only 1
mark; the remaining 7 marks count towards case 2b which is considerably harder.


Q2:
 (a) 1 point for stating the size of the array (if not, see comment "SIZE")
     3 points for a correct definition of array A: You have to be very
     specific/clear to get full marks here.
     1 point for saying what is the solution to the problem

 (b) 1 point for pointing out A[1,1]
     2 points for considering the marginal cases (i.e. A[i,1] and A[i,i])
     5 points for the general recurrence

Note: In some solutions the marginal cases were not present, but there was
some attempt to get around them by setting the profit of an "out of the
border" moves to 0. This will work only if the array contains *positive*
integers only. There is no such assumption, however, in the statemnt of
the problem.

At most 3-4 out of 8 marks if the recurrence was not correct.

2 marks go towards the justification. Justification here means: explain how
you got the recurrence (i.e., what each term that appeards in the
recurrence stands for). Anything else is NOT a justification.


 (c) 1 point for just saying O(n^2).
     1 point for a brief explanation.

0 marks if the running time is not correct.


Bonus:

There have been various attempts here. If the algorithm appears to work you got
full or almost full marks. If the intuition is right, 2-3 out of 5 marks
(e.g., you did not show what are the arguments when you call the recursive
function the very first time, or alternatively, if you did not clearly describe
how to find the "right" element in the last row, or in cases you just described
in a high-level how the algorithm *would* work).  Note that, as in all DP
algorithms we have seen so far, we have to work our way "backwards", and not
"forwards" (the latter approach will not work).