Week 10, 10/30

Lab Exercises

1. Your completed PercolationVisualizer shouldd display the percolation process starting with a N-by-N grid of sites (initially all blocked and black). After each site is opened, display full sites in cyan, open sites (that aren't full) in white, and blocked sites in black using princeton.StdDraw.

   The PercolationVisualizer contains the following code:

   // set x- and y-scale
   StdDraw.setXscale(0, N);
   StdDraw.setYscale(0, N);
   

   These lines set the drawing coordinates to be within a bounding box whose lower left corner is (0,0) and whose upper right coordinate is (N,N).

   To achieve the black border effect, draw the background in black and draw the sites 90% of the size of grid cell. In other words, instead of the length and width of the filled square that you draw being 1 and 1 respectively. Make the length and width each be 0.9 and leave 0.1 as the border.

   1. What are should the four coordinates (upper left, upper right, lower left, lower right) be of the grid square (0,0) and (N-1, N-1)?

   2. What should the four coordinates of the square (i,j) where 0 &le i,j ≤ N?

   3. StdDraw.filledSquare draws a filled square of side length 2r, centered on (x, y). What is the appropriate call to draw the above grid square (i,j)?

2. Complete the draw method in PercolationDFS to draw the current state of the grid.

3. In class, we wrote the following code for percolates. int n = myGrid.length; // run DFS to find all full sites for (int k = 0; k < n; k++) dfs(0,k); // return true iff any full sites on bottom row for (int k=0; k < myGrid.length; k++) if (myGrid[n-1][k] == FULL) return true; return false;

   The method dfs should mark full all cells that are open and reachable from the passed in row and col /** * Private helper method to mark all cells that are open and reachable * from (row,col). * @param row is the row coordinate of the cell being checked/marked * @param col is the col coordinate of the cell being checked/marked */ private void dfs(int row, int col) { // TODO: complete dfs if (myGrid[row][col] != OPEN) return; }

   1. The case where the grid square is already full or blocked is a base case where no further computation is required. What other base case is there?
   2. As in the DFS Demo, your program should mark the current square as full and then check down, right, left, and up. Add the necessary calls to dfs.

4. To test your program with the visualizer, you should add code to the main method of the PercolationVisualizer to repeatedly declare sites open, draw, & pause until the system percolates. What methods of IPercolate interface should you be calling?

5. Your program likely does not work at this stage -- leaving some open areas unexplored. Why not? What is the fix?

6. Once you have completed and tested PercolationDFS, you should work on PercolationUF that uses a Union-Find implementation. The main idea is that initially all cells of a simulated grid are each part of their own set so that there will be n^2 sets in an nxn simulated grid. Finding an open cell will connect the cell being marked to its neighbors --- this means that the set in which the open cell is 'found' will be unioned with the sets of each neighboring cell.