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. Coin exchange a) Create a greedy algorithm and prove that it produces an optimal solution. b) Is the algorithm optimal if the available coins are: 1c, 5c, 10c and 26c. c) Is the algorithm optimal if the available coins are: 1c, 5c, and 25c. d) 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. Prims Algorithm Algorithm Visualization 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 results. [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)
