Marking scheme for class test 1

1. Correct answer: 1/2 mark, Explanation: 1/2 mark
2. For part (c): Correct solution of recurrence: 2 marks,
   No answer for naive use of master method: 1 mark or
   Yes answer for master method with additional clause on f(n) as in CLRS exercise 4.4-2: 1 mark
3. Recognizing that greedy method does not work: 1 mark
   correct counter-example: 1 mark
   correct DP algo: 3 marks
   DP recurrence: best(1,k)=min_i {best(1,i)+best(i,n)+length(1,n)}
   analysis: 1 mark for O(k^3)
4. Correct idea: 2 marks
   Correct pseudocode: 2 marks
   In case you have given the solution to swap the medians of groups of 5 with the first n/5 elements of the array A, you can get marks without pseudocode. For any other more complicated idea, pseudocode is essential.
5. Recognizing that there is no change after m iterations: 2 marks
   Correct answer (keeping a flag variable to record change): 2 marks