... Let An = {a, a2, ..., an} be a finite set of distinct coin types (e.g., a= 50 cents, a2= 25 cents, a3= 10 cents etc.). We assume each a; is an integer and that a > a > . > an. Each type is available in unlimited quantity. The coin changing problem is to make up an exact amount C using a minimum total number of coins. C is an integer > 0. (a) Explain that if a, 1 then there exists a finite set of coin types and a C for which there is no solution to the coin changing problem. (b) When an = 1 a greedy solution to the problem will make change by using the coin types in the order a, a2, ..., an. When coin type a; is being considered, as many coins of this type as possible will be given. Write an algorithm based on this strategy. (c) Give a counterexample to show that the algorithm in (b) doesn't necessarily generate solutions that use the minimum total number of coins. (d) Show that if An = { k-1, k-2, k } for some k > 1 then the greedy method in (b) always yields solutions with a minimum number of coins.