In the United States, coins are minted with denominations of 1, 5, 10, 25, and 50 cents. Now consider a country whose coins are minted with denominations of fdi,..., dk^ units. They seek an algorithm that will enable them to make change of n units using the minimum number of coins. 1. (20 pts) The greedy algorithm for making change repeatedly uses the biggest coin smaller than the amount to be changed until it is zero. Provide a greedy algorithm for making change of n units using US denominations. Prove its correctness and analyze its time complexity. 2. (20 pts) Show that the greedy algorithm does not always give the minimum number of coins in a country whose denominations are 1, 6, 10) 3. (20 pts) Give dynamic programming algorithm that correctly determines the minimum number of coins needed to make change of n units using denominations [di,..., dk) Analyze its running time