Equivalence Classes

Question 1

Minimum Spanning Trees is an application/manipulation of equivalence classes

Answer 1

Minimum Spanning Trees results from establishing relationships between specific elements in a set.

Question 2

The equivalence classes are disjoint subsets

Answer 2

No element of S belongs to a difference equivalence class

Question 3

An equivalence relation E() over a set S defines a system of equivalence
classes within S

Answer 3

The equivalence class of some element x of S is that set of all y in S such that
E(x,y) is true:
• Note that every equivalence class defined this way is a subset of S
• The equivalence classes are disjoint subsets: no element of S is in two different equivalence classes
• The equivalence classes are exhaustive: every element of S is in some equivalence class

Question 4

Kruskal’s Alogrithm

Answer 4

1. Create a set with independent vertices
2. Each vertex is considered in its own equivalence class.
3. The algorithm considers edges in order of increasing cost. For
   each edge:
   • It is accepted if the vertices it connects are not in the same equivalence class
   • If it is accepted, the equivalence classes containing the vertices it connects are joined into one equivalence class
4. When |V|-1 edges have been accepted, the algorithm terminates.
5. The edges that have been accepted are the edges of the minimum spanning tree

These equivalence-class computations can be done very efficiently using a “disjoint subset”, “union/find” structure

Question 5

An abstract data type (ADT) designed for basic computations on equivalence classes is sometimes called a “disjoint subset” structure (since equivalence classes are disjoint subsets of their domain). It is sometimes also called a “union-find” structure because of the names of its principal operations.

Answer 5

Create(int N)

Find(int i)

Union (int m, int n)

Question 6

Implementing Disjoint SubSet Structure using :

Answer 6

LinkedList , when union just move all the contents into one head node
- however, this is very slow/inefficient , a it results in O(N^2 + NM)

Question 7

Improving efficiency comes from how unions are executed in which item to “move” in a list.

Trees are a better approach than Linked List.

Answer 7

If using TREES. Each tree is a subset and each node has at most 1 parent.

Find(int i): will go to the node and traverse up parent until it reaches null and then return the label to identify which subset it belongs to

Union (m,n) : will make one subset’s parent point to the parent of the others subset.

Question 8

Flaws in Implementations of a Disjoint Subset

Answer 8

Due to union-in order or how the union is designed the resulting trees might turn into a linked list.

While union will be O(k), the find will possibly take O(n)