Problem 3. Consider the problem of making change for n cents using the fewest number of coins. Assume that each coins value is an integer.

Problem 3.a. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c 0 , c1 , , ck for some integers c > 1 and k 1. Show that the greedy algorithm of picking the largest denomation first always yields an optimal solution. You are expected to reason about why this approach gives an optimal solution. (Hint: Show that for each denomination c i , the optimal solution must have less than c coins.)

Problem 3.b. Design an O(nk) time algorithm that makes change for any set of k different coin denominations, assuming that one of the coins is a penny.