Notes - DAA HT23, Disjoint sets
Flashcards
What are the three basic operations of a disjoint-set data structure?
- $\text{Make-Set}(x)$, which makes a new set $\{x\}$ and adds it to the collection $\mathcal S$ of disjoint sets.
- $\text{Union}(x, y)$, which removes the sets containing $x$ and $y$ and adds a new set containing the union of the two sets.
- $\text{Find-Set}(u)$, which returns the pointer of the representative of the set containing $u$.
In a disjoint-set data structure, how is each set identified?
By a representative member of each set.
For a disjoint-set data structure, given $m$ total operations and $n$ $\text{Make-Set}$ operations, what is the running time when implemented via a linked list?
For a disjoint-set data structure, given $m$ total operations and $n$ $\text{Make-Set}$ operations, what is the running time when implemented via a “weighted” linked list?
For a disjoint-set data structure, given $m$ total operations and $n$ $\text{Make-Set}$ operations, what is the running time when implemented via a disjoint-set forest?
One simple implementation of a disjoint-set data structure uses a linked list and handles $\text{Union(x, y)}$ by tacking the linked list for $y$ onto the one for $x$. How does the weighted-union heuristic improve this?
Appending the shorter list onto the longer list.
When implementing a disjoint-set data structure using a linked list, what pointers are used?
Pointers to the next element (i.e. like a normal linked list) and pointers to the head of the list (the representative).
In the context of running time analysis, what is the very slow-growing function $\alpha(n)$?
The inverse Ackermann function.
Roughly speaking, what is a primitive recursive function?
A function that can be computed in a language with just for loops.
What is an example of a function that is not primitive recursive?
The Ackermann function.