Marking Scheme for assignment 2 and hints/solutions
- Problem 1: (a) and (b) are incorrect, most of you have given correct
counter-examples. 2 marks each.
Solution (c) is correct. Assume that the optimal solution has some other
order, which violates the given order at position i. Show that swapping
ith and (i+1)st files reduces the cost of the solution, thereby contradicting
optimality. (5 marks)
- One of the solutions: Find the longest common subsequence. Insert the
remaining characters from both A and B at appropriate places. O(n^2) time.
(5 marks)
-
The solutions to the 3rd (and to Problem 8 from midsem!) can be found
here
(This also explains the delay in posting the solutions).
Each of (a) to (e) carry 2 marks.