Write a program to estimate the value of the percolation constant by simulation. The primary goal of this assignment is to introduce you to basic tools for understanding the effect of algorithm performance on completing a typical programming task.
Install Std* libraries. If you have not already done so, download StdDraw.java, StdIn.java, StdOut.java, StdRandom.java, and StdStats.java from http://www.cs.princeton.edu/introcs
Percolation simulation. The code Percolation.java which uses QuickU.java is your starting point. It fills random squares in an initially empty grid until the top row is connected to the bottom row, using the quick-union algorithm to detect connectivity. Your first task is to modify this code to display all of the squares that are connected to top (and bottom) in StdDraw.BLUE, as in this picture.
The purpose of having this program is to serve as a large-scale trace to make sure that your code works on reasonable-sized inputs. Knowing that it works properly for a 20-by-20 grid gives some confidence that it works for a 200-by-200 grid.
Initial experiments. The running time of Percolation.java is dominated by the graphics, so your next task is to remove the graphics calls to get a program PercolationX.java that can run experiments to produce an estimate for the percolation constant. Then modify the program to do multiple experiments:
Improved union-find implementations. Substitute implementations of weighted quick-union and weighted quick-union with path compression (either halving or full path compression) and run the same experiments as above. You may use the code from the lecture notes or implement your own versions. Observe the comparative performance characteristics of the three algorithms. Which is fastest? Why? Which is slowest? Why?
Deliverables. Submit your modified Percolation.java, PercolationX.java, QuickUW.java (weighted quick-union), and QuickUWPC.java (weighted quick-union with path compression). Each program should include its own main() that tests the associated operations. You may not call any Java library functions. Finally, submit a readme.txt file and answer the questions.
Extra credit. Develop and validate a model for the running time of your program when using quick-union, as a function of the number of cells.