Union-find algorithm

Introduction

This section talk abouts the union find problem. It is a set of algorithms for solving the so-called dynamic connectivity problem. We'll look at two classic algorithms. Quick Find and Quick Union, and some applications and improvements of those algorithms.

Setps to developing a usable algorithem.

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

The first step is to model the problem. Try to understand, basically what are the main elements of the problem that need to be solved. Then we'll find some algorithm to solve the problem. In many cases, the first algorithem we come up with would be fast enough and maybe it fits in momery. And we'll go ahead and use it, and be off and running. But in many other cases maybe it is not fast enough, or there is not enough memory. So, what we do is try to figure out why, find a way to address whatever's causing that problem, find a new algorithm and iterate until we are satisfied.

This is the scientific approach to designing and analyzing algorithms, where we build mathematical models to try and understand what's going on, and then we do experiments to validate those models and help us improve things.