Question:

Answer:
The Greedy Algorithm help us address the minimum number of coins/currency denominations required to make up a given amount.
The best apporach in this is to take the maximum number of the largest denomination available, within the specified amount, subtract it, then take the next largest denomination available and subtract, etc, till we get the specified amount. This will help us arrive at the least number of coins required to make up the amount.
Now, answering the questions
a) In US currency,
Quarters - 25 cents
Dimes - 10 cents
Nickels - 5 cents
Pennies - 1 cent
Amount required - 93 cents
Largest denomination available = Quarters (25 cents)
We can have three quarters = 3*25 = 75 cents
Remaining amount = 93 - 75 = 18 cents
In 18 cents, we can have 1 dime (10 cents)
Remaining amount = 18 - 10 = 8 cents
In 8 cents, we can have 1 nickel (5 cents)
Remaining amount = 8 - 5 = 3 cents
In 3 cents, we can have 3 pennies (1 cent)
Remaining amount = 3 - 3 = 0 cents.
Now we have found the solution to our problem.
93 cents = 3 Quarters + 1 dime + 1 nickel + 3 pennies
Therefore, total number of coins = 3 + 1 + 1 + 3 = 8 coins.
The algorithm output for 93 cents is 8.
b) In a country there are below denominations coins
20 cents, 10 cents, 5 cents and 1 cent
Amount required = 57 cents
Following same algorithm steps as above.
57 cents can contain 2 * 20 cents
Remaining amount = 57 - 40 = 17 cents
17 cents can contain 1 * 10 cents
Remaining amount = 17 - 10 = 7 cents
7 cents can contain 1 * 5 cents
Remaining amount = 7 - 5 = 2 cents
2 cents can contain 2 * 1 cent
Remaining amount = 2 - 2 = 0 cents.
Now we have found the solution to our problem.
57 cents = 2 * 20 cents + 1 * 10 cents + 1 * 5 cents + 2 * 1 cent
Therefore, total number of coins = 2 + 1 + 1 + 2 = 6 coins
The algorithm output for 57 cents is 6.