Question 1: Most students solved the problem using a slight
modification to Prim's algorithm. I gave 1 point for stating the
algorithm; 0.5 points for referring to a proof (semi-formal arguments
were accepted in this case); 0.5 points for stating the runtime.

Question 2: About 70% of students gave a somewhat correct version of
the algorithm. I required a formal algorithm, but sometimes gave a
full 1 point for a clear paragraph description. The algorithm
descriptions were poor. I required a formal proof for this question (1
point). Students did badly on this part. Most have no idea what they
are trying to prove. Very unclear arguments. Student lost -0.5 for not
stating the runtime of their algs.

Question 3: I was generous on this question. Most students gave some
version of a correct algorithm. I accepted semi-formal arguments for
its optimality. -0.5 points for not stating the runtime of their algs.

Question 4: I used the marking scheme that you sent. Some students
gave semi-convincing arguments for using variants of "max_{ i >= j}
a_i - a_j". A few of these works got 2 marks for this solution +
proofs. Less convincing arguments were given at most 1 point for this
variant of the algorithm. Students did very badly on this question.