Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Minimum spanning trees.
• Two algorithms: Prim's algorithm and Kruskal's algorithm.
• Examples.
• Proofs of correctness.
• Efficiency.

Preliminaries

Admin

• Question for student athletes (and other students): Should we allow practice to continue beyond the end of the season?

Checking in on terms and algorithms. I am confident in my understanding; I know some things; I don't know.

• Minimum spanning tree (MST).
• Any algorithm to construct a MST.
• Prim's algorithm for MSTs.
• Kruskal's algorithm for MSTs.
• Union-find.

Upcoming Work

• HW (Due Wednesday): 5-1, 5-2, 5-6, 5-7, 5-13, 5-20, 5-23, 5-28

Extra Credit

Academic

• CS Table Tuesday: Why is everyone so mean on the Internet?
• CS Extras Thursday: Walker on the fun of Bluetooth
• Sexual Misconduct at Grinnell College: Results from the 2013 and 2015 Sexual Conduct Surveys. 1-3 pm, November 8, JRC 101.

Peer Support

Questions

There is no topological sort for 5-2. What should we do?

Indicate why there is no way to topologically sort 5-2.

Remove an edge to permit topological sort and then topologically sort it.

Ask yourself whether this was intentional on Skiena's part or not (no answer to this last part needed).

Minimum spanning trees

Given a weighted non-directed connected graph, G(V,E) [connected: path from any vertex to any other vertex] [complete: edge from every vertex to every other vertex], build a new connected graph G(V,E'), s.t.

• E' is a subset of E.
• If G(V,F) is connected and F is a subset of E, the sum of the weights in F is less than or equal to the sum of the weights in E'.

Why do we call it a minimum spanning tree and not a minimum spanning graph?

• If there any cycles, throw away one of the edges, and it's still a spanning graph. Take away enough, it's a tree.

What techniques can we use?

• Broad algorithmic strategies
  • Divide and conquer
  • Greed
  • Exhaustive search
• Tools
  • Recursion
• Processes
  • Think a lot
  • Look for similar problems

Here's a graph! (Picture on the board.)

 Vertices: A, B, C, D, E, F, G
 Edges: AB(6), AC(7), AE(8), BD(9), CD(1), CE(1), CF(2), DF(5),
 EF(10), EG(14), FG(8).

An Exhaustive Algorithm

• Find each subset, E' of E.
• Determine whether G(V,E') is a minimum spanning tree.
• Find the smallest such E'.

Three Approaches

• Start with all the edges, repeatedly throw away large edges if you can do so.
• Start with no edges, repeatedly add the smallest edge that doesn't cause a cycle.
• Start with no edges and one node, repeatedly "grow" the tree in the cheapest way possible.