COS 226 Programming Assignment Checklist: Percolation

Frequently Asked Questions

What's a checklist? The assignment checklists are meant to supplement the assignment, clearing up any potentially confusing points and providing some hints.

Is there anything else I should do before getting started? Please read the Assignments Page, including the collaboration policy, lateness policy, and submission system instructions if you have not done so already.

What Java programming environment should I use? You are free to choose your own. We recommend DrJava and the command-line, which is what most of you used in COS 126. For instruction, go to the first paragraph of Section 1.1 of Introduction to Programming. You will also need to use the Terminal (OS X) or Command Prompt (Windows) on your system. You can review how to do this in Section 1.5 of Introduction to Programming in Java.

Where can I learn about the Std*.java libraries? They are described in Section 1.5 and Section 2.2 of Introduction to Programming in Java booksite. Here are the APIs.

How long should my program be? You should strive for clarity and efficiency. Our reference solution is 75 lines, plus a test client.

Do I need to implement draw()? Yes, you should implement the same API as PercolationDFS. Note that you shouldn't need the array full[][]; instead you can determine which sites are full by using the find() method.

How should I format and comment my code? Here are some style guidelines that your grader will appreciate.

How long should the methods in PercolationUF take? Make step() and percolates() as fast as you can. Don't worry much about draw() since the bottleneck will be drawing the squares on the screen.

I don't get reliable timing information for when N is 100. What should I do? Increase the size of N (say to 200, 400, 800, and 1600), until mean running time exceeds the standard deviation of the running time.

My program is getting overly-complicated because I'm re-implementing the union-find data structure, specializing it to an N-by-N grid of objects. Am I on the right track? No, you are re-inventing the wheel. Instead, reuse Quick*. This design makes your code more modular and easier to understand.

Is it possible to perform one experiment in N^2 time? Yes, but you are not asked to discover the algorithm.

I'm curious. Where can I learn a bit more about the percolation model? Read Section 2.4 of Introduction to Programming in Java.

Testing and Submitting

Submission.   After you have submitted all of the required files, the "Run Script" button on the submission system will appear. Be sure to hit the button and check that you submitted the right files and they compile cleanly.

Readme.   Use the following readme file template and answer all questions.

Possible Progress Steps

These are purely suggestions for how you might make progress. You do not have to follow these steps.

1. Installing a Java programming environment. Follow the instructions from the Hello World assignment from COS 126 to install Java 1.5 on your system. If you have a previous version of Java, we recommend uninstalling it before upgrading. To develop your programs, we recommend DrJava and the command line. If you use an IDE (integrated development environment), be sure that you can use command-line arguments, read from standard input, and redirect standard input and output.

2. Getting started. Download the directory percolation to your system. It contains the files PercolationDFS.java, Quick*.java, Stopwatch.java, and readme.txt that you need to get started.

3. Union-find. Read Chapter 1 of Algorithms in Java and review the slides for lecture 1 for more information on union-find algorithms. Completing this assignment successfully requires a general idea of how these algorithms work, but not a detailed understanding of the analytic results.

4. Analysis of algorithms. Review Lecture 2, especially the section on estimating running time and the doubling hypothesis.