Problem 4: Coin Changing Consider the problem of making change for n cents using the fewest number of coins. Problem Set #5: March 12, 2021 (noon) 2 (a) When people give change, they usually use the following greedy strategy: Select the largest coin denomination that is less than n (say it is c), and use one of these coins. Repeat for n-c cents. Prove that this greedy algorithm gives the optimal solution for US coins: quarters, dimes, nickels, and pennies. Hint: Observe that: No optimal solution can include 5 pennies. Similarly, no optimal solution can include 2 nickels, or 1 nickel and 2 dimes. (These can be replaced with 1 nickel, 1 dime, and 1 quarter, respectively.) Finally, we note that no optimal solution can include 3 dimes because this can be replaced with 1 quarter and 1 nickel. Use the above observations to prove that an optimal solution for n > 25 must include at least 1 quarter, that an optimal solution for 10