1 Coin Change
We now prove the simple greedy algorithm for the coin change problem with quarters, dimes, nickels and pennies are optimal (i.e. the number of coins in the given change is minimized), when the supply of each coin type is unlimited.
Let qo , do , ko , po be the number of quarters, dimes, nickels and pennies used for changing n cents in an optimal solution.
1. First, show that do ≤ 2, ko ≤ 1, po ≤ 4. Also, show that if ko = 1, then do ≤ 1.
2. Now show it is always optimal to choose as many quarters as possible.
3. Finally, show that the greedy algorithm is optimal in its choice for dimes, nickels and pennies.
2 Problem 4.4 on page 190 of your textbook
Do problem 4.4 on page 190 of your textbook. This is the problem that asks you to design an algorithm to determine whether a sequence is a subsequence of another sequence.
3 Problem 4.13 on page 194 of your textbook
Do problem 4.13 on page 194 of your textbook. Note you need to prove your algorithm is indeed optimal.
4 Huffman coding
1. There is a long string consisting of characters A, C, G and T . The frequencies of A, C, G and T are
40%, 25%, 25% and 10% respectively. What is the Huffman encoding of these four characters?
2. Under a Huffman coding of n symbols with frequencies f1 , f2, ..., fn , what is the longest a codeword could possibly be? Give an example set of frequencies that would produce this case.
