Revisions to Percolation Model

added 156 characters in body

Source Link

edited Sep 26, 2016 at 14:47

user118482

Now the goal is to perform efficient percolates() queries (boolean method that checks whether system percolates or not), using the UnionFind algorithm (Brute-force solution will take quadratic time, which is not scalable for huge systems).

Additional materials that might be useful:

Now the goal is to perform efficient percolates() queries (boolean method that checks whether system percolates or not), using the UnionFind algorithm (Brute-force solution will take quadratic time, which is not scalableQuick video for huge systems).visualizing the entire process:
https://www.youtube.com/watch?v=xUWuZjadbbQ
Quick video for visualizing the entire process:
https://www.youtube.com/watch?v=xUWuZjadbbQ Source code for WeightedQuickUnionUF: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionUF.java.html

Tweeted twitter.com/StackCodeReview/status/780117706125283328

occurred Sep 25, 2016 at 18:52

added 167 characters in body

Source Link

edited Sep 25, 2016 at 14:13

user118482

In this problem I model a percolation system using an N-by-N grid of sites. Each site could be either open or blocked (all of them are blocked initially). To open the site, client should call open(row, col) method.
There is a notion of full site. "A full site is an open site that can be connected to an open site in the top row via a chain of neighboring (left, right, up, down) open sites [1]"
The system percolates, when there is a full site in the bottom row.

Now the goal is to perform efficient percolates() queries (boolean method that checks whether system percolates or not), using the UnionFind algorithm (Brute-force solution will take quadratic time, which is not scalable for huge systems).
Now the goal is to perform efficient percolates() queries (boolean method that checks whether system percolates or not), using the UnionFind algorithm (Brute-force solution will take quadratic time, which is not scalable for huge systems).