logo

UTK Notes


Clicker Questions - 10-Disjoint

Behold the following instance of disjoint sets. Links go from low to high.

Question 1: How many disjoint sets are there?

Answer Four.

Question 2: If I say Union(4,5) (blue nodes) why will there be an error?

Answer 5 is not a set id.

Question 3: If I’m using Union-by-size, and I call Union(48,49) (pink nodes), what node’s link will change?

Answer 48

Question 4: If I’m using Union-by-height, and I call Union(48,49), what node’s link will change?

Answer 49

Question 5: If I’m using Union-by-rank-with-path-compression, how many links change when I call Find(28) (gray).

Answer 2 (28 and 44)

Question 6: If I’m using Union-by-rank-with-path-compression, Ranks[18] (green) can be three? Answer T or F.

Answer It originally was the root of a set whose height was three. For example, perhaps node 23 linked to 18 and 30 linked to 23. That set was unioned with 4, and then Find(30) was called. Because of path compression, nodes 30 and 23 now link directly to 4.

PDF Download, 2022 Class Stats, 2023 Class Stats