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 continued our discussion on the disjoint-set union data structure, improving the previous implementations by using:

- the
*union-by-depth*heuristic, and - linked lists to connect the elements of a set (or the so-called
*threaded trees*).

- If we store the leader information as pointers, and apply the
**union by depth**heuristic, what is the complexity of`findSet(i)`

? - Something else
- If we store the leader information as pointers, and apply the
**union by depth**heuristic, what is the complexity of`unionSet(i,j)`

, ignoring the calls to`findSet(i)`

? - Something else
- If we store the leader information as
*direct pointers to the leader element,*with a linked list connecting all elements with a common leader, what is the worst-case complexity of`findSet(i)`

? - Something else
- If we store the leader information as
*direct pointers to the leader element,*with a linked list connecting all elements with a common leader,**and apply the union-by-size heuristic**, what is the worst-case complexity of`unionSet(i,j)`

? - Something else

## Reveal answer

Note that the size of the set whose leader element is, say, is at least , where denotes the depth of the tree associated with the set represented by . We can prove this by induction, and note that this implies that the complexity of `findSet(i)`

, which is really if is the leader element of the set that belongs to, is at most , where is the size of the set that belongs to.

## Reveal answer

Here's the algorithm for finding the union (borrowed from Chapter 11 in *Algorithms *by Erickson, c.f. PDF):

Note that all steps after the first two calls to `Find()`

are doable in constant time.

## Reveal answer

This is just an array look up as before.

## Reveal answer

in the worst case but amortized.

We will discuss this more in the next class, but you can get to the average case complexity by considering how many times an element is involved in an update.