# 23 Aug, 2021

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

#### In-class Quiz Questions

π
We continued our discussion on the disjoint-set union data structure, improving the previous implementations by using:
1. the union-by-depth heuristic, and
1. linked lists to connect the elements of a set (or the so-called threaded trees).
1. If we store the leader information as pointers, and apply the union by depth heuristic, what is the complexity of findSet(i)?
1. Something else
β
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.
1. 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)?
1. Something else
β
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.
1. 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)?
1. Something else
1. 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)?