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