1 Quick Lecture Recap
Go over the scheduling problem proof again.
2 Making Change
You have an unlimited supply of 1c, 5c, 10c and 25c coins, and you want to
make change for C cents using as few coins as possible.
Create a greedy algorithm and prove that it produces an optimal solution.
Is the algorithm optimal if the available coins are: 1c, 5c, 10c and 26c.
Is the algorithm optimal if the available coins are: 1c, 5c, and 25c.
The algorithm is sometimes optimal depending on the available coins. Name 1
type of coins that allow for an optimal solution?
Powers. Example, 2n: 1, 2, 4, 8 …
3 Minimum Spanning Tree – Prim’s Algorithm
Review Prim’s algorithm.
4 Extra – Not required content!
Some students were asking questions about how we could describe ALL sets
of coins that produce an optimal solution. We found that powers are a good
example of coins that work, but there are more. Example: 1, 5, 10
This is a difficult problem but recent research (up to 2004) has yielded interesting
[Chang and Gill] proved that for a set of coins, where N is the largest coin, if
there are no counterexamples where the input value, V is 1 ≤ V ≤ N 3.
1[David Pearson] found an algorithm that checks if a set of coins is “canonical”
(always produces an optimal solution using our greedy algorithm) in O(n3)