1 Coin Changing Again (30 pts) Consider again the problem of making change for n cents using the fewest number of coins. Again, assume that we live in a country where coins come in k different denominations C1, C2, ...,ck, such that the coin values are positive integers, k > 1, and ci = 1, i.e., there are pennies, so there is a solution for every value of n. For example, in case of the US coins, k = 4,C1 = 1, C2 = 5,C3 = 10,C4 = 25, i.e., there are pennies, nickels, dimes, and quarters. To give optimal change in the US for n cents, it is sufficient to pick as many quarters as possible, then as many dimes as possible, then as many nickels as possible, and finally give the rest in pennies. (a) (5 pts) Give an example of coin denominations, such that using the above strategy of picking the maximum number of coins of the largest denomination will not lead to an optimal solution, i.e. will not minimize the number of coins in the change. (b) (10 pts Suppose now that the available coins are in the denominations that are powers of c, i.e., the denominations are c, c-, ..., ck for some integers c>1 and k > 1. Write down pseudocode for a greedy algorithm that returns the fewest number of coins needed for making change for n cents. Analyze the running time of your algorithm. (c) (15 pts) Prove that your greedy algorithm always returns an optimal solution for coin denominations that are powers of c. Hint: prove the greedy choice property. Don't forget to state explicitly the precise claim you are proving before proving it