COS 226 Percolation and Union-Find

COS 226 Programming Assignment

Note: this is a new assignment, under development. The final version will be ready on the morning of Monday, February 19. You are encouraged to get started, but please check again on Monday for the final version.

Percolation and Union-Find

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:

Take a number of trials as command-line parameter and add a loop to perform that many trials.
Use StdStats to print the sample mean and standard deviation of the observed percolation constant.

Starting at 10-by-10 with 10 trials, double the grid dimension until the running time is about 20 seconds on your computer. Use Stopwatch.java to measure running time. Does increasing the number of trials substantially improve the sample standard deviation? Do your experiments validate or refute the hypothesis that the running time is approximately a linear function of the number of cells? How accurate is your estimate of the percolation constant?

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.