Example TDD

Below, we provide an example TDD for the Percolation assignment. Note that this solution is not fully correct.

Data

Not applicable for the Peroclation assignment.

---

Data Structures

• UF percUF of size N*N + 2 (grid plus virtualTop and virtualBottom).
  Used to answer percolates() efficiently.
• boolean[][] open tracks open sites.

---

Algorithms

Constructor

• Set up:
  • open[N][N] = false
  • percUF = new WeightedQuickUnionUF(N*N + 2) with virtualTop = N*N, virtualBottom = N*N + 1
• Don’t open or pre-connect anything.

open tile method:

• open(int row, int col)
• High-level pseudocode below (Note to self: Order of union calls doesn’t matter.)

checkBounds(row, col)
if open[row][col] is true: return because already open
open[row][col] = true

// convert to one dimensional index
int id = xyTo1D(row, col)

// if opened site at the top, connect to the virtual top
if row == 0:
    percUF.union(id, virtualTop)

// if at the bottom, connect to the virtual bottom
// note: don't connect the fullUF because we want
// to avoid backwash
if row == N-1:
    percUF.union(id, virtualBottom)

for each neighbor (nr, nc) in {up, down, left, right}:
    if inBounds(nr, nc) and open[nr][nc]:
        int nid = xyTo1D(nr, nc)
        percUF.union(id, nid)

Check if tile is open:

• isOpen(int row, int col)
• If in bounds, just return open[row][col].

Check if tile is full:

• isFull(int row, int col)
• If in bounds, just return percUF.connected(xyTo1D(row, col), virtualTop).

  Check if board percolates:

• percolates()
• Return percUF.connected(virtualTop, virtualBottom).

---

Complexity

Let M = N² be the number of sites.

• Constructor: Θ(N²) time, to build the arrays and union find objects, Θ(N²) space to store open[][] and the union find objects.
• open: Θ(1) work to do up to 4 neighbor checks, also takes a up to 4 UF union/connected calls, each of which is very close to constant time. In class we said that a union find object with path compression takes on average inverse-Ackermann time per operation with weighted quick-union. So overall time for those four calls is almost constant.
• isOpen: Θ(1) time to check open[][]
• isFull and percolates: Θ(1) connected calls, so basically constant time.

---

Questions

Open Questions

Will my percolation design work to avoid backwash? How do I check the bounds in a nice way?

---