## Description

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)