Princeton Algorithm Assignment 1

Translate from my old Chinese blog

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:

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:

The second class

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

Leave a Reply

Your email address will not be published. Required fields are marked *