CSC300 / CSC402: Homework (UF problems, Percolation)

Homework (UF Problems, Percolation) [1/1]

Read Algorithms 1.4 and 1.5 again.
Read Algorithms 2.1. Also read the discussion of stability in section 2.5 (page 341 in the the text).

Do these problems on paper, but don't hand them in.

1.5.1: Show the contents of the id[] array and the number of times the array is accessed for each input pair when you use quick-find for the sequence 9-0 3-4 5-8 7-2 2-1 5-7 0-3 4-2.
1.5.2: Do Exercise 1.5.1, but use quick-union (page 224). In addition, draw the forest of trees represented by the id[] array after each input pair is processed.
1.5.3: Do Exercise 1.5.1, but use weighted quick-union (page 228).

1.5.8: Give a counterexample that shows why this intuitive implementation of union() for quick-find is not correct:

public void union(int p, int q) {
  if (id[p] == id[q]) return;
  // Rename p's component to q's name.
  for (int i = 0; i < id.length; i++)
    if (id[i] == id[p]) id[i] = id[q];
  count--;
}

1.5.10: In the weighted quick-union algorithm, suppose that we set id[find(p)] to q instead of to id[find(q)]. Would the resulting algorithm be correct?

Review the notes on Percolation from class. Start at Slide 41:
Notes from the textbook

Complete Percolation.java

Hints: Depending on how you do it, you could use one or two Union Find data structures! Top and bottom virtual sites could also be created to efficiently determine if the system percolates.

Use InteractivePercolationVisualizer.java for testing. Run it and click around the grid to see what happens.

In PercolationVisualizer.java there is a main method with different simulations provided by the author of the textbook. You will need to change the path to the input files to be src/main/java/algs15... (this is required to get things working in IntelliJ IDEA).

PercolationStats.java is where you will run your simulations to run experiments to converge on the value of p*.

Here's a song to listen to while you work.

file:Percolation.java [source]

package algs15.perc;

//import stdlib.*;
//import algs15.*;

// Uncomment the import statements above.

// You can test this using InteractivePercolationVisualizer and PercolationVisualizer
// All methods should make at most a constant number of calls to a UF data structure.
// You can use more than one UF data structure.
// You can assume that N>1
//
// Note that you can print out a UF structure using its toString method.
// You can also use the toGraphviz method to draw the UF.
// These may be useful for debugging.
// Try calling them whenever you open a new square.
public class Percolation {
  int N;
  boolean[] open;
  // TODO: more fields to add here
  public Percolation(int N) {
    if (N < 2) throw new IllegalArgumentException();
    this.N = N;
    this.open = new boolean[N*N];
    // TODO: more to do here
  }
  // open site (row i, column j) if it is not already
  public void open(int i, int j) {
    int x = i*N+j;
    if (!open[x]) {
      open[x] = true;
      // TODO: more to do here.
    }
  }
  // is site (row i, column j) open?
  public boolean isOpen(int i, int j) {
    return open[i*N+j];
  }
  // is site (row i, column j) full?
  public boolean isFull(int i, int j) {
    // TODO
    return false;
  }
  // does the system percolate?
  public boolean percolates() {
    // TODO
    return false;
  }
}