Project 1 (Percolation)

Project 1 (Percolation)
Exercises
Exercise 1. (Great Circle Distance) Write a program called GreatCircle.java that accepts x1 (double), y1 (double), x2 (double),
and y2 (double) as command-line arguments representing the latitude and longitude (in degrees) of two points on earth, and
writes to standard output the great-circle distance (in km) between the two points, given by the formula
d = 6359.83 arccos(sin(x1) sin(x2) + cos(x1) cos(x2) cos(y1 − y2)).
& ~/workspace/project1
$ java GreatCircle 48.87 -2.33 37.8 -122.4
8701.387455462233
Exercise 2. (Counting Primes) Implement the static method isPrime() in PrimeCounter.java that accepts an integer x and returns
true if x is prime and false otherwise. Also implement the static method primes() that accepts an integer n and returns the
number of primes less than or equal to n — a number x is prime if it is not divisible by any number i ∈ [2,
√
x].
& ~/workspace/project1
$ java PrimeCounter 1000
168
Exercise 3. (Euclidean Distance) Implement the static method distance() in Distance.java that accepts position vectors x and
y — each represented as a 1D array of doubles — and returns the Euclidean distance between the two vectors, calculated as
the square root of the sums of the squares of the differences between the corresponding entries.
& ~/workspace/project1
$ java Distance
5
-9 1 10 -1 1
5
-5 9 6 7 4
13.0
Exercise 4. (Matrix Transpose) Implement the static method tranpose() in Transpose.java that accepts a matrix x — represented
as a 2D array of doubles — and returns a new matrix that is the transpose of x.
& ~/workspace/project1
$ Transpose
3 3
1 2 3
4 5 6
7 8 9
3 3
1.00000 4.00000 7.00000
2.00000 5.00000 8.00000
3.00000 6.00000 9.00000
Exercise 5. (Rational Number ) Implement an immutable data type called Rational that represents a rational number, ie, a
number of the form a/b where a and b 6= 0 are integers. The data type must support the following API:
1 / 10
Project 1 (Percolation)
² Rational
Rational(long x) constructs a rational number whose numerator is x and denominator is 1
Rational(long x, long y) constructs a rational number given its numerator x and denominator y (†)
Rational add(Rational other) returns the sum of this rational number and other
Rational multiply(Rational other) returns the product of this rational number and other
boolean equals(Object other) returns true if this rational number is equal to other, and false otherwise
String toString() returns a string representation of this rational number
† Use the private method gcd() to ensure that the numerator and denominator never have any common factors. For example,
the rational number 2/4 must be represented as 1/2.
& ~/workspace/project1
$ java Rational 10
a = 1 + 1/2 + 1/4 + ... + 1/2^10 = 1023/512
b = (2^10 - 1) / 2^(10 - 1) = 1023/512
a. equals (b) = true
Exercise 6. (Harmonic Number ) Write a program called Harmonic.java that accepts n (int) as command-line argument,
computes the nth harmonic number Hn as a rational number, and writes the value to standard output.
Hn = 1 +
1
2
+
1
3
+ · · · +
1
n − 1
+
1
n
.
& ~/workspace/project1
$ java Harmonic 5
137/60
2 / 10
Project 1 (Percolation)
Problems
Goal Write a program to estimate the percolation threshold of a system.
Percolation Given a composite system comprising of randomly distributed insulating and metallic materials: what fraction
of the system needs 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 nxn 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 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 equals 1, the
system percolates. The plots below show the site vacancy probability p versus the percolation probability for 20 ×20 random
grid (left) and 100 × 100 random grid (right).
When n is sufficiently large, there is a threshold value p
?
such that when p < p? a random n×n grid almost never percolates,
and when p > p?
, a random n × n grid almost always percolates. No mathematical solution for determining the percolation
threshold p
? has yet been derived. Your task is to write a computer program to estimate p
?
.
Percolation API To model a percolation system, we define an interface called Percolation, supporting the following API:
3 / 10
Project 1 (Percolation)
² Percolation
void open(int i, int j) opens site (i, j) if it is not already open
boolean isOpen(int i, int j) returns true if site (i, j) is open, and false otherwise
boolean isFull(int i, int j) returns true if site (i, j) is full, and false otherwise
int numberOfOpenSites() returns the number of open sites
boolean percolates() returns true if this system percolates, and false otherwise
Problem 1. (Array Percolation) Develop a data type called ArrayPercolation that implements the Percolation interface using a
2D array as the underlying data structure.
² ArrayPercolation implements Percolation
ArrayPercolation(int n) constructs an n x n percolation system, with all sites blocked
Corner cases:
ˆ ArrayPercolation() should throw an IllegalArgumentException("Illegal n") if n ≤ 0.
ˆ open(), isOpen(), and isFull() should throw an IndexOutOfBoundsException("Illegal i or j") if i or j is outside the interval [0, n−1].
Performance requirements:
ˆ open(), isOpen(), and numberOfOpenSites() should run in time T(n) ∼ 1.
ˆ percolates() should run in time T(n) ∼ n.
ˆ ArrayPercolation() and isFull() should run in time T(n) ∼ n
2
.
& ~/workspace/project1
$ java ArrayPercolation data / input10 . txt
10 x 10 system :
Open sites = 56
Percolates = true
$ java ArrayPercolation data / input10 - no . txt
10 x 10 system :
Open sites = 55
Percolates = false
Directions:
ˆ Instance variables:
– Percolation system size, int n.
– Percolation system, boolean[][] open (true =⇒ open site and false =⇒ blocked site).
– Number of open sites, int openSites.
ˆ private void floodFill(boolean[][] full, int i, int j)
– Return if i or j is out of bounds; or site (i, j) is not open; or site (i, j) is full (ie, full[i][j] is true).
– Fill site (i, j).
– Call floodFill() recursively on the sites to the north, east, west, and south of site (i, j).
ˆ public ArrayPercolation(int n)
– Initialize instance variables.
ˆ void open(int i, int j)
– If site (i, j) is not open:
* Open the site.
4 / 10
Project 1 (Percolation)
* Increment openSites by one.
ˆ boolean isOpen(int i, int j)
– Return whether site (i, j) is open or not.
ˆ boolean isFull(int i, int j)
– Create an n × n array of booleans called full.
– Call floodFill() on every site in the first row of the percolation system, passing full as the first argument.
– Return full[i][j].
ˆ int numberOfOpenSites()
– Return the number of open sites.
ˆ boolean percolates()
– Return whether the system percolates or not — a system percolates if the last row contains at least one full site.
Problem 2. (Union Find Percolation) Develop a data type called UFPercolation that implements the Percolation interface using
a WeightedQuickUnionUF object as the underlying data structure.
² UFPercolation implements Percolation
UFPercolation(int n) constructs an n x n percolation system, with all sites blocked
Corner cases:
ˆ UFPercolation() should throw an IllegalArgumentException("Illegal n") if n ≤ 0.
ˆ open(), isOpen(), and isFull() should throw an IndexOutOfBoundsException("Illegal i or j") if i or j is outside the interval [0, n−1].
Performance requirements:
ˆ isOpen() and numberOfOpenSites() should run in time T(n) ∼ 1.
ˆ open(), isFull(), and percolates() should run in time T(n) ∼ log n.
ˆ UFPercolation() should run in time T(n) ∼ n
2
.
& ~/workspace/project1
$ java UFPercolation data / input10 . txt
10 x 10 system :
Open sites = 56
Percolates = true
$ java UFPercolation data / input10 - no . txt
10 x 10 system :
Open sites = 55
Percolates = false
Directions:
ˆ Model percolation system as an n × n array of booleans (true =⇒ open site and false =⇒ blocked site).
ˆ Create an UF object with n
2 + 2 sites and use the private encode() method to translate sites (0, 0),(0, 1), . . . ,(n−1, n−1)
of the array to sites 1, 2, . . . , n2 of the UF object; sites 0 (source) and n
2 + 1 (sink) are virtual, ie, not part of the
percolation system.
5 / 10
Project 1 (Percolation)
ˆ A 3 × 3 percolation system and its UF representation
0, 0 0, 1 0, 2
1, 0 1, 1 1, 2
2, 0 2, 1 2, 2
0
1 2 3
4 5 6
7 8 9
10
ˆ Instance variables:
– Percolation system size, int n.
– Percolation system, boolean[][] open.
– Number of open sites, int openSites.
– Union-find representation of the percolation system, WeightedQuickUnionUF uf.
ˆ private int encode(int i, int j)
– Return the UF site (1, 2, . . . , n2
) corresponding to the percolation system site (i, j).
ˆ public UFPercolation(int n)
– Initialize instance variables.
ˆ void open(int i, int j)
– If site (i, j) is not open:
* Open the site
* Increment openSites by one.
* If the site is in the first (or last) row, connect the corresponding uf site with the source (or sink).
* If any of the neighbors to the north, east, west, and south of site (i, j) is open, connect the uf site corresponding
to site (i, j) with the uf site corresponding to that neighbor.
ˆ boolean isOpen(int i, int j)
– Return whether site (i, j) is open or not.
ˆ boolean isFull(int i, int j)
– Return whether site (i, j) is full or not — a site is full if it is open and its corresponding uf site is connected to
the source.
ˆ int numberOfOpenSites()
– Return the number of open sites.
ˆ boolean percolates()
– Return whether the system percolates or not — a system percolates if the sink is connected to the source.
ˆ Using virtual source and sink sites introduces what is called the back wash problem.
6 / 10
Project 1 (Percolation)
ˆ In the 3 × 3 system, consider opening the sites (0, 1), (1, 2),(1, 1), (2, 0), and (2, 2), and in that order; the system
percolates once (2, 2) is opened.
0, 0 0, 1 0, 2
1, 0 1, 1 1, 2
2, 0 2, 1 2, 2
0
1 2 3
4 5 6
7 8 9
10
ˆ The site (2, 0) is technically not full since it is not connected to an open site in the top row via a path of neighboring
(north, east, west, and south) open sites, but the corresponding uf site (7) is connected to the source, so is incorrectly
reported as being full — this is the back wash problem.
ˆ To receive full credit, you must resolve the back wash problem.
Problem 3. (Estimation of Percolation Threshold) To estimate the percolation threshold, consider the following computational (Monte Carlo simulation) experiment:
ˆ Create an n × n percolation system (use the UFPercolation implementation) with all sites blocked.
ˆ Repeat the following until the system percolates:
– Choose a site (row i, column j) uniformly at random among all blocked sites.
– Open the site (row i, column j).
ˆ The fraction of sites that are open when the system percolates provides an estimate of the percolation threshold.
For example, if sites are opened in a 20 × 20 grid according to the snapshots below, then our estimate of the percolation
threshold is 204/400 = 0.51 because the system percolates when the 204th site is opened.
By repeating this computational experiment m times and averaging the results, we obtain a more accurate estimate of the
percolation threshold. Let x1, x2, . . . , xm be the fractions of open sites in computational experiments 1, 2, . . . , m. The sample
mean µ provides an estimate of the percolation threshold, and the sample standard deviation σ measures the sharpness of
the threshold:
µ =
x1 + x2 + · · · + xm
m
, σ2 =
(x1 − µ)
2 + (x2 − µ)
2 + · · · + (xm − µ)
2
m − 1
.
Assuming m is sufficiently large (say, at least 30), the following interval provides a 95% confidence interval for the percolation
threshold:
h
µ −
1.96σ
√
m
, µ +
1.96σ
√
m
i
.
7 / 10
Project 1 (Percolation)
To perform a series of computational experiments, create an immutable data type called PercolationStats that supports the
following API:
² PercolationStats
PercolationStats(int n, int m) performs m independent experiments on an n x n percolation system
double mean() returns sample mean of percolation threshold
double stddev() returns sample standard deviation of percolation threshold
double confidenceLow() returns low endpoint of 95% confidence interval
double confidenceHigh() returns high endpoint of 95% confidence interval
The constructor perform m independent computational experiments (discussed above) on an n × n grid. Using this experimental data, it should calculate the mean, standard deviation, and the 95% confidence interval for the percolation threshold.
Corner cases:
ˆ The constructor should throw an IllegalArgumentException("Illegal n or m") if either n ≤ 0 or m ≤ 0.
Performance requirements:
ˆ mean(), stddev(), confidenceLow(), and confidenceHigh() should run in time T(n, m) ∼ m.
ˆ PercolationStats() should run in time T(n, m) ∼ mn2
.
& ~/workspace/project1
$ java PercolationStats 100 1000
Percolation threshold for a 100 x 100 system :
Mean = 0.592
Standard deviation = 0.016
Confidence interval = [0.591 , 0.594]
Directions:
ˆ Instance variables:
– Number of independent experiments, int m.
– Percolation thresholds for the m experiments, double[] x.
ˆ PercolationStats(int n, int m)
– Initialize instance variables.
– Perform the following experiment m times:
* Create an n × n percolation system (use the UFPercolation implementation).
* Until the system percolates, choose a site (i, j) at random and open it if it is not already open.
* Calculate percolation threshold as the fraction of sites opened, and store the value in x[].
ˆ double mean()
– Return the mean µ of the values in x[].
ˆ double stddev()
– Return the standard deviation σ of the values in x[].
ˆ double confidenceLow()
– Return µ −
1
√.96σ
m
.
ˆ double confidenceHigh()
– Return µ +
1
√.96σ
m
.
Data The data directory contains some input .txt files for the percolation visualization programs, and associated with each
file is an output .png file that shows the desired output. For example
8 / 10
Project 1 (Percolation)
& ~/workspace/project1
$ cat data / input10 . txt
10
9 1
1 9
...
7 9
The first number specifies the size of the percolation system and the pairs of numbers that follow specify the sites to open.
& ~/workspace/project1
$ display data / input10 . png
Visualization Programs The program PercolationVisualizer accepts mode (the String “array” or “UF”) and f ilename (String)
as command-line arguments, and uses ArrayPercolation or UFPercolation to determine and visually report if the system represented
by the input file percolates or not.
& ~/workspace/project1
$ java PercolationVisualizer UF data / input10 . txt
The program InteractivePercolationVisualizer accepts mode (“array” or “UF”) and n (int) as command-line arguments, constructs
an n × n percolation system using ArrayPercolation or UFPercolation, and allows you to interactively open sites in the system by
clicking on them and visually inspect if the system percolates or not.
& ~/workspace/project1
$ java InteractivePercolationVisualizer UF 3
3
0 1
9 / 10
Project 1 (Percolation)
1 2
1 1
2 0
2 2

Files to Submit
1. GreatCircle.java
2. PrimeCounter.java
3. Distance.java
4. Transpose.java
5. Rational.java
6. Harmonic.java
7. ArrayPercolation.java
8. UFPercolation.java
9. PercolationStats.java
10. report.txt
Before you submit your files, make sure:
ˆ Your programs meet the style requirements by running the following command in the terminal.
& ~/workspace/project1
$ check_style src /*. java
ˆ Your code is adequately commented, follows good programming principles, and meets any specific requirements
such as corner cases and running times.
ˆ You use the template file report.txt for your report.
ˆ Your report meets the prescribed guidelines.
10 / 10