Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Kruskal's algorithm, revisited.
• A Set ADT.
• The Union-Find algorithm.

Preliminaries

Admin

• Food!
• Pens.
• 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
    1. C, Java, Python, Ruby, or Scheme.
  • Implement the clever version of the algorithm described in 6-2. Do a similar analysis. C, Java, Python, Ruby, or Scheme.
  • 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

• Metal Radio Show tonight. (Only if you haven't listened twice already.)
• SH performing tonight 8-10 at Prairie Canary.

Questions

Kruskal's Algorithm

sort all of the edges by weight
for each edge, e, in edges,
 if e connects two separate components, add it to MST

Analysis

• Sorting is O(mlogm)
  • (unless there is only a small range of edge weights)
  • Main loop repeats m times
  • How long does it take to determine if two vertices are in the same component?
    • How do we determine if two vertices are in the same component?
      • Label edge with its component
        • In each loop, relabeling is potentially O(n) (maybe worse)
        • O(mn) algorithm
      • Do a search (DFS or BFS) starting with one vertex: O(n+m)

Step back, think about what we are dealing with, abstract away details, think about implementation.

A Set ADT

Let's design the ADT: What are the primary procedures, their parameters, their product, their purpose, and potential problems?

• add(Set s, Value v) - gives back a new set
• add!(Set s, Value v) - mutates the set
• remove(Set s, Value v) - gives back a new set
• remove!(Set s, Value v) - mutates the set
• allSubsets(Set) - returns list of sets ; sam would use Iterator
• contains?(Set, Value v) - returns boolean
• isEmpty?(Set) - returns Boolean
• carve(Predicate, Set) - returns the subset of Set for which Predicate holds.
• map(Function, Set) - create a new set by applying the function to every element of the set
• cartesianProduct(Set, Set) - return a new set of the Cartesian Product of the two sets.
• size(Set) - return an integer indicating how many elements are in the set.
• complement(Set) - might just be subtract
• iterator(Set) - get an iterator that lets you step through the valus
• sortedIterator(Set, Comparator) - get an iterator that lets you step through the values in some order
• union(Set, Set) - returns Set
  • union!(Set,Set) - adds all of the elements of the second set to the first set
• intersection(Set, Set) - returns Set
  • intersection!(Set, Set) - removes elements not in the second set from the first st
• subtract(Set, Set) - remove anything in the second set from the first set, returning a new set
  • subtract!

The Union-Find algorithm

For Kruskal's algorithm, we need only two operations:

• union(Set,Set) - indicate that the two sets are one set (side effect)
• find(Value) - return the Set that contains the value
• Are two things in the same component? find(thing1) == find(thing2)

See book or board for the algorithm.

union(set1) root1 = findRoot(set1) root2 = findRoot(set2) if (root1.size > root2.size) root2.parent = root1; root1.size = root1.size + root2.size else root1.parent = root2; root2.size = root2.size + root1.size

How many steps does it take to find the set to which a value belongs?

log(size of tree)

Kruskal's algorithm, with this Union-Find structure, is O(mlogm + mlogn)

Awesome for spare graphs

Turning trees around can be really powerful.