Question 1 (Coin changing problem) Suppose that you want to carry a money amount of n cents and you want to minimize the number of coins to carry. We only consider pennies, nickels, dimes, and quarters with denominations 1, 5, 10, and 25 cents, respectively. For example, an amount of n = 71 cents becomes two quarters, two dimes and a penny. An amount of n=81 becomes three quarters, a nickel, and a penny. 1. Describe a greedy algorithm to solve the above problem and write a pseudo code for it. 2. Prove the optimality of your greedy algorithm. Hint: You can consider each of the four possible decisions separately, i.e., picking a penny, a nickel, a dime, and a quarter, preferably in this order. 3. Establish the running time of your algorithm. 4. Apply your algorithm to the problem when n = 57