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[1] <= d[2] ... <= d[k], including a penny (ie. d[1]=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 t₁,..., t_n (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).

1. [10pt] Describe a greedy approach to assigning tracks to CDs (high-level description or pseudocode).
2. [5pt] Give an example where your greedy approach does not find an optimal solution, that is, uses more CDs than is necessary to place all the tracks.
3. [5pt] Show that if we let t = t₁+ ...+ t_n, the total duration of our music, we need at least [t/78] CDs to place all tracks (independent of the method you use).
4. [10pt] How bad can your algorithm be? That is, can you show that the number of CDs your greedy algorithm uses is within some factor of an optimal solution? Hint: part c. should come in handy here.

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.

1. [5pt] Why is there always a vertex of in-degree 0? Hint: what can you say about a graph in which every vertex has in-degree at least 1?
2. [5pt] Argue that the algorithm produces a topological sort.
3. [10pt] Give a high-level description (or pseudocode) of how you would implement this algorithm to run in time O(|V|+|E|), where G = (V,E).

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.