Plz do each step.

Consider the problem of making change for n cents using the fewest number of coins. 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, k1, and c1=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) (2 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) (8 pts) Prove that the coin changing problem exhibits optimal substruct ure. (c) (15 pts) Design a recursive backtracking (brute-force) algorithm that ret urns the minimum number of coins needed to make change for n cents for any set of k different coin denominations. Write down the pseudocode and prove that your algorithm is correct. No points will be given for an algorithm without the proof. (d) (7 pts) Modify your pseudocode in part (c) to use memoization. Write down the modified pseudocode and expalin your choice of the table dimensions and the indices used for memoization. A solution without the explanation will receive 0 points! (e) (13 pts) Design a bottom-up (non-recursive) O(nk)-time algorithm that makes change for any set of k different coin denominations. Write down the pseudocode and analyze its running time. Argue why your choice of the array and the order in which you fill in the values is the correct one. Notice how it is a lot easier to analyze the running time of the bottom-up (non-recursive) dynamic programming solution (however, it is a lot easier to design/understand the top-down solution first). 1 (f) (3 pts) Suppose now that the available coins are in the denominations that are powers of c, i.e., the denominations are c0,c1,,ck for some integers c>1 and k1. 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. (g) (7 pts) Prove that your greedy algorithm always returns an opt imal 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