Set and UFDS

Question 1

2 implementations for sets

Answer 1

1. HashTable -> if don’t have to union or intersect
2. Union-Find Disjoint Sets (UFDS)

Question 2

2 Key Ideas of UDFS

Answer 2

1. Each set is modelled as a tree, thus a collection of disjoint sets form a forest of trees
2. Each set is represented by a representative item, which is the root of the corresponding tree of that set

Question 3

Main Implementation of UFDS

Answer 3

Arrays for Parents and Ranks

Question 4

Time Complexity of findSet

Answer 4

O(a(N)) -> Recursively visit p[i] until p[i] = i, then compress the path

Question 5

Time Complexity of isSameSet

Answer 5

O(a(N)) -> Check if findSet(i) == findSet(j)

Question 6

Time Complexity of unionSet

Answer 6

O(a(N)) -> If i and j are of different disjoint sets, we can union the two sets by setting the representative item of the taller tree to be the representative item fo the new combined set

Question 7

What is the Union by Rank heuristic

Answer 7

We use another integer array rank where rank[i] stores the upper bound of the height of tree rooted at i. It is an upper bound as path compressions can make trees shorter than its upper bound and we don’t want to waste effort maintaining the correctness of rank[i]

Question 8

What is the Inverse Ackermann Function - a(N)

Answer 8

If both Union by Rank and Path Compression heuristics are used, then UFDS operations run in O(a(N)) time. We can assume it as O(1) for practical values of N.