We saw one more example of a dynamic programming problem, the 0/1 knapsack problem (only mentioned in the book, page 382), before we started talking about greedy strategies. We discussed the coin changing problem (Exercise 16-1 of the book), activity selection (Section 16.1) and Huffman coding (Section 16.3). We also discussed topological sort (Section 22.4). Next week, after the midterm, we will talk about some other basic graph algorithms (minimum spanning tree).
Note that the homework is due the week after the midterm.
Submission: you can submit the homework to me either by hardcopy in class or email it to me.
1. [Coin changing, 20pt] You want to make change for n cents using the fewest number of coins. Given a set of k coin denominations d <= d ... <= d[k], including a penny (ie. d=1), write an algorithm that finds the optimal change in time O(nk). Hint: we saw that greedy does not work in general.
2. [Printing CDs, 30pt] You have a sequence of n music tracks lasting t1,..., tn (in minutes) that you want to fit on the fewest number of CDs. We assume that you can fit 78 minutes of music on a CD (and that no track is longer than 78 minutes).
3. [Huffman coding, 20pt] Find an optimal Huffman code for text with letter frequencies: A: 75, B: 100, C: 25, D: 275, E: 50, F: 100, G: 25.
4. [Topological sort, 20pt] Here is another way of implementing a topological sort iteratively; recall that for a directed graph the in-degree of a vertex is the number of edges leading to that vertex (as opposed to leaving the vertex) [see Appendix B for graph terminology]. Given a directed graph G without any cycles, repeatedly pick a vertex of in-degree 0, remove it and all its outgoing edges from G. (You might want to do this with the graph in Figure 22.7a, page 550). The vertices are a topological sort in the order you remove them.
5. [Extra Credit, Line-breaking] For extra credit, you can still submit a solution for problem 1c from homework 4, that is, implementing the dynamic programming solution for line-breaking.