Describe an efficient greedy algorithm for making change for a specified value using a minimum number of coins, assuming there are four denominations of coins (called dimes, nickels, quarters, and pennies), with values 10, 5, 25, and 1, respectively. The input of your algorithm is an integer number N representing the total number of cents. The out put specifies for each denomination how many coins are to be used. Here, "efficient" means O(N). 1. Present pseudocode, running time analysis, proof of correctness. 2. Find four denominations of coins, one of which is 1 cent, and one value of N for which the greedy algorithm fails to return the minimum number of coins. Show the greedy and optimum solutions. 3. Present a dynamic program for any set of k denominations. Strive for running time of O(kN), but make sure that the running time is polynomial in k and N. Present the pseudocode, discuss correctness, and analyze the running time.