# Notes - DAA HT23, Disjoint sets

> Source: https://ollybritton.com/notes/uni/prelims/ht23/daa/notes/disjoint-sets/ · Updated: 2023-03-23 · Tags: uni, notes

- [Course - Design and Analysis of Algorithms HT23](https://ollybritton.com/notes/uni/prelims/ht23/daa/)
	- [Notes - ADS HT24, Disjoint sets](https://ollybritton.com/notes/uni/part-a/ht24/ads/notes/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?::

$$
O(m + n^2)
$$

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?::

$$
O(m + n \log n)
$$

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?::

$$
O(m \alpha(n))
$$

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.

### Proofs

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt