Percolation How-To

What should I read prior to writing code: Most of the code in this assignment comes from discussion in the text and supplementary reading. Please review the following

• Section 2.4 in the course textbook, Introduction to Programming in Java by Robert Sedgewick & Kevin Wayne
• Sedgewick & Wayne's union-find case study or the following excerpt from Algorithms, 3rd Edition.

What do I need to write You have to add code to the following files:

1. PercolationDFS.java: This class implements the brute force method for percolation. Please refer to Section 2.4 in the textbook. You will complete the following methods:
   • constructor: initialize a grid of size n
   • open: open a particular grid cell
   • isOpen & isFull: give current state of grid cell
   • percolates and dfs: determine whether current grid will percolate by implementing recursive scheme depth-first search as discussed in class and the textbook
2. PercolationVisualizer.java: complete main so that it repeatedly calls a percolator (i.e., something that implements IPercolate like PercolationDFS) to declare sites open, draw, and pause until the system percolates
3. PercolationUF.java: You will implement a more efficent solution that can use any union-find algorithm that implements IUnionFind (e.g., QuickFind.java)
   • constructor: initialize a grid of size n and union-find algorithm
   • open: open a particular grid cell and merge components as appopriate
   • isOpen & isFull: give current state of grid cell
   • getIndex: return an index that uniquely identifies (row, col), so that each grid square can be in its own set at the beginning
   • percolates: determine whether top and bottom are connected (i.e., in the same component)
4. QuickUWPC.java: class that implements weighted quick union with path compression data structure. See the Sedgewick & Wayne case study or the following reading for more informaiton. You will need to create this file by adapting WeightedQuickUnionUF.java or WeightedQuickUnionHalvingUF.java. The class should implement the IUnionFind interface.
5. PercolationStats.java: prompts for N and T, performs T experiments on NxN grid, and prints mean, standard deviation, confidence interval, and timings.

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 OK? Yes, we won't deduct for that. You can think of the water as filling back up from the bottom.

How efficient should the methods in Percolation be? The construction should take N² time; the other methods should take time at most logarithmic in N.

How do I generate a random blocked site? Create a list of all blocked sites. Shuffle the list at the beginning and then each step pick the next element from the list.

What do I submit? Submit using percolation as the assignment name. Submit a README and all .java files.

What do clases do I need to test in PercolationStats? You need to test PercolationDFS, PercolationUF with QuickFind, and PercolationUF with WeightedQuickUnionHalvingUF. Check back for more questions and answers.