12.9 Exercise 1

A cashier rings up a sale for $4.63 cents in U.S. currency. The customer pays with a $5 bill. The cashier would like to give the customer $0.37 in change using the fewest coins possible. The coins that can be used are quarters ($0.25), dimes ($0.10), nickels ($0.05), and pennies ($0.01). The cashier starts by selecting the coin of highest value less than or equal to $0.37, which is a quarter. This leaves $\$ 0.37 - \$ 0.25 = \$ 0.12$. The cashier selects the coin of highest value less than or equal to $0.12, which is a dime. This leaves $\$ 0.12 - \$ 0.10 = \$ 0.02$. The cashier selects the coin of highest value less than or equal to $0.02, which is a penny. This leaves $\$ 0.02 - \$ 0.01 = \$ 0.01$. The cashier selects the coin of highest value less than or equal to $0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.

1. Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
2. The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.