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 dynamic programming to make change consisting of quarters, dimes, nickels, and pennies and prove that your algorithm yields an optimal solution. Implement your algorithm and test your solution.

b. Describe a greedy algorithm to make change consisting of quarters, dimes, nickels, and pennies. Prove that your algorithm yields an optimal solution. Implement your algorithm and test your solution.

c. Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are c⁰, c¹, ...., c^k for some integers c>1 and k>= 0. Show that the greedy algorithm always yields an optimal solutions.

Please submit your source codes, corresponding proofs, and a screenshot of execution results.