Percolation Checklist

Should I implement the union–find data structures from scratch? No, use the versions in algs4.jar. On some assignments (such as this one), you will apply classic algorithms and data structures (from the textbook) to solve interesting problems. On other assignments (such as the next one), you will implement fundamental algorithms and data structures from scratch. Both are important skills.

Can I add (or remove) methods to (or from) the Percolation or PercolationStats APIs? No. You must implement the APIs exactly as specified, with the identical set of public methods and signatures (or you will receive a substantial deduction). However, you are encouraged to add private methods that enhance the readability, maintainability, and modularity of your program.

Why is it so important to implement the prescribed API? It is an essential component of modular programming, whether you are developing software by yourself or as part of a team. When you properly implement an API, others can write software to use your module or to test it. We do this regularly when grading your programs. For example, your PercolationStats client should work with our Percolation and vice versa. If you add an extra public method to Percolation and call it from PercolationStats, then your client won’t work with our Percolation. Conversely, our PercolationStats client may not work with your Percolation if you remove a public method.

How thoroughly must I test my code? For each program, you must include a main() method that unit tests the class. At a minimum, the main() method must not only call each public constructor and method directly, but it must also help verify that they work as prescribed (e.g., by printing results to standard output).

How many lines of code should my program be? You should strive for clarity and efficiency. Our reference solution for Percolation.java is about 80 lines, plus a test client. Our PercolationStats.java client is about 60 lines.

Frequently Asked Questions (Percolation)

Can I use a depth-first search based approach instead of using union–find? The percolation problem is discussed in Section 2.4 of Computer Science: An Interdisciplinary Approach (the course textbook for COS 126) and it uses depth-first search to solve a related problem. However, depth-first search will not meet the performance requirements of this assignment.

After the system has percolated, PercolationVisualizer colors in light blue all sites connected to open sites on the bottom (in addition to those connected to open sites on the top). Is this “backwash” acceptable? Yes. While allowing backwash does not strictly conform to the Percolation API, it requires a bit of ingenuity to fix. It is extra credit if you are able to implement a solution that meets the performance requirements and has no backwash.

Frequently Asked Questions (PercolationStats)

What should stddev() return if T equals 1? The sample standard deviation is undefined. We recommend returning Double.NaN but we will not test this case.

How do I generate a site uniformly at random among all blocked sites? Pick a site at random—use StdRandom to generate two integers between 0 (inclusive) and n (exclusive)—and use this site if it is blocked; if not, try again and repeat until you find a blocked site.

I don’t get reliable timing information when n = 200. What should I do? Increase the size of n (say to 400, 800, and 1,600), until the average running time exceeds its standard deviation.

I don’t get reliable timing information even when n is large. What should I do? Here are a few ideas.

I can’t squeeze 5 data points so that they all fit between 0.25 seconds and 30 seconds. What should I do? Try using a smaller multiplicative factor (such as \(\sqrt{2}\)) in the “doubling” test. If you use a non-integral multiplicative factor, round the resulting values of \(n\) or \(T\) to the nearest integer.

Testing

Testing. We provide two clients that serve as large-scale visual traces. Use them for testing and debugging your Percolation implementation.

Visualization client. PercolationVisualizer.java animates the results of opening sites in a percolation system specified by a file, performing the following steps:

Sample data files. The file percolation.zip contains sample data files for use with the visualization client. Associated with most input .txt files is an output .png file that contains the desired graphical output at the end of the visualization.

InteractiveVisualization client. InteractivePercolationVisualizer.java is similar to the first test client except that the input comes from a mouse (instead of from a file). It takes a command-line integer n that specifies the grid size.

Possible Progress Steps

Install a Java programming environment. The easiest way to accomplish this is to use the auto-installer for Mac OS X or Windows.
Download percolation.zip, which contains sample data files and clients.
Do not worry about backwash for your first attempt. You can revise your implementation later, time permitting.
For each method in Percolation that you must implement (e.g., open() and percolates()), make a list of which methods in WeightedQuickUnionUF (e.g., union() and find()) that might be useful for implementing that method. This should help solidify what you’re attempting to accomplish. Do not write your own union–find data structure or algorithms.
Using the list of methods from the API as a guide, choose instance variables that you’ll need to solve the problem. Don’t overthink this, you can always change them later. Instead, use your list of instance variables to guide your thinking as you follow the steps below, and make changes to your instance variables as you go.
Plan how you’re going to map from a two-dimensional (row, column) site to a one-dimensional union–find index. Write a private method to convert from 2D coordinates to 1D coordinates (instead of copying and pasting the conversion formula multiples times).
Write a private method for validating indices. Since each method must throw an exception for invalid indices, write a private helper method to do so (instead of copying and pasting the validation code multiples times).
Write the Percolation constructor. It’s job is to initialize all of the instance variables.
Write the open() method. The open() method should do three things. First, it should validate the indices of the site that it receives. Second, it should somehow mark the site as open and increment the number of open sites by one (if the site is not already open). Third, it should perform some sequence of union–find operations that links the site in question to its open neighbors. The constructor and instance variables should facilitate the open() method’s ability to do its job.
Test the open() method and the Percolation() constructor. These tests should be in main(). An example of a simple test is to create a percolation object with n = 2, then call open(0, 1) and open(1, 1), and finally to call percolates().
Write the percolates(), isOpen(), and isFull() methods. These should be very simple methods. Each of the methods (except the constructor) in Percolation must use a constant number of union–find operations. If you have a loop (or recursion) inside of one of your Percolation methods, you’re probably doing it wrong. Don’t forget about the virtual-top / virtual-bottom trick.
Test your complete implementation using the two visualization clients.
Write and test the PercolationStats class. Use standard random and standard statistics.
Analysis of algorithms. Review Lecture 2, especially the section on estimating running time and the doubling hypothesis. Analyze your program using each of QuickFindUF and WeightedQuickUnionUF by answering the questions provided in the readme.txt file.

A video is provided for those wishing additional assistance. Be forewarned that video was made in early 2014 and is somewhat out of date. For example the API has changed.

50 open sites	100 open sites	150 open sites
204 open sites	250 open sites

Frequently Asked Questions (General)

Frequently Asked Questions (Percolation)

Frequently Asked Questions (PercolationStats)

Testing

Possible Progress Steps