Reading

These notes and closely review Unit 5 Section 4.1.

Quiz questions

Have a greate break

We started class by recalling what we described as "Prim's algorithm":

Minimum Spanning Tree

Algorithm: Prim's MST
Input : G, a connected, weighted, undirected graph with n vertices and e edges
        r, a vertex in G 
Output: T a minimum weight spanning tree for G

0. mark each vertex's parent as "unknown" except r, which has parent nil ← i.e. only r is in the current MST
1. select vertex v with parent "unknown" with edge (u,v), where u's parent is 
   not "unknown",  such that (u,v) has minimum weight amongst all such edges

2. set v's parent to u  ← i.e. add v to thecurrent MST by connecting it to u

3. goto Step 1
      

Making a fully specified algorithm

We then discussed what it would take to make our outline a fully specified algorithm. It took some creative thinking, but we arrived at a version that used a heap and some clever arrays for tracking information, and this gave us an $O(e \lg n)$ version of Prim's algorithm.

The big takeaway is this: we usually think of greedy algorithms first in this very broad terms - what's the greedy choice. Once we've found a greedy choice that works, i.e. produces optimum solutions, then we still have a ways to go before we get a concrete algorithm - something that's descrived sufficiently to analyze.