Percolation

The main objective of this project is to calculate the percolation treshold via Monte Carlo simulation

Percolation is the process of modeling a situation where we have, for example, a composite
system comprised of randomly distributed insulating and metallic materials and we wanted to
know what fraction of the materials need to be metallic so that the composite system is an
electrical conductor.
You can find more information about the concept of Percolation in this scientific article.

Monte Carlo Simulation is a computerized mathematical technique to generate random sample
data based on some known distribution for numerical experiments. Reference.

Main Challenges

As described earlier, the main objective of this project is to calculate the percolation threshold and for this
I made use of the Monte Carlo method. But the main challenge is not directly using this method, instead, it was how
to model the percolation system and execute the simulations from a computational efficient perspective.
Achieving this efficiency was possible thanks to the Union-Find Data Structure as well as the mathematical
relation that I came up to to translate a matrix element's position to an array position.

Solving the main challenges

The mathematical relation mentioned in the previous section is described as follow:

$$ArrayPosition = ((R(M_{i,j}) - 1) * n ) + C(M_{i,j}) - 1$$

Where $R(M_{i,j})$ is a matrix row element; $n$ is the grid size; and $C(M_{i,j})$ is a matrix column element

Obs.: I did not formally proved this relation, but it worked for all test cases that it was submitted to

Example

The following image shows a matrix with a $n = 4$, so the matrix size is 4x4. For the element $M_{3,4}$ ,for example,
we have a mapping to an array position of 11

Union-find Data structure

The Union-find data structure is used to solve the problem of dynamic connectivity. This data structure is capable of, given a set of integers, and given that we can connect pairs in this set, union find is capable of "remembering" these connections, as well as connecting pairs and efficiently verifying if a element p is connected to a element q in a set. Applied to the percolation problem, we use this data structure to model the connections among the sites. One of the main challenges were to know when do a simulation percolates, and to address this issue, it was used the concept of "virtual top" and "virtual bottom"

As we can see in the image above, the virtual top is connected to the first row of the matrix. Similarly, the virtual bottom is connected to the last row of the matrix. We say that a system percolates if any element in the virtual top is connected to any element in the virtual bottom.

Joining concepts

Using the matrix as the basis for the percolation system; a method for translating elements in the matrix to a an array position; and the union find that, at its core, uses an array to do the operations needed, we have the complete set of concepts and solutions that were used to solve the percolation problem.

How to run this project

To run these programs you need to have Java installed and configured (version >= 5.0) as well as add algs4.jar
to the classpath.
The main class to run is the Percolation Stats.java, where it receives two arguments:
n - The size of the grid
T - The number of trials. By repeating this computation experiment T times and averaging the results, we obtain a more accurate estimate of the percolation threshold

Observation

1 -The use of this code (or any modification of it) to solve the same assignment results in a direct infringement of cousera's Honor Code.

2 - The assessment score was 91/100. The main issues remaining to solve for this algorithm are some corner cases and the backwash problem.