Held: Friday, 6 November 2015

Back to Outline 27 - Minimum Spanning Trees, Continued. On to Outline 29 - Shortest Paths.

Summary

We consider some details to make Kruskal's algorithm more efficient.

Related Pages

Overview

• Kruskal's algorithm, revisited.
• A Set ADT.
• The Union-Find algorithm.

Administrivia

• Food!
• How many of you read/understood union-find?
• Homework due Wednesday.
  • Implement the naive version of the algorithm described in 6-2 and determine the average distance the arm travels on sets of 10, 20, and 40 random inputs in where each coordinate is between 0 and 99.
  • Implement the clever version of the algorithm described in 6-2.
  • 6-1, 6-5, 6-6, 6-12.

Extra Credit

Academic

• Cool Physics talk on Tuesday.
• CS Table Tuesday: Cryptographic Back Doors.
• CS Extras Thursday: Mobile Sensing (UIowa).
• Innovation Talk next Thursday.

Peer

• Basketball alumni game Saturday at 1pm.
• Metal Radio Show tonight. (Only if you haven't listened twice already.)

Analyzing Kruskal's Algorithm, Revisited

sort the edges by weight
while the graph is not connected
  find the smallest weight edge that connects two components

• m rounds. At each round we inspect an edge and decide whether or not to add it to the MST.
• We add it only if it connects two different components.
• How much does it cost to determine whether an edge connects two different components?

Sets

• We can treat each component as a set of values.
• That means we should probably think about ADTs.
• Guess what: That's your responsibility.

Union-Find

• Implementing a subset of the set operations.
• Union(s1,s2): Given two sets, destructively create their union. (I'd call this merge, but that's me.
• Find(v): Determine what set a value is in.