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.

Lecture Recording

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

  2. 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
    2. Reveal answer
      βœ…

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

      image

      Note that all steps after the first two calls to Find() are doable in constant time.

  3. 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
    2. Reveal answer
      βœ…

      This is just an array look up as before.

  4. 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)?
    1. Something else
    2. 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.