4. Consider the problem of making change for n cents using the smallest number of coins. Assume that the value of each coin is an integer. (a) Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Analyze the running time and prove that your algorithm yields an optimal solution. (b) Suppose that the available coins are in denominations that are powers of c that is, the denominations are cº, c¹, ..., ck for some integers c > 1 and k ≥ 1. Show that the greedy algorithm always yields an optimal solution. (c) Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n. (d) Give an O(nk)-time algorithm that makes change for any set of k different coin de- nominations using the smallest number of coins, assuming that one of the coins is a penny.

4. Consider the problem of making change for n cents using the smallest number of coins. Assume that the value of each coin is an integer. (a) Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Analyze the running time and prove that your algorithm yields an optimal solution. (b) Suppose that the available coins are in denominations that are powers of c that is, the denominations are cº, c¹, ..., ck for some integers c > 1 and k ≥ 1. Show that the greedy algorithm always yields an optimal solution. (c) Give a set of coin denominations for which the greedy algorithm does not yield an optimal solution. Your set should include a penny so that there is a solution for every value of n. (d) Give an O(nk)-time algorithm that makes change for any set of k different coin de- nominations using the smallest number of coins, assuming that one of the coins is a penny.