We consider the coin changing problem: making change for n cents using the fewest number of coins. Each coin's value is an integer larger or equal to 1. We assume that the set of coin denominations contains a 1 cent coin. Question 8 Write a formal problem statement for the coin changing problem. Question 9 Assume a set of coins S-1,5,10, 25 cents. A greedy algorithm for the coin changing problem is to pick the largest coin denomination E in S less than n and solve the problem of making change for n - l cents. Show that this greedy algorithm yields an optimal solution for S 1,5,10, 25]. You have to write the reduction to sub-problem(s) and prove optimal sub-structure. Give examples of how your algorithm works for making change for 17, 90, 123, 165, and 236 cents. Question 10 Is there a set of S coin denominations and an integer n such that more than one optimal solution exists? If yes, you should provide a concrete example and try to make it as simple as possible Question 11 Give a set of coin denominations for which the greedy algorithm pro- posed above does not yield an optimal solution