CSC301.01 2015F, Class 28: Sets and Union-Find
==============================================

_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
      99.  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.