Courses ⸱ Algorithms

You can also access the quiz on Itempool here if you want to practice, or see the notes below for more context.

#### Lecture Recording

#### In-class Quiz Questions

We introduced the

*Disjoint Set Union*data structure, where the goal is to maintain a collection of disjoint sets over the “universe” . Each set has a unique “leader” or “representative” element, which identifies the set.We want to support the following operations:

**findSet(i).**Find (the leader of) the set containing**i**.

**unionSet(i, j).**If the sets that**i**and**j**belong to are and , respectively, then we replace the sets and in our collection with their union .

- If we store the leader information directly, what is the complexity of findSet(i)?
- Something else

## Reveal answer

findSet(i) is an array lookup.

- If we store the leader information directly, what is the complexity of unionSet(i,j)?
- Something else

## Reveal answer

For implementing unionSet(i,j) we have to go through the entire array to make sure that the leader information is appropriately updated.

- If we store the leader information as pointers, what is the complexity of findSet(i)?
- Something else

## Reveal answer

A series of union updates can create a pointer chain of length .

- If we store the leader information as pointers, what is the complexity of unionSet(i,j)
*apart from the calls to findSet()*? - Something else

## Reveal answer

unionSet(i,j) is a single pointer update after the findSet() queries have been executed.