Percolation threshold of a system

Assignment 3 (Percolation)

Goal: Write programs to estimate the percolation threshold of a system, which is a measure of how porous the system needsbe so that it percolates.

Part I: Warmup Problems The problems in this part of the assignment are intended to give you solid practice on concepts (using and defining datatypes) needed to solve the problems in Part II.

Problem 1. (Die Data Type) Implement a data type calledDiethat represents a six-sided die and supports the following

API:² DieDie()constructs a die with the face value -1

Problem 2. (Location Data Type) Implement a data type calledLocationthat represents a location on Earth and supportsthe following API:² LocationLocation(String name, double lat, double lon)constructs a new location given its name, latitude, and longitudedouble distanceTo(Location other)returns the great-circle distance† between this location andotherboolean equals(Object other)returnstrueif the latitude and longitude of this location are the same as thoseofother, anfalseotherwiseString toString()returns a string representation of this location

† See Problem 3 of Assignment 1 for formula.

& ~/workspace/percolation

✩ javac -d out src / Location . java

✩ java Location

x = Paris (48.51 , -2.17)

y = Boston (42.36 , -71.05)

5224. distanceTo (y) = 5224.780334245809
5225. equals (y) = falseProblem 3. (Rational Data Type) Implement an immutable data type calledRationalthat represents a rational number, ie,a number of the form a/b where a and b = 0 are integers. The data type must support the following API:

1 / 7Assignment 3 (Percolation) ² Rational

Rational(long x)constructs a rational number whose numerator isxand denominator is 1Rational(long x, long y)constructs a rational number given its numeratorxanddenominatory(†)Rational add(Rational other)returns the sum of this rational number andotherRational multiply(Rational other)returns the product of this rational number andotheboolean equals(Object other)returnsrueif this rational number is equal toother, andfalse otherwiseString toString()returns a string representation of this rational number† Use the private functiongcd()o 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/percolation

✩ javac -d out src / Rational . java

✩ java Rational 101 + 1/2 + 1/4 + ... + 1/2^10 = 1023/512

Problem 4. (Harmonic Number ) Write a program calledHarmonic.javathat accepts n (int) as command-line argument,computes the nth harmonic number Hn as arational number (using theRationaldata type from the previous problem), andwrites the value to standard output. Recall that Hn is defined as

7381/2520

Part II: Percolation

Percolation: Given a composite system comprising of randomly distributed insulating and metallic materials: what fractionof the system needs to be metallic so thatthe composite system is an electrical conductor? Given a porous landscape withwater on the surface (or oil below), under what conditions will the water be able to drain through to the bottom (or the oilto 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 × n grid of sites. Each site is either open or blocked. A full site isan 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 opensites connected to the top row and that process fills some open site on the bottom row. For the insulating/metallic materialsexample, the open sites correspond to metallic materials, so that a 代 写Percolation  threshold of a system system that percolates has a metallic path from top tobottom, with full sites conducting. For the porous substance example, the open sites correspond to empty space throughwhich water might flow, so that a system that percolates lets water fill open sites, flowing from top to bottom.

2 / 7Assignment 3 (Percolation)

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, thesystem percolates. The plots below show the site vacancy probability p versus the percolation probability for 20 ×20 randomgrid (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 neverpercolates,

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 ⋆ .

Problem 5. (Percolation Data Type) Develop a data type called

❼ Percolation() should throw anIllegalArgumentException("Illegal n")if n ≤ 0.

❼ open(),isOpen(), andsFull()should throw anIndexOutOfBoundsException("Illegal i or j")f i or j is outside the interval [0, n−1].Performance requirements:

❼ Percolation() should run in time T(n) ∼ n 2 .

❼ isOpen() andnumberOfOpenSites()should run in time T(n) ∼ 1.

❼ open(),isFull(, andpercolates()should run in time T(n) ∼ log n.& ~/workspace/percolation

✩ javac -d out src / Percolation . java

✩ java Percolation data / input10 . txt10 x 10 system :

Open sites = 56Percolates = true✩ java Percolation data / input10 - no . txt10 x 10 system :

3 / 7Assignment 3 (Percolation) Open sites = 55Percolates = false

Problem 6. (Estimation of Percolation Threshold) To estimate the percolation threshold, consider the following computa

ional (Monte Carlo simulation) experiment:

❼ Create an n × n percolation system (use thePercolationimplementation) 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 percolationhreshold 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 threshold. Let x1, x2, . . . , xm be the fractions of open sites in computational experiments 1, 2, . . . , m. The samplemean µ provides an estimate of the percolation threshold, and the sample standard deviation σ measures the sharpness ofthe threshold:µ =x1 + x2 + · · · + xm

. Assuming m is sufficiently large (say, at least 30), the following interval provides a 95% confidence interval for the percolationthreshold:

h µ − 1 √ .96 m σ , µ + 1 √ .96 m σ i . To perform a series of computational experiments, create an immutable data type called

PercolationStats

that supports thefollowing API:² PercolationStatsPercolationStats(int n, int m)erformsmindependent experiments on ann x npercolation systemdouble mean()

returns sample mean of percolation thresholddouble stddev()returns sample standard deviation of percolation threshold

double confidenceLow()returns low endpoint of 95% confidence intervaldouble confidenceHigh()returns high endpoint of 95% confidence intervalThe constructor should perform m independent computational experiments (discussed above) on an n × n grid. Using thisexperimental data, it should calculate the mean, standard deviation, and the 95% confidence interval for the percolationthreshold.Corner cases:

4 / 7Assignment 3 (Percolation)

❼ The constructor should throw anllegalArgumentException("Illegal n or m")f either n ≤ 0 or m ≤ 0.Performance requirements:

❼ PercolationStats() should run in time T(n, m) ∼ mn2 .

❼ mean(),

stddev(),confidenceLow(), andconfidenceHigh()should run in time T(n, m) ∼ m.

& ~/workspace/percolation

✩ javac -d out src / PercolationStats . java

✩ java PercolationStats 100 1000

Percolation threshold for a 100 x 100 system :Mean = 0.592Standard deviation = 0.016Confidence interval = [0.591 , 0.593]

Data: Thedatadirectory contains some input (.txt) files for the percolation programs. The first number specifies the size ofthe percolation system and the pairs of numbers that follow specify the sites to open. Associated with each file is an output(.png

) file that shows the desired output. For example, here is an input file:

& ~/workspace/percolation

✩ cat data / input10 . txt109 11 9...7 9and here is the corresponding output file:

& ~/workspace/percolation

✩ display data / input10 . png

Visualization Programs: The programPercolationVisualizeraccepts f ilename (String) as command-line argument andvisually reports if the system represented by the input file percolates or not.

& ~/workspace/percolation

✩ javac -d out src / PercolationVisualizer . java

✩ java PercolationVisualizer data / input10 . txt

5 / 7Assignment 3 (Percolation)

The programInteractivePercolationVisualizeraccepts n (int) as command-line argument, constructs an n×n percolation system,and allows you to interactively open sites in the system by clicking on them and visually inspect if the system percolates ornot.

& ~/workspace/percolation

✩ javac -d out src / InteractivePercolationVisualizer . java

✩ java InteractivePercolationVisualizer 3

Files to Submit:

6 / 7Assignment 3 (Percolation) Before you submit your files, make sure:

❼ You do not use concepts from sections beyond Defining Data Types.

❼ Your code follows good programming principles (ie, it is clean and well-organized; uses meaningful variable names;and includes useful comments).

❼ You edit the sections (#1mandatory,#2

f applicable, and#3optional) in the givennotes.txtfile as appropriate. Insection#1, for each problem, you must include in nore more than 100 words: a short, high-level description of theproblem; your approach to solve it; and any issues youencountered and if/how you managed to solve them.Acknowledgement: Part II of this assignment is an adaptation of the Percolation assignment developed at PrincetonUniversity by Robert Sedgewick and KevinWayne.7 /