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 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.
