18 Aug, 2021

CoursesAlgorithms

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:

  1. findSet(i). Find (the leader of) the set containing i.
  2. 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 .

  1. If we store the leader information directly, what is the complexity of findSet(i)?
    1. Something else
    2. Reveal answer

      findSet(i) is an array lookup.

  2. If we store the leader information directly, what is the complexity of unionSet(i,j)?
    1. Something else
    2. 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.

  3. If we store the leader information as pointers, what is the complexity of findSet(i)?
    1. Something else
    2. Reveal answer

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

  4. If we store the leader information as pointers, what is the complexity of unionSet(i,j) apart from the calls to findSet()?
    1. Something else
    2. Reveal answer

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