Question:

In the United States, coins are minted with denominations of 1,5,10,25, and cents. Now consider a country whose coins are minted with denominations of fd1; :::; dkg units. They seek an algorithm that will enable them to make change of n units using the minimum number of coins.

a) 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 algorithmfor making change of n units using US denominations. Prove its correctness and analyze its time complexity.

b) Show that the greedy algorithm does not always give the minimum number of coins in a country whose denominations are f1; 6; 10g.

c) Give an efficient algorithm that correctly determines the minimum number of coins needed to make change of n units using denominations fd1; :::; dkg. Analyze its running time.