Percolation Models

by Gilbert Keith

I remember writing a bonus part for chicago open on percolation models back in the day. In retrospect it was really poorly written. The concept itself is so simple! You should watch the above video explaining it.

So apparently, Union Find problems, where the idea is to find, among a set of objects with partial connections, how the subsets are clustered. In more technical terms, if you have a set of objects, and various equivalence relations defined for that set, union find essentially boils down to finding the equivalence classes.

I just learned about various ways in which you can take a simple problem like Union find, introduce complexity in the number of operations involved (eg. finding the equivalence classes among 1 billion objects could take 1 billion billion (10 ^ 18) calculations. But it’s possible to significantly reduce this number. Which is why algorithms are awesome.

 

 

Advertisements