DisjointSets vs. WeightedQuickUnionUF

For this assignment, we’ll use the WeightedQuickUnionUF class provided in the Princeton standard library.

​

Supports three options:

• void union(int p, int q): Unions two items.
• boolean connected(int p, int q): Returns true if items are connected.
• int find(int p): Returns set number of a given item.�

Very similar to the Disjoint Sets type from lecture. WQUUF:

• uses “union” instead of “connect”
• uses “connected” instead of “isConnected”
• Supports an additional operation called “find”

Project 3: Percolation

When N is large, theory guarantees a sharp threshold p*.

• p < p*: almost never percolates
• p > p*: almost certainly percolates.

​

What is the value of p*?

Project 3: Percolation

Likelihood of percolation depends very strongly on open-site probability p.

Spoilers: Basic Functionality

Initial State of the Universe

After One Open

open(3, 4)

After Two Opens

open(3, 4)

open(2, 4)

• union((3, 4), (2, 4))???

​

To Support Connectedness, Must Make Union Calls

Strong recommendation, write an xyTo1D(int r, int c) method, e.g. xyTo1D(2, 4) = 14

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

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

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

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

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

Checking Fullness

How to check if a cell is full?

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

Checking Fullness

One solution: Check every cell in the top row and call connected()

… (see previous slide)

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

Checking Fullness

How much time will isFull(int x, int y) take for a N x N grid?

Recall from lecture or a cheat sheet:

N calls to connected/isConnected: O(N log N)

Can we do this in one connected call? O(log N)?

• Hint: Need to treat the top row (and the bottom row) as one, so only one call is required: connected(top row, site #)

Good luck with the project!

… (see previous slide)

isFull(2, 2)

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

​

​

​

​

​

​