Let A,-{ al, a2, , an } be a finite set of distinct coin types (e.g., ?,-50 cents, a2-25 cents, a,- 10 cents etc.). We assume each ai is an integer and that ai > 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 integer0. (a) When an a greedy solution to the problem will make change by using the coin types in ., a. When coin type a is being considered, as many coins of this type as the order a, az, possible will be given. Write an algorithm based on this strategy. solutions that use the minimum total number of coins. with a minimum number of coins. (b) Give a counterexample to show that the algorithm in (a) doesn't necessarily generate (c) Show that if Ank1, k"^, k then the greedy method in (a) always yields solutions