Opening discussion: Let's say you are working at a cash register (in the US), and need to make $0.66 in change, using the fewest number of coins. How would you go about doing this? What coins would you use? How did you arrive at your answer?

Follow up question: what if you were working on a different planet, with a different currency system. Make up one where your approach from before would fail.

• Greedy Approach to Algorithms!

Practice!

Given the graph below:

• [ ] Find an MST using Prim's algorithm
• [ ] Find an MST using Krukal's algorithm (show your work please!)
• [ ] As a group, work together to find a MST using Prim's and then Kruskal's algorithms.
• My solutions - note that these are not necessarily unique (and I chose some random vertices as my starting point or sources)
• Huffman trees and codes