Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer.
a. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution.
d. Give 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.