Lab 6: Disjoint Sets

## Introduction

In this lab, you’ll create UnionFind which will be used to solve the dynamic connectivity problem. As mentioned in discussion “Union Find” is a synonym for “Disjoint Sets”.

Your implementation of the Union Find data structure will be the most advanced version from lecture, namely Weighted Quick Union. For more information about this please reference the slides from lecture. To better visualize and help you understand the operations on disjoint sets check out this online datastructure visualizer. Be sure to turn on Union by Rank where Rank = # of nodes (Union by Rank is just another way of saying “Weighted Quick Union”).

Optionally, you may also implement path compression. If you do so, make sure to enable Path Compression in the visualizer linked above.

## Weighted Quick Union

A skeleton will be provided in which you will have to fill in the following methods to complete the data structure:

• public UnionFind(int n): Creates a UnionFind data structure holding n vertices. Initially, all vertices are in disjoint sets.
• public void validate(int v1): Throws an exception if v1 is not a valid index.
• public int sizeOf(int v1): Returns the size of the set v1 belongs to.
• public int parent(int v1): Returns the parent of v1. If v1 is the root of a tree, returns the negative size of the tree for which v1 is the root.
• public boolean connected(int v1, int v2): Returns true if nodes v1 and v2 are connected.
• public void union(int v1, int v2): Connects two elements v1 and v2 together. v1 and v2 can be any valid elements, and a union-by-size heuristic is used. If the sizes of the sets are equal, tie break by connecting v1’s root to v2’s root. Unioning a vertex with itself or vertices that are already connected should not change the sets, but it may alter the internal structure of the data structure.
• public int find(int v1): Returns the root of the set v1 belongs to. Path-compression is employed allowing for fast search-time.

For the above functions you should also correctly handle faulty inputs, e.g if invalid vertices are passed into the above functions, throw an IllegalArgumentException.

When implementing UnionFind feel free to either follow the above order or any other order which makes sense to you. Please note that that these methods are not independent from one another, and some methods might be useful as helper methods for others.

## Optional Questions / Exercises

Below are a number of exercises that deal with Quick Find, Weighted Quick Union, and some variants of them. These questions are not required, but will serve as good practice in thinking about the differences between these differing implementations. The answers are displayed in white text, so if you want to check what you think highlight the line to reveal the text.

### Quick Find

1. Using the Quick Find algorithm with $N$ items, what is the worst-case runtime for the find operation?

Answer: The worst case runtime is $\Theta(1)$

2. Using the Quick Find algorithm with $N$ items, what is the worst-case runtime for the union operation?

Answer: The worst case runtime is $\Theta(N)$.

### Weighted Quick Union

Define a fully connected DisjointSets object as one in which connected returns true for any arguments, due to prior calls to union. Suppose we have a fully connected DisjointSets object with 6 items. Give the best and worst case height for the two implementations below. We define height as the number of links from the root to the deepest leaf, so a tree with 1 element has a height of 0. Give your answer as an exact value. Assume HeightedQuickUnion is like WeightedQuickUnion, except uses height instead of size/weight to determine which subtree is the new root. Hint: Try drawing out a few disjoint set trees and think about the different possible sequences of union operations that will result in the maximum height vs. the minimum height tree.

1. What is the best-case height for a WeightedQuickUnion containing 6 items?

Answer: The best case height is 1.

2. What is the worst-case height for a WeightedQuickUnion containing 6 items?

Answer: The worst case height is 2.

3. What is the best-case height for a HeightedQuickUnion containing 6 items?

Answer: The best case height is 1.

4. What is the worst-case height for a HeightedQuickUnion containing 6 items?

Answer: The worse case height is 2.

## TA Overview

At the end of lab, your TA will go over the reference solution to UnionFind. This will be helpful if you haven’t finished the lab, since we don’t want you to be stuck working on lab too much outside of lab. (This is also an incentive for you to go to lab!)

## Submission and Recap

In this lab we covered the implementation of Weighted Quick Union, optionally with path compression. You already know the drill, but just to remind you make sure to push your code to GitHub and submit to Gradescope to get credit for this lab. We will only be grading the code you have written in UnionFind.