CSC373: Greedy Coin-Changing Daniel Zingaro
daniel.zingaro@utoronto.ca
1 Canadian Coins
You have an unlimited supply of 1c, 5c, 10c and 25c coins, and you want to make change for A cents using as few coins as possible. For example, if you want to make change for 15c, then the best you can do is use one dime (10c). That¡¯s better, for example, then using 15 1c coins.
Write a greedy algorithm that attempts to solve this problem, then write a complete proof that your algorithm is correct, following the structure presented in class.
Hint: you want to consider each coin that the greedy algorithm adds. There¡¯s exactly one optimal solution for any given problem, so no ¡°change OPT to OPT2¡± kind of argument makes sense here.
2 New Coins
Suppose now that we have the following types of coins: 1c, 5c, 10c, 26c. Show that the greedy algorithm is not optimal in this case.
3 When Does it Work?
OK. So your greedy algorithm works for Canadian coins, but there are cases where it does not work. Can you think of other cases where your algorithm works or doesn¡¯t work?
How about when coins are powers of 2, like 1c, 2c, 4c, 8c, 16c . . . does your greedy algorithm work
in that case? And can you prove it?