Coursera MOOC Algorithms, part I (Princeton University) week I

WEEK I Percolation
It's been two weeks since i began a MOOC in coursera.org entitled "Algorithms, part I" and I'm glad to post here the first programming assignment i had to do with the following score:

Compilation:  PASSED
Style:        FAILED
Findbugs:     No potential bugs found.
API:          PASSED

Correctness:  24/24 tests passed
Memory:       8/8 tests passed
Timing:       9/9 tests passed

Raw score: 100.00% [Correctness: 65%, Memory: 10%, Timing: 25%, Style: 0%]

In order to accomplish the assignment we had to use an algorithm called "union-find", more precisely an improvement of this algorithm that we previously studied through the lectures.

The goal of the problem was to calculate the Percolation Threshold of a system using Monte Carlo simulation. This threshold is known to be around 0.5927 for square sites and cannot be analytically determined.

We repeated T times the following experiment and then calculated the mean:

We set a grid of NxN sites and we randomly open sites til there is a path connecting the top row with the bottom row, when this happens the system is said to "percolate". We then divide the number of opened sites by the number of total sites in the grid (NxN) this gives us a value for the threshold.

The evaluation of this threshold is very important because it determines the minimum percentage of sites that need to be opened for us to expect a system that percolates.

BACKWASH Problem

This is a problem that arose from the first implementations when using a 2d visualizer class provided by the staff of the course and is due to the fact that i was using a virtual bottom node that caused some bottom sites to be full when there was no path connecting them to top row sites.

In the following video you can see the final result with the backwash problem solved:

Note: "Percolation" can be translated in Spanish as "filtrado" or "goteo".