# 14.6 Exercises

Last updated

Last updated

Factual

Problem 2 from the Spring 2016 Midterm 2.

Problem 1d from the Spring 2015 Midterm 2.

Suppose we have the following WQU with path compression. What is the height of the tree after we call

`isConnected(8, 9)`

?

Conceptual

Which of the following arrays could represent a valid weighted quick union structure?

Procedural

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?Suppose we have a WQU of height H. What is the minimum number of elements that must be in the WQU?

Metacognitive

Problem 3 from the Spring 2017 Midterm 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?

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)$.

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.