Consider the problem of making change for n cents using fewest number of...

Please provide REASONING and EXPLANATION

Please write CLEARLY

Problem 3. Consider the problem of making change for n cents using the fewest number of coins. Assume that each coin's value is an integer. Problem 3.a. (4 points) Suppose that the available coins are in the denominations that are powers of c, i.e., the denominations are co,c,...,ck for some integers c>1 and k > 1. Show that the greedy algorithm of picking the largest denomation first always yields an optimal solution. You are expected to reason about why this approach gives an optimal solution. (Hint: Show that for each denomination c', the optimal solution must have less than c coins.)