week-1-union-find.markdown

Overview

1. Quick Find
2. Quick Union

Steps to developing a useful algorithm.

1. Model the problem.
2. Find an algorithm to solve it.
3. Fast enough? Fits in memory?
4. If not, figure out why.
5. Find a way to address the problem.
6. Iterate until satisfied.

This is a scientific method to designing and analyzing algorithms.

Dynamic Connectivity Problem

Given a set of N objects (doesn't matter what they are).

• Union Command Connect two objects.
• Find/connected query: Is there a path connecting the two objects? (even an indirect path)

Applications involve manipulating objects of all types like pixels, computers in a network, friends in a network, transistors in a chip, etc. When programming, it's convenient to name objects 0 to N - 1.

• Use integers as array index.
• Suppress details not relevant to the union-find.

This way we can access information quickly. We assume "is connected to" is an equivalence relation:

• Reflective: p is connected to p.
• Symmetric: if p is connected to q. then q is connected to p.
• Transitive: if p is connected to q and q is connected to r, then p is connected to r.

These properties are intuitive but important.

A connected component is maximal set of objects that are mutually connected (groups).

Implementing Operations

Find query. Check if 2 objects are in the same component.

Union command. Replace components containing two objects with their union.