What are the goals of this assignment?
- Set up a Java programming environment.
- Use our standard input and output libraries.
- Learn about a scientific application of the union–find data structure.
- Measure the running time of a program and use the doubling hypothesis to make predictions.
- Measure the amount of memory used by a data structure.
Can I add methods to Percolation? You must implement the Percolation API exactly as specified, with the identical set of public methods. You may not add public methods. However, you are encouraged to add private methods that enhance the readability, maintainability, and modularity of your program.
Can my Percolation data type assume the row and column indices are between 0 and N-1? No. The API specifies that valid row and column indices are between 1 and N.
How long should my program be? You should strive for clarity and efficiency. Our reference solution for Percolation.java is about 70 lines, plus a test client. Our PercolationVisualizer.java and PercolationStats.java clients are about 50 lines each. If you are re-implementing the union-find data structure (instead of reusing the implementations provided), you are on the wrong track.
What assumptions can I make about the input to PercolationVisualizer? It can be any valid input: that is an integer N ≥ 1, followed by pairs of integers between 1 and N. So, you do not have to worry about the input containing strings or floating-point numbers. But you do need to deal with pathological cases such as N = 1.
What assumptions can I make about the input to PercolationStats? It can be any valid input: that is an integer N ≥ 1 and an integer T ≥ 1. Note that if T is 1, then the standard deviation is undefined.
How do I specify the colors white, black, and light blue? They are predefined constants in standard draw: StdDraw.WHITE, StdDraw.BLACK, and StdDraw.BOOK_LIGHT_BLUE, respectively. (If you prefer a different shade of blue, that's fine too.)
In PercolationVisualizer, do I need to write how many sites have been opened, as in the movie? Do I need to separate each site by a black border as in the diagrams and movie? Neither of these is required. To include text, use the command StdDraw.text(). To achieve the black border effect, draw the background in black and draw the sites 90% of the size of grid cell.
Can I use setXscale() and setYscale() in PercolationVisualizer? Yes, provided you produce the identical drawing to the one you would obtain if you had not used setXscale() and setYscale(). Note that the default drawing area is the unit box from (0, 0) to (1, 1), with a 10% blank border (in which you should not draw).
After the system has percolated, my 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? This will be only a minor deduction, so don't go crazy trying to get this detail.
% java PercolationVisualizer < input10.txt
Where can I learn about tilde notation and the analysis of algorithms? We will cover that in Lecture 2. You may wish to defer the analysis portion of the assignment until then. It is also discussed in Section 4.2 of Introduction to Programming in Java.
How efficient should be the methods in Percolation? The construction should take N^2 time; the other methods should take time at most logarithmic in N.
How efficient should be PercolationVisualizer? This program is primarily to assist in debugging, so efficiency is not paramount. It is fine (and recommended) to clear the screen and redraw all N^2 sites after each new site is opened.
How do I generate a random blocked site for use in PercolationStats? Pick a site at random (by using StdRandom to generate two integers between 1 and N) and use this site if it is blocked; if not, repeat.
I don't get reliable timing information in PercolationStats when N is 200. What should I do? Increase the size of N (say to 400, 800, and 1600), until the mean running time exceeds its standard deviation.
How should I compute the mean and standard deviation? Don't reinvent the wheel—use StdStats.mean() and StdStats.stddev(), respectively.
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. Use the input*.txt files in the directory percolation for testing.
Submission. Be sure to click the Check All Submitted Files button to check that you submitted all of the required files and that they compile cleanly.
|
|
These are purely suggestions for how you might make progress. You do not have to follow these steps.
- Installing a Java programming environment. Follow the instructions from the first paragraph of Section 1.1 of Introduction to Programming in Java to install Java 1.6 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.
- Getting started. Download the directory percolation to your system. It contains the files stdlib.jar, *UF.java, and readme.txt that you need to get started. There are many files in stdlib.jar which you will use each week; this week you will use StdIn, StdDraw, StdRandom, StdStats, and Stopwatch.
- Union-find. Read Section 1.5 of Algorithms, 4th edition 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.
- Analysis of algorithms. Review Lecture 2, especially the sections on estimating running time (and the doubling hypothesis) and measuring memory space.