Algorithms: Dynamic Connectivity and Quick Find

So, I've signed up for this Algorithms course with Coursera.

It starts on Monday 30th October, but I'm getting a head-start, because I'm a little bit rusty.

The first lesson is all about Union Find: Dynamic Connectivity and Quick Find.

Key takeaways:

1. To find the algorithm to solve a problem you first need to understand the problem.
2. If at first you don't succeed, try and try again.
3. And even if you do succeed, keep trying until you find the best solution - That's the scientific method.
4. When joining the dots, the point of entry is everything.
5. Equivalence relations:
• Reflexive: A thing is connected to itself - i.e. 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.
6. Union commands: They are the match-makers.
7. Connected Queries: They follow the breadcrumbs and discover connections.
8. Data Structures: Using integers as an array index is convenient to start with. Do it.

I'll put my notes up in a convenient infographic or something shortly.

Thanks for reading!