Short description: Analyze novel greedy algorithms using exchange arguments; prove correctness.
Relevant notes: Topic D: Greedy Algorithms.
Construct greedy algorithms and prove correctness using exchange arguments. Identify failures of exchange arguments.
You are a cashier making change. You have a supply of quarters (worth 25 cents), dimes (worth 10 cents), nickels (worth 5 cents) and pennies (worth 1 cent). Given an amount, such as 87 cents, your goal is to make change using as few coins as possible.
Give a greedy algorithm for this problem. Prove the algorithm is correct using an exchange argument.
Algorithm: We use as many quarters as possible until the amount remaining is less than 25 cents. Then we use as many dimes as possible until the amount remaining is below 10 cents. Then we use a nickel if possible, so the amount remaining is below 5 cents. Then we use pennies for the remaining amount.
Proof: Consider any other solution. If it has fewer quarters than greedy, then it has a collection of non-quarters that adds up to 25 cents or more. Then we can reduce the number of coins. There are two cases. If this collection has three dimes, we can replace them with a quarter and a nickel, reducing the total number of coins. Otherwise, it has 0-2 dimes and some number of nickels and pennies, which implies that there is a subset worth exactly 25 cents. We can replace this whole subset with a quarter, reducing the number of coins.
Similarly, suppose it has the same number of quarters as greedy but fewer dimes. Then it has a collection of nickels and pennies that add up to 10 cents or more; we can replace 10 cents of that collection with a dime. And suppose the solution has the same number of quarters and dimes, but fewer nickels. Then it has 5 or more pennies; we can replace 5 of them with a nickel.
To pass, a solution must pass both parts.
To pass, a solution must follow the course requirements for writing and proofs.
The proof must show that any solution that differs from greedy can be improved by exchanging in a larger-denomination coin for several smaller ones. In particular, it has to handle the case of 30 cents made up of 3 dimes correctly. It cannot just assume that there is a set of coins worth exactly 25 cents that can be swapped out for a quarter. It should be careful to cover all cases. It should not assume the suboptimal solution has a particular structure.
The numerical rubric for this problem is: