Programming Assignment 1: Percolation
The page of assignment is following:
http://coursera.cs.princeton.edu/algs4/assignments/percolation.html
Answer
This homework need us to make two different class.
The first one called Percolation, including five main functions, which are used to operate on the N-by-N grid.
And the second class called PercolationStats, which is ued to estimate 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.
The first class
The assignment offers official API as following:
|
1 2 3 4 5 6 7 8 9 10 11 |
public class Percolation { public Percolation(int N) // create N-by-N grid, with all sites blocked public void open(int i, int j) // open site (row i, column j) if it is not open already public boolean isOpen(int i, int j) // is site (row i, column j) open? public boolean isFull(int i, int j) // is site (row i, column j) full? public boolean percolates() // does the system percolate? public static void main(String[] args // test client (optional) } |
Because of the courses we have taken this week, we can confirm that we should use Quick-Find and Quick-Union to solve it.
The assignment offers us a method that we can add another blank layer both on the top of the sites and the bottom of it, so that we can only judge if (0,1) and (N+1,1) is united.
Notes:
1. we need to change the array[i][j] to the array[i*N+j], whcih is easier to calculate and use quick-find and quick-union straightly.
2. The question mentioned a problom called “backwash”
I use a new array without the bottom of the sites, and using function isFull() to check if the site is really connected with the top site.
So the first class code is following:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 |
public class Percolation { private WeightedQuickUnionUF uf; private WeightedQuickUnionUF uf_backwash; private int N; //private int count_n=0;//record the number of open site; private boolean[] ifopen;//an array record if the site is open; public Percolation(int N) { if (N<=0) throw new IllegalArgumentException("N is<=0"); this.N = N; int i; uf=new WeightedQuickUnionUF((N+1)*(N)+N+1); uf_backwash=new WeightedQuickUnionUF(N*N+N+1); ifopen=new boolean[(N+1)*(N)+N+1]; for(i=1;i<=N;i++){ uf.union(0*N+1, 0*N+i); uf_backwash.union(0*N+1, 0*N+i); ifopen[0*N+i]=true; uf.union((N+1)*N+1, (N+1)*N+i); ifopen[(N+1)*N+i] = true; } }// create N-by-N grid, with all sites blocked public void open(int i, int j){ if (i<1||i>N) throw new IndexOutOfBoundsException("row index i out of bounds"); if(j<1||j>N) throw new IndexOutOfBoundsException("column index j out of bounds"); if(ifopen[i*N+j]) return; ifopen[i*N+j]=true; //count_n++; if (ifopen[(i-1)*N+j]){ uf.union(i*N+j, (i-1)*N+j); uf_backwash.union(i*N+j, (i-1)*N+j); } if (ifopen[(i+1)*N+j]){ uf.union(i*N+j, (i+1)*N+j); if (i!=N){ uf_backwash.union(i*N+j, (i+1)*N+j); } } if (j!=1 && ifopen[i*N+j-1]){ uf.union(i*N+j, i*N+j-1); uf_backwash.union(i*N+j, i*N+j-1); } if (j!=N && ifopen[i*N+j+1]){ uf.union(i*N+j, i*N+j+1); uf_backwash.union(i*N+j, i*N+j+1); } }// open site (row i, column j) if it is not already public boolean isOpen(int i, int j){ if (i<1||i>N) throw new IndexOutOfBoundsException("row index i out of bounds"); if(j<1||j>N) throw new IndexOutOfBoundsException("column index j out of bounds"); return ifopen[i*N+j]; }// is site (row i, column j) open? public boolean isFull(int i, int j){ if (i<1||i>N) throw new IndexOutOfBoundsException("row index i out of bounds"); if(j<1||j>N) throw new IndexOutOfBoundsException("column index j out of bounds"); return uf_backwash.connected(i*N+j, 0*N+1) && ifopen[i*N+j]; } // is site (row i, column j) full? public boolean percolates() { return uf.connected(0*N+1, (N+1)*N+1); }// does the system percolate? public static void main(String[] args){ int N = StdIn.readInt(); Percolation pe=new Percolation(N); pe.open(1, 1); pe.open(2, 1); System.out.println(pe.percolates()); }// test client, optional } |
The second class
|
1 2 3 4 5 6 7 8 9 10 11 |
public class PercolationStats { public PercolationStats(int N, int T) // perform T independent experiments on an N-by-N grid public double mean() // sample mean of percolation threshold public double stddev() // sample standard deviation of percolation threshold public double confidenceLo() // low endpoint of 95% confidence interval public double confidenceHi() // high endpoint of 95% confidence interval public static void main(String[] args) // test client (described below) } |
This class is used to calculate the statistical probability.
1.Initialize a N*N grid and all sites are closed.
2.Everytime making a site open randomly until the sites are in Percolation.
3.Record the vaule p=open sites number/all sites number.
4.Repeat N to get the final sample average
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 |
public class PercolationStats { private double staT[]; private double sta_mean; private double sta_stddev; private int N; public PercolationStats(int N, int T){ staT=new double[T]; this.N=N; int times=0; if(N<=0) throw new IllegalArgumentException(); if(T<=0) throw new IllegalArgumentException(); while(times<T){ Percolation pe=new Percolation(N); int count=0; while(true){ count++; while(true){ int x = StdRandom.uniform(N) + 1; int y = StdRandom.uniform(N) + 1; if(pe.isOpen(x, y)){ continue; }else{ pe.open(x, y); break; } } if(pe.percolates()){ staT[times]=(double)count/((double)N*(double)N); break; } } times++; } this.sta_mean = StdStats.mean(staT); this.sta_stddev = StdStats.stddev(staT); }// perform T independent computational experiments on an N-by-N grid public double mean(){ return this.sta_mean; }// sample mean of percolation threshold public double stddev(){ return this.sta_stddev; } // sample standard deviation of percolation threshold public double confidenceLo(){ return this.sta_mean-1.96*this.sta_stddev/Math.sqrt(N); }// returns lower bound of the 95% confidence interval public double confidenceHi(){ return this.sta_mean+1.96*this.sta_stddev/Math.sqrt(N); } // returns upper bound of the 95% confidence interval public static void main(String[] args){ int N = StdIn.readInt(); int T = StdIn.readInt(); PercolationStats percolationStats = new PercolationStats(N, T); StdOut.println("mean = " + percolationStats.mean()); StdOut.println("stddev = " + percolationStats.stddev()); StdOut.println("95% confidence interval " + percolationStats.confidenceLo() + ", " + percolationStats.confidenceHi()); } // test client, described below } |