% java PercolationVisualizer < input10.txt
|
|
What's a checklist? The assignment provides the programming assignment specification; the checklist provides clarifications, test data, and hints that might be helpful in completing the assignment.
Where can I find the course policies regarding submission, lateness, grading, and collaboration? Please read the Assignments Page.
Which Java programming environment should I use? We recommend DrJava and the command line. Here are instructions for installing Java and configuring the command line on your [ Windows · Mac OS X · Linux ] system. If you use another IDE (such as Eclipse), be sure that you can use command-line arguments, read from standard input, and redirect standard input and output.
I never took COS126. Or I took COS126 a long time ago. What material do I need to remember? If you took COS 126, you should already be familiar with our the basics of Java programming and our standard input and output libraries. For a review, read Sections 1.1 and 1.2 of Algorithms, 4th Edition.
What are the standard input and output libraries? We have designed a set of easy-to-use Java libraries for input and output that you are required to use in COS 226. Here are the APIs and installation instructions.
Can I use Java libraries such as java.util.LinkedList, java.util.ArrayList, java.util.TreeMap, and java.util.HashMap? No. You should not use any Java libaries until we have implemented equivalent versions in lecture. Once we have introduced them in lecture, you are free to use either the Java library version or our equivalent.
How do I throw a java.lang.IndexOutOfBoundsException? Use a throw statement like the following:
if (i <= 0 || i > N) throw new IndexOutOfBoundsException("row index i out of bounds");
Your code should not attempt to catch any exceptions—this will interfere
with our grading scripts.
How should I format and comment my code? Here are some recommended style guidelines. Below are some that are particularly important (and for which you will lose points if you ignore).
What's the easiest way to copy a subdirectory from the COS 226 ftp site to my computer?
|
|
What are the goals of this assignment?
Can I add (remove) methods to (from) Percolation? No. You must implement the Percolation API 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. The one exception is main()—you are always permitted to add this method to test your code, but we will not call it unless we specify it in our API.
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.
Why is it so important to implement the prescribed API? Writing to an API is an important skill to master because it is an essential component of modular programming, whether you are developing software by yourself or as part of a group. When you develop a module that properly implements an API, anyone using that module (including yourself, perhaps at some later time) does not need to revisit the details of the code for that module when using it. This approach greatly simplifies writing large programs, developing software as part of a group, or developing software for use by others. For example, your program depends on StdIn and WeightQuickUnionUF implementing their documented APIs.
Most important, 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 your PercolationVisualizer client should work with our Percolation data type and vice versa. If you add an extra public method to Percolation and call them from PercolationVisualizer, then your visualizer won't work with our Percolation data type. Conversely, our PercolationVisualizer client may not work with your Percolation data type if you remove a public method.
How many lines of code 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: 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: an integer N ≥ 1 and an integer T ≥ 1. Note that if T = 1, then the standard deviation and confidence interval are undefined.
How do I perform animations using standard draw? You can use BouncingBall.java as a guide. The command StdDraw.show(t) performs two related actions: it pauses for t milliseconds (leaving the current drawing on the screen) and it turns on animation mode (deferring future drawing commands until the next call to show()). It is important that the last statement in your animation loop is a call to show() and not a drawing command.
How do I specify the colors white, black, and light blue? Use the predefined constants in standard draw: StdDraw.WHITE, StdDraw.BLACK, and StdDraw.BOOK_LIGHT_BLUE, respectively.
In PercolationVisualizer, do I need to separate each site by a black border as in the diagrams and movie? No, but it's easy to do: draw the background in black and draw a site as a filled square that is 90% of the size of a grid cell.
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
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 = 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.
|
|
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.
|
|
Is it possible to perform one experiment in PercolationStats in N^2 time? Yes, but you are not expected to discover such an algorithm on this assignment.
I'm curious. Where can I learn a bit more about the percolation model? Read Section 2.4 of Introduction to Programming in Java.