Algorithms + Data Structures = Programs
The notion of algorithm was first formalized by Church and Turing in the 1930s (http://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis).
Algorithms are computational models that are replacing mathematical models.
2. Dynamic Connectivity
Given a set of N objects, we can define two operations:
- Union Command - connect two objects p and q (create a path between p and q)
- Connected Query - are two objects p and q connected (is there a path from p to q)
Properties of the Union-Find algorithm:
- Reflexive - p is connected to p (itself)
- Symmetric - if p is connected to q, then q is connected to p
- Transitive - if p is connected to an object q and q is connected to r, then p is connected to r
CONNECTED COMPONENTS - a maximal set of objects that are mutually connected.
We can implement our data type and the set of operations as a Python class:
An eager approach to implement the Quick-Find algorithm would be to use an array of ids. The operations we can define on our data structure are:
- FIND - p and q are connected if they have the same id
- UNION - merge components by changing all entities that equal id[p] to id[q]
Here we have an example on how our data structure looks after performing UNION commands:
Quick-Find algorithm implementation (eager approach):
Resulting Cost Model:
Defect: takes quadratic time (N^2) to process N union commands on a set of N objects
Other approaches and/or improvements to Quick-Find will follow in Part II.