14.6 Exercises

Factual

1. Problem 2 from the Spring 2016 Midterm 2.

2. Problem 1d from the Spring 2015 Midterm 2.

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

Problem 1

Solutions are linked here and on the course website.

Problem 2

Solutions are linked here and on the course website.

Problem 3

The resulting tree will have height 1. Every node along the path from 0 to 9 will now have parent 0, and similarly every node along the path from 0 to 8 will also have parent 0.

Conceptual

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]

Problem 1

• [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.

Procedural

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?

Problem 1

The minimum height is always 1 (all elements are connected to the root). The maximum height is 2 (we take the floor of $\log_2 6$).

Problem 2

We know that $H \leq \log_2 N$, where $N$ is the number of elements in the WQU. As such, $N \geq 2^H$.

Metacognitive

1. Problem 3 from the Spring 2017 Midterm 2.
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.

Problem 1

Solutions are linked here and on the course website.

Problem 2

$O(N + (M_U + M_C)\log N)$. Each operation takes $\log N$ time, and we need $N$ time to initialize an empty array of size $N$.

Problem 3

Initialize the array as usual. Then, connect the items in sequence: connect(0, 1), connect(0, 2), connect(0, 3), up to connect(0, N). This results in a height-1 tree, on which connect and isConnected run in constant time.

Problem 4

public int find(int p) {
    int root = p;
    while (root != parent[root]) {
        root = parent[root];
    }
    
    while (p != root) {
        int newp = parent[p];
        parent[p] = root;
        p = newp;
    }
    
    return root;
}