# 14.6 Exercises

- 1.
- 2.
- 3.Suppose we have the following WQU with path compression. What is the height of the tree after we call
`isConnected(8, 9)`

?

- 1.Which of the following arrays could represent a valid weighted quick union structure?
`[8, 0, 4, 0, 0, 4, 0, 4, 2, 0]`

`[4, -8, 8, 2, 1, -2, 1, 1, 4, 5]`

`[3, 3, 5, 9, 3, 6, 3, 4, 1, -10]`

`[2, -10, 1, 1, 1, 1, 1, 2, 1, 7]`

`[8, 0, 4, 0, 0, 4, 0, 4, 2, 0]`

: invalid. There is a cycle 8 --> 2 --> 4 --> 0 --> 8.`[4, -8, 8, 2, 1, -2, 1, 1, 4, 5]`

: invalid. The maximum height is$4 > \log_2 (10)$.`[3, 3, 5, 9, 3, 6, 3, 4, 1, -10]`

: invalid. The size of the tree rooted at 9 (excluding the subtree rooted at 3) is less than the size of the tree rooted at 3. As such, when we connected the two trees, 3 should have been the parent of 9 instead of the other way around.`[2, -10, 1, 1, 1, 1, 1, 2, 1, 7]`

: valid.

- 1.Define a
*fully connected*WQU as one where all elements are in the same set. What is the maximum and minimum height of a fully connected WQU with 6 elements? - 2.Suppose we have a WQU of height H. What is the minimum number of elements that must be in the WQU?

- 1.
- 2.Suppose we create a WQU with$N$items, then we perform$M_C$union operations and$M_U$union operations. Using big O notation, what is the runtime of this sequence of operations?
- 3.Using the same variables as problem 2, describe a sequence of operations that would result in a runtime of$O(N + M_U + M_C)$.
- 4.Write a
`int find(int p)`

method for the WQU with path compression. It should perform path compression as described in lecture: any node on the path from root to our target node should have its parent reset to the root. It takes in the target node`p`

and returns the root of the tree`p`

is in.

Last modified 11mo ago