This repository contains my solutions for the online courses "Algorithms, Part I" and "Algorithms, Part II" from Princeton University.
Coursera:
Text:
Algorithms, 4th ed., by Robert Sedgewick and Kevin Wayne
Part I, Week 1: Percolation
"Percolation" calculates whether we can traverse through adjacent open sites to get from the top of the lattice to the bottom. As an analogy, I like to think of water being poured over a lattice containing sites that are either open (holes!) or closed. The question now is whether the water percolate through the lattice...
The percolation problem implements the Union-Find, or Disjoint-Set, data structure, which simulates set partitioning. Union Find uses an array id[] to append an id to each index; if the two elements corresponding to indexes a and b are such that id[a] = id[b], then the two elements are in the same equivalence class.
The time complexity of normal Union-Find, which I found most intuitive, is O(n). With optimizations, Sedgewick and Wayne's WeightedQuickUnionUF takes O(n) to construct and O(log n) to merge equivalence classes and find the representative element of a set.
Finally, the "Percolation" class is used to empirically estimate the value of the percolation threshold for a square lattice. By running a Monte Carlo simulation and randomly opening sites, as shown below, we experimentally estimate when a lattice transitions from non-percolating to percolating state.
When I was working on this project two years ago, I ran into some issues (now fixed!) with backwashing.
In cases where a Percolation object does percolate, some sites that aren't connected appear to be connected because the we union() sites at the top of the lattice to sites at the bottom of the lattice as a part of implementing Union-Find.
For example, running PercolationVisualizer.java on input10.txt results in the solution to the right rather than the solution to the left (this is mentioned in the FAQ!).
The solution I implemented simply uses two Union-Find objects. Doing this seems to satisfy the Coursera autograder, but it's also pretty costly in terms of memory. I'd be interested in hearing about any other solutions out there!