---
title: 'PS7'
disqus: hackmd
---

###### tags: `CSC263` `ps7`
CSC263 Problem set 7
===
##### Part (a)
The smallest n such that $T_1$ & $T_2$ are not equivalent is 8.
We can first perform 4 **MAKE-SET** operations to create 4 nodes, {a, b, c, d}.
Then we can perform **UNION(a, b)**, and **UNION(c, d)**, let their result be a' and c'. Up to this point, the operations performed using either $T_1$, and $T_2$ are both equivalent.
At last, we can perform a **FIND-SET(a', c')**, and after this, the result of this operation under $T_1$ implementation and $T_2$ implementation will be different.

Since both $T_1$ and $T_2$ uses union-by-weight, the key factor that makes their operation result to be different is on the path compression part. We know that path-compression happens when we perform **FIND-SET**. Let a tree be constructed by union-by-weight and **MAKE-SET**, then if it has 1 or 2 nodes, performing path-compression on it will not make any difference. When the tree has 3 node, since it is constructed using union-by-weight, the additional node added will link to the representative of the tree that has 2 nodes before the union. Thus this tree will always look like a binary tree with 3 nodes. And since every node is linked to the representative in a 3 node tree, performing a path compression does not change any thing. In a 4 node tree, there is two possible case, case 1 is that 3 nodes are linked to a representative node, and Case 2 is that 2 node is linked to the representative node, and 1 node is linked to either any non-representative node. In Case 1, performing path-compression will not make any difference, since every node is connected to the representative node. In Case 2, after performing path-compression, the tree will become the same structure of the tree in Case 1, with every node linked to the representative node. To obtain a tree that has the structure of Case 2, we need to have 7 operations, then we can perform a FIND-SET, then $T_2$ with path compression will alter the tree structure in the structure described by Case 1. Since $T_1$ does not have path compression, it will maintain in the structure of Case 2. Therefore the smalles number of operation s such that $T_1$ & $T_2$ are not equivalent is 7 + 1 = 8.

##### Part (b)

Make-Set(a)
Make-Set(b)
Make-Set(c)
Make-Set(d)
Make-Set(e)
Union(a, b)
Union(a, c)
Union(d, e)
Union(d, a)

**Justification for the difference:**
Let by $S_a$ denote the disjoint-set forest represented by set $a$.
The difference appeared after the last $Union$ operation.
$S_a$ has rank $1$ and weight $3$.
$S_d$ has rank $1$ and weight $2$.

Under $T_3$, since $S_a$ and $S_d$ has the same rank, when $Union(d, a)$ is executed, $d$ becomes the root after $Union$. But for $T_2$, because $S_a$.weight $>$ $S_d$.weight, $a$ becomes the new root after $Union$.
**Justification for why $n=9$ is the least amount of operations needed**:
Let $S^n$ denote the set of all disjoint-set forest with $n$ members.
Since $MakeSet$ and $FindSet$ are the same for both $T_2$ and $T_3$, the key is to find two small disjoint-set forest $A$ and $B$ such that $Union(A, B)$ under $T_2$ is different than under $T_3$.
For $A, B \in S^1$, $A.rank = B.rank$ and $A.weight = B.weight$, thus $Union$ would not give different result

The above assertion also true if $A, B \in S^2$.

Also if either one of $A$ or $B$ belongs to $S^1$, then $Union$ would not give different result under $T_2$ comparing to $T_3$ since we always append $A$ to $B$'s root.

Thus what we have so far shown that $A, B \notin S^1$ and one of $A$ or $B$ must belong to $S^{> 2}$.

We now attempt the next smallest possible pair, i.e. $A \in S^3$ and $B \in S^2$. This worked as we have previously justified.

To create $A$ and $B$ we need $5$ $MakeSet$ operations and $3$ $Union$ operations. Then $Union(A, B)$ is 1 operation. Thus we need at least $9$ operations to see the difference.