> For the complete documentation index, see [llms.txt](https://cs61b-2.gitbook.io/cs61b-textbook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cs61b-2.gitbook.io/cs61b-textbook/14.-disjoint-sets/14.6-exercises.md).

# 14.6 Exercises

## Factual

1. [Problem 2](https://drive.google.com/file/d/1GuTG5O-2SSudWgm47rIi4orkmmpU4Apa/view?usp=share_link) from the Spring 2016 Midterm 2.
2. [Problem 1d ](https://drive.google.com/file/d/1uE1QlF4YguWVp8m8UJ97R2xPC4b1NnQ5/view?usp=sharing)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)`?

<figure><img src="/files/oIeRtsicZwne58esAGvZ" alt=""><figcaption></figcaption></figure>

<details>

<summary>Problem 1</summary>

[Solutions](https://drive.google.com/file/d/1KXLkjx1e8QPiu-waBJFwmcT5IToMHQK5/view?usp=sharing) are linked here and on the course website.

</details>

<details>

<summary>Problem 2</summary>

[Solutions](https://drive.google.com/file/d/1IYt4VbzdX4dTekh6cYAC8tigpJ_LgljV/view?usp=sharing) are linked here and on the course website.

</details>

<details>

<summary>Problem 3</summary>

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`.

</details>

## 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]`

<details>

<summary>Problem 1</summary>

* [ ] `[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.

</details>

## 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?

<details>

<summary>Problem 1</summary>

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

</details>

<details>

<summary>Problem 2</summary>

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

</details>

## Metacognitive

1. [Problem 3](https://drive.google.com/file/d/1yWyRp7QTizspTp9dsKz5yxE6bSf9YUIi/view?usp=sharing) 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.

<details>

<summary>Problem 1</summary>

[Solutions](https://drive.google.com/file/d/1b99XARlZxg3NMfeSAVt2yzDzwSEcASq3/view?usp=sharing) are linked here and on the course website.

</details>

<details>

<summary>Problem 2</summary>

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

</details>

<details>

<summary>Problem 3</summary>

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.

</details>

<details>

<summary>Problem 4</summary>

```java
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;
}
```

</details>