Algorithms
Welcome to Algorithms, Part I (Week 0)
There is a course overview:
Union Find problem
Steps to developing a useable algorithm
- 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.
Dynamic onnectivity
Given a set of N objects:
- =Union command*: connect two objects.
Find/connected query: is there path connecting the two objects?
Modeling the connections
We assume "is connected to" is an equivalence relation:
- Reflexive
- Symmetric
- Transitive.
Connected Components
Maximal set of objects that are mutually