For problem 2, can the songs be placed arbitrarily on the CDs as long as each CD contains the song in sorted order?
No. The first CD must contain song 1, song 2, …. song k. Then the second CD must contain song k+1, song k+2, …. and so on. So all you are doing is deciding when to end the current CD and start the next. The solution to this problem is not complex and neither is the proof. However, this is a good problem to be sure that you understand how to prove that a greedy algorithm is correct. If you feel that your solution is obviously correct and cannot prove it then you don’t understand the mechanism provided in class to prove correctness and should come to our office hours and go over it with us.
