CS61B Fall 2023

Homework Intro Section

Homework 2: Percolation

Introduction

• Building 2 data types
• Percolation.java → will be solving the percolation problem, which we will discuss in further slides
• PercolationStats.java → will be using percolation to learn something interesting

CS61B Fall 2023

What is Percolation?

CS61B Fall 2023

Percolation Methods

• public Percolation(int N) // create N-by-N grid, with all sites initially blocked
• public void open(int row, int col) // open the site (row, col) if it is not open already
• When you open a site, connect all 4 sides if possible
• public boolean isOpen(int row, int col) // is the site (row, col) open?
• Imagine having a 2D array of booleans
• public boolean isFull(int row, int col) // is the site (row, col) full?
• Might need to scan through the universe and keep track of information
• public int numberOfOpenSites() // number of open sites
• public boolean percolates() // does the system percolate?
• Might need to scan through the universe and keep track of information
• public static void main(String[] args) // use for unit testing

​

CS61B Fall 2023

What is a Weighted Quick Union and how can it help us?

CS61B Fall 2023

WeightedQuickUnion stores the parent of each node in the array and merges sets by setting the parent of one root to the other based off size (merge smaller into larger)

​

We can use a single array to represent our disjoint set when implementing union() optimally

​

arr[i] contains the parent of element i in the set; the index of a root contains -(# elements in set rooted at that index)

​

​

​

[-9, 0, 0, 0, 0, 1, 1, 4, 4]

​

WeightedQuickUnionUF

• public WeightedQuickUnionUF(int n) // creates a UF with n elements
• public int count() // number of disjoint sets
• public int find(int p) // the root of p's set
• public boolean connected(int p, int q) // whether p and q are in the same set
• public void union(int p, int q) // join p and q's sets together }

​

To think about in your code

• How many sites you need for WQU?
• What is the index of TOP and BOTTOM?

​

​

CS61B Fall 2023

Initial State of the Universe

CS61B Fall 2023

After One Open

open(3, 4)

CS61B Fall 2023

After Two Opens

open(3, 4)

open(2, 4)

• union((3, 4), (2, 4))???
• Error: remember union can only take in two integers union(a, b)
• Make a helper method to convert x, y to 1D

​

CS61B Fall 2023

To Support Connectedness, Must Make Union Calls

open(3, 4)

open(2, 4)

• union(14, 19)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

After Three Opens

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

After Four Opens

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

open(2, 3)

• union(12, 13)
• union(13, 14)

​

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

After Five Opens

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

open(2, 3)

• union(12, 13)
• union(13, 14)

open(0, 2)

​

​

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

After Six Opens

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

open(2, 3)

• union(12, 13)
• union(13, 14)

open(0, 2)

open(1, 2)

• union(2, 7)
• union(7, 12)

​

​

​

​

​

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

Checking Fullness

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

open(2, 3)

• union(12, 13)
• union(13, 14)

open(0, 2)

open(1, 2)

• union(2, 7)
• union(7, 12)

isFull(2, 2)

• ???

​

​

​

​

​

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

Checking Fullness

Could call connected for each item in top row but too slow!!

open(3, 4)

open(2, 4)

• union(14, 19)

open(2, 2)

open(2, 3)

• union(12, 13)
• union(13, 14)

open(0, 2)

open(1, 2)

• union(2, 7)
• union(7, 12)

isFull(2, 2)

• connected(0, 12)
• connected(1, 12)
• connected(2, 12)
• connected(3, 12)
• connected(4, 12)

​

​

​

​

​

​

0

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

CS61B Fall 2023

Virtual Sites

CS61B Fall 2023

• Remember that if we loop through and check if the whole grid is connected(a,b), it will take too much time
• One approach is the virtual sites method
• Virtual top: connected to all open items in top row
• Virtual bottom: connected to all open items in bottom row
• Example: checking isFull
• See if there is a connection to the top site
• Example: checking percolation
• Check is there is a connection between the top and bottom sites

Beware! Backwash

CS61B Fall 2023

• If you use virtual sites, you will encounter a problem we call backwash
• If you create a tunnel from the top to the bottom, then make another tunnel at the button, them it should not be full

water should not flow back up through the virtual bottom site!

Backwash Tips

CS61B Fall 2023

• This is a very tricky problem! Hardest part of the homework for most people
• Solution is only a small amount of code
• Hint 1: https://www.youtube.com/watch?v=-pr7psbTSOU
• Hint 2: https://www.youtube.com/watch?v=gTqM4WvM9D8

FAQ

• How do I create and use virtual top and bottom sites?
• Create two extra indices in your WeightedQuickUnionUF object, one for virtual top and one for virtual bottom. Connect the virtual top to all sites in the top row, and virtual bottom to all sites in the bottom row.
• How do I convert between 2D and 1D indices?
• Use a formula like: 1D index = row * N + col, where N is the grid size. This should be done without loops for constant time.
• What's the difference between open and full sites?
• An open site is one that has been "dug out". A full site is open and connected to the top (filled with water). Open sites can be either full or empty.
• How do I implement numberOfOpenSites() in constant time?
• Keep a counter that you increment each time you open a new site.

CS61B Fall 2023

FAQ

• Can I use loops in my methods?
• Loops should be avoided in the main methods (open, isOpen, isFull, numberOfOpenSites, percolates) to maintain constant time complexity.
• What data structures should I use?
• At minimum, you need a WeightedQuickUnionUF object. You may also want additional arrays or variables to track open sites or other information.
• How do I test if my implementation is correct?
• Use the provided PercolationVisualizer and InteractivePercolationVisualizer to visualize your implementation. Also run the provided unit tests and submit to Gradescope.
• What are the runtime requirements?
• The constructor should take time proportional to N^2. All other methods should take constant time plus a constant number of calls to WeightedQuickUnionUF methods.

CS61B Fall 2023

Questions

CS61B Fall 2023