Analysis

Implement PercolationUF using the quick find data structure (QuickFind.java) and by creating a version using the weighted quick union with path compression data structure.

Adapt the code from class or WeightedQuickUnionUF.java to create QuickUWPC.java which implements the IUnionFind interface. Run PercolationStats to gather timings for

  1. PercolationDFS
  2. PercolationUF with QuickFind
  3. PercolationUF with QuickUWPC

In your README, you will answer the following questions.

  1. How does doubling N affect the running time?
  2. How does doubling T affect the running time?
  3. Measure running time (using calls to System.currentTimeMillis) of the three versions of your program (DFS, Quick Find, and weighted quick union with path compression).
  4. Give a formula (using Big-Oh notation) of the running time on your computer (in seconds) as a function of both N and T.
  5. Estimate the largest experiment you could perform in one [minute, day, year] assuming your computer has enough memory.
  6. Give a formula (using Big-Oh notation) that describes the amount of memory (in bytes) that your IPercolate object consumes as a function of N for DFS, Quick Find, and weighted quick union with path compression).