Programming Assignment 1: Percolation Algorithms, Part I Princeton University Write a program to estimate the value of the percolation threshold via Monte Carlo simulation. Assignment specification The whole assignment is just to write an instance to apply the weighted quick union algorithm to solve some percolation problem. It's strange that the assignment focus more on the application process rather than the algorithm itself. All core code to realize the algorithm has already been packaged and all one need to do is to import and call it. Seems ridiculous. Anyway, I'll take this as a chance of learning Java. Gonna just google some code and see what others do with this ridiculous assignment.

Percolation.java

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;
import edu.princeton.cs.algs4.WeightedQuickUnionUF;

public class Percolation {
    private int matrixOrder;
    private boolean[] matrix; 
    private WeightedQuickUnionUF wqu; // 申
    private WeightedQuickUnionUF wqu2; // 由
    private int openCount;

    // create n-by-n grid, with all sites blocked
    public Percolation(int n){
        matrixOrder = n;
        matrix = new boolean[matrixOrder*matrixOrder];
        wqu = new WeightedQuickUnionUF(matrixOrder*matrixOrder + 1);
        wqu2 = new WeightedQuickUnionUF(matrixOrder*matrixOrder);
    }

    // check if in range
    private void validate(int row, int col) {
        if (row < 1 || row > matrixOrder){
            throw new IndexOutOfBoundsException("row index out of bounds");
        }
        if (col < 1 || col > matrixOrder){
            throw new IndexOutOfBoundsException("col index out of bounds");
        }

    }

    // map coordinates
    private int no(int row, int col) {
        return (row - 1) * matrixOrder + col - 1;
    }

    // open site (row, col) if it is not open already
    public  void open(int row, int col){
        validate(row, col);
        int self = no(row,col);
        if (matrix[self]) {
            return;
        }
        openCount++;
        matrix[self] = true;

        //top
        if (row == 1){
            wqu.union(self,0);
            wqu2.union(self,0);
        }
        //bottom
        if (row == matrixOrder){
            wqu.union(self,matrixOrder*matrixOrder);
        }

        //surround
        //up
        int next;
        if (row > 1) { 
            next = no(row - 1, col);
            if (matrix[next]) {
                wqu.union(self, next);
                wqu2.union(self, next);
            }
        }
        //down
        if (row < matrixOrder) {
            next = no(row + 1, col);
            if (matrix[next]) {
                wqu.union(self, next);
                wqu2.union(self, next);
            }
        }
        //left
        if (col > 1) {
            next = no(row, col - 1);
            if (matrix[next]) {
                wqu.union(self, next);
                wqu2.union(self, next);
            }
        }
        //right
        if (col < matrixOrder) {
            next = no(row, col + 1);
            if (matrix[next]) {
                wqu.union(self, next);
                wqu2.union(self, next);
            }
        }
    }

    // is site (row, col) open?
    public boolean isOpen(int row, int col){
        validate(row, col);
        return matrix[no(row, col)];
    }

    // is site (row, col) full?
    public boolean isFull(int row, int col){
        validate(row, col);
        return wqu2.connected(0, no(row, col));
    }

    // number of open sites
    public   int numberOfOpenSites(){
        return openCount;
    }

    // does the system percolate?
    public boolean percolates(){
        return wqu.connected(0, matrixOrder*matrixOrder);
    }

    // test client (optional)
    public static void main(String[] args){
        int n = StdIn.readInt();
        Percolation percolation = new Percolation(n);
        try {
            while (!StdIn.isEmpty()) {
                int row = StdIn.readInt();
                int col = StdIn.readInt();
                percolation.open(row, col);
            }
        } catch (Exception e) {
        }


        StdOut.println("percolation is " + percolation.percolates());
    }
}

PercolationStats.java

import edu.princeton.cs.algs4.StdRandom;
import edu.princeton.cs.algs4.StdStats;
import edu.princeton.cs.algs4.StdOut;

public class PercolationStats {
    private int matrixOrder;
    private double[] trailsResult;
    private double resultMean;
    private double resultStddev;
    private double resultConfidenceLo;
    private double resultConfidenceHi;


    // perform trials independent experiments on an n-by-n grid
    public PercolationStats(int n, int trials)  {
        matrixOrder = n;
        if (matrixOrder == 1) {
            resultMean = 1;
            resultStddev = Double.NaN;
            resultConfidenceLo = Double.NaN;
            resultConfidenceHi = Double.NaN;
        }
        else {
            trailsResult = new double[trials];
            for (int i = 0; i < trials; i++) {
                trailsResult[i] = oneTrial(matrixOrder);
            }
            resultMean = StdStats.mean(trailsResult);
            resultStddev = StdStats.stddev(trailsResult);
            double diff = (1.96 * resultStddev) / Math.sqrt(trials);
            resultConfidenceLo = resultMean - diff;
            resultConfidenceHi = resultMean + diff;
        }
    }

    private double oneTrial(int n) {
        int openCount = 0;
        Percolation percolation = new Percolation(n);
        while (!percolation.percolates()) {
            int row = StdRandom.uniform(n) + 1;
            int col = StdRandom.uniform(n) + 1;
            if (!percolation.isOpen(row, col)) {
                percolation.open(row, col);
                openCount++;
            }
        }
        return (double) openCount / (n * n);
    }

    // sample mean of percolation threshold
    public double mean() {
        return resultMean;
    }
    // sample standard deviation of percolation threshold
    public double stddev() {
        return resultStddev;
    }
    // low  endpoint of 95% confidence interval
    public double confidenceLo() {
        return resultConfidenceLo;
    }
    // high endpoint of 95% confidence interval
    public double confidenceHi() {
        return resultConfidenceHi;
    }

    // test client (described below)
    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int trials = Integer.parseInt(args[1]);
        PercolationStats percolations = new PercolationStats(n, trials);
        StdOut.println("mean                    = " + percolations.mean());
        StdOut.println("stddev                  = " + percolations.stddev());
        StdOut.println("95% confidence interval = "
                           + percolations.confidenceLo() + ", "
                           + percolations.confidenceHi());
    }
}

Result

trials                  = 1000

Matrix order            = 100
Time elapsed            = 711ms
mean                    = 0.5918497
stddev                  = 0.016182015867856135
95% confidence interval = 0.590846728265402, 0.5928526717345981
Matrix order            = 150
Time elapsed            = 1548ms
mean                    = 0.5925722666666671
stddev                  = 0.012359051812954566
95% confidence interval = 0.5918062446990673, 0.5933382886342669
Matrix order            = 200
Time elapsed            = 2909ms
mean                    = 0.5924982250000007
stddev                  = 0.00980778741196471
95% confidence interval = 0.5918903320382414, 0.59310611796176
Matrix order            = 250
Time elapsed            = 4699ms
mean                    = 0.5927787679999993
stddev                  = 0.008344998896150485
95% confidence interval = 0.5922615396097641, 0.5932959963902344
Matrix order            = 300
Time elapsed            = 7078ms
mean                    = 0.5931236444444441
stddev                  = 0.007199183633420095
95% confidence interval = 0.592677434419966, 0.5935698544689222
Matrix order            = 350
Time elapsed            = 10082ms
mean                    = 0.5928870448979593
stddev                  = 0.006583179647252199
95% confidence interval = 0.5924790151961042, 0.5932950745998143
Matrix order            = 400
Time elapsed            = 13322ms
mean                    = 0.5925558624999998
stddev                  = 0.005692078514108843
95% confidence interval = 0.592203063818588, 0.5929086611814116
Matrix order            = 450
Time elapsed            = 17437ms
mean                    = 0.5925850370370376
stddev                  = 0.005422322398156335
95% confidence interval = 0.5922489580129136, 0.5929211160611616
Matrix order            = 500
Time elapsed            = 22535ms
mean                    = 0.5927408759999994
stddev                  = 0.004986023171595944
95% confidence interval = 0.5924318390821024, 0.5930499129178963
Matrix order            = 550
Time elapsed            = 29226ms
mean                    = 0.5929557454545455
stddev                  = 0.004618400138898833
95% confidence interval = 0.5926694940482804, 0.5932419968608107
Matrix order            = 600
Time elapsed            = 37402ms
mean                    = 0.5927429777777777
stddev                  = 0.004069565303191747
95% confidence interval = 0.5924907435070581, 0.5929952120484974
Matrix order            = 650
Time elapsed            = 47626ms
mean                    = 0.5928332544378708
stddev                  = 0.004173448582106463
95% confidence interval = 0.5925745814148166, 0.5930919274609251
Matrix order            = 700
Time elapsed            = 59931ms
mean                    = 0.5926866428571428
stddev                  = 0.0037659630469823306
95% confidence interval = 0.5924532260492179, 0.5929200596650677
Matrix order            = 750
Time elapsed            = 73874ms
mean                    = 0.5929860995555557
stddev                  = 0.0038504371960324875
95% confidence interval = 0.5927474469856285, 0.5932247521254829
Matrix order            = 800
Time elapsed            = 89315ms
mean                    = 0.5927271359374998
stddev                  = 0.0035836033493786778
95% confidence interval = 0.5925050219007327, 0.5929492499742669
Matrix order            = 850
Time elapsed            = 106882ms
mean                    = 0.5928467750865053
stddev                  = 0.0032535179004236302
95% confidence interval = 0.5926451199578253, 0.5930484302151853
Matrix order            = 900
Time elapsed            = 125782ms
mean                    = 0.592534590123456
stddev                  = 0.0033149857431577436
95% confidence interval = 0.5923291251784124, 0.5927400550684996
Matrix order            = 950
Time elapsed            = 146882ms
mean                    = 0.5926625562326869
stddev                  = 0.003091779745979468
95% confidence interval = 0.5924709257386779, 0.592854186726696
Matrix order            = 1000
Time elapsed            = 168256ms
mean                    = 0.5928149579999994
stddev                  = 0.002929236887480933
95% confidence interval = 0.5926334020167352, 0.5929965139832636

Tab. 1 time - matrix order

Matrix Order	Time/ms
100	711
150	1548
200	2909
250	4699
300	7078
350	10082
400	13322
450	17437
500	22535
550	29226
600	37402
650	47626
700	59931
750	73874
800	89315
850	106882
900	125782
950	146882
1000	168256

Unfortunately, it's at least a quadratic algorithm.

To conclude, when x is small enough, the algorithm can be viewed as linear since x^2 generally contribute nothing to the whole time consumption. When x is big enough, like 1000 or more, then high degree can not be neglected. In order to have the stddev small enough, there have to be a extremely large x. Obviously this algorithm can not save the trouble of inevitable ax^2 like matrix initiation and block randomly open process, though it's still worth the time to scale down the a as much as possible.