Percolation. Given a composite system comprised of randomly distributed insulating and metallic materials: what fraction of the materials need to be metallic so that the composite system is an electrical conductor? Given a porous landscape with water on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oil to gush through to the surface)? Scientists have defined an abstract process known as percolation to model such situations.
The model. We model a percolation system using an N-by-N grid of sites. Each site is either open or blocked. 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. We say the system percolates if there is a full site in the bottom row. In other words, a system percolates if we fill all open sites connected to the top row and that process fills some open site on the bottom row. (For the insulating/metallic materials example, the open sites correspond to metallic materials, so that a system that percolates has a metallic path from top to bottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space through which water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.)
The problem. In a famous scientific problem, researchers are interested in the following question: if sites are independently set to be open with probability p (and therefore blocked with probability 1 − p), what is the probability that the system percolates? When p equals 0, the system does not percolate; when p equals1, the system percolates. The plots below show the site vacancy probability p versus the percolation probability for 20-by-20 random grid (left) and 100-by-100 random grid (right).
When N is sufficiently large, there is a threshold value p* such that when p < p* a random N-by-N grid almost never percolates, and when p > p*, a random N-by-N grid almost always percolates. No mathematical solution for determining the percolation threshold p* has yet been derived. Your task is to write a program to:
PercolationVisualizer should prompt the user for N and display the
percolation process starting with a N-by-N grid of sites
(initially all blocked and black). After
each site is opened, display full sites in cyan,
open sites (that aren't full) in white, and blocked sites in black using princeton.StdDraw.
Here is an example of steps in a visualization on a 20x20 grid as in
this movie and the following
snapshots.
| 
| 
| 
| 
|
IPercolate interface.
public interface IPercolate {
public abstract void open(int i, int j); // open site (row i, col j) if it is not already
public abstract boolean isOpen(int i, int j); // is site (row i, col j) open?
public abstract boolean isFull(int i, int j); // is site (row i, col j) full?
public abstract boolean percolates(); // Returns true iff open path from to bottom
}
You will complete brute-force (PercolationDFS) and union-find
(PercolationUF) versions
of the IPercolate data type. By convention, the indices
i and j
are integers between 1 and N, where (1, 1) is the upper-left cell:
To obtain an accurate estimate of the percolation threshold, repeat the experiment T times and average the results. Let xt be the fraction of open sites in experiment t. The sample mean μ provides an estimate of the percolation threshold. The sample standard deviation σ measures the sharpness of the threshold.
Assuming T is sufficiently large (say, at least 30), the following provides a 95% confidence interval for the percolation threshold:
Write a client program
PercolationStats that prompts the user for N and T,
performs T independent experiments on an N-by-N grid,
and prints out the 95% confidence interval for the percolation threshold.
Use java.util.Random to generate random numbers and follow steps above to compute the sample mean and standard deviation.
Below is an example run with N=200 and T=100.
mean percolation threshold = 0.5920965000000004 stddev = 0.009811413646870666 95% confidence interval = [0.5901734629252137, 0.594019537074787] total time = 2.074 mean time per experiment = 0.02073999999999999 stddev = 0.0037646248153036512
QuickFind.java) and by creating a version using the
weighted quick union with path compression data structure (WeightedQuickUnionUF.java).
In your README, you will answer the following questions.
System.currentTimeMillis) of the 3 versions of your program (DFS, Quick Find, and weighted quick union with path compression).
PercolationVisualizer,
PercolationDFS, and PercolationUF. Your
implementation of PercolationStats and the subsequent
analysis will determine your analysis points. Proper code
decomposition, formatting, and documentation earns your
engineering points.