% java PercolationVisualizer < input10.txt
|
|
What are the goals of this assigment?
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? We recommend DrJava and the command-line, which is what most of you used in COS 126 (but feel free to use your another, such as Eclipse). For instruction on installling DrJava, go to the first paragraph of Section 1.1 of Introduction to Programming in Java. You should also be comfortable using the Terminal (OS X) or Command Prompt (Windows) on your system. You can review how to do this in Section 1.5.
Where can I learn about the standard input and output libraries that are used in this course? You should be familiar with them already if you took COS 126. If you placed out of COS 126, they are described in Section 1.5 and Section 2.2 of Introduction to Programming in Java booksite. Here are the APIs.
How should I format and comment my code? Here are some recommended style guidelines. Below are some that are particularly important (and you will lose points if you ignore).
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.
Can my Percolation data type assume the row and column indices are between 0 and N-1? No. The API specifies that the 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 clients are about 50 lines each.
In PercolationVisualizer, do I need to write how 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? Do I need to color the full sites exactly the same as in the diagrams and movie? No, none of these are 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. To color the full sites, We use StdDraw.setPenColor(cyan) where Color cyan = new Color(103, 198, 243);.
After the system has percolated, my PercolationVisualizer colors in cyan 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, we won't deduct for that. You can think of the water as filling back up from the bottom.
% 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 the methods in Percolation be? The construction should take N^2 time; the other methods should take time at most logarithmic in N.
How do I generate a random blocked site? 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 for 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 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, use the Quick* files from lecture as is. 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 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.
|
|
Testing. Use 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.