DS3 UNION-FIND

Question 1

UNION-FIND INTRO

Answer 1

create connections between objects
min connections required
-if a-b and a-c then b-c so no direct connection between them required

-objects
-subsets of connected objects

Question 2

UNION-FIND ABSTRACTION

Answer 2

union(x, y): connect subsets that contain x and y
find(x): return id of set that contains x
is how we decide if a set is unnecessary

connected components(subsets) decrease in number with every union

solution:
for pair of numbers x,y
-find(x) to see if there is a connection (or find(x) then find(y) and compare ids)
-if yes continue
-if no union(x, y)
unions and objects can be a high number (time cost)

Question 3

QUICK FIND

Answer 3

integer array id[] size n
id[i] contains the representative(id) number of the subset that contains i
p,q are connected if id[p]=id[q]
i : 0 1 2 3 4 5 6 7 8 9
id: 0 1 9 9 9 6 6 7 8 9
this means:
{0} {1} {2 3 4 9} {5 6} {7} {8}

if p,q not connected change all with id[p] to id[q]
code:

quickF(n)
~{int id[] = new id[n];
~for(int i = 0; i<n; i++)
~~{id[i] = i;} //initialization no connections
~for(In.init(); !In.empty();) //while there is input cause we supposedly give pairs of numbers as input
~~{int p = In.getInt(), q = In.getInt();
~~int temp = id[p];
~~if(temp == id[q]){continue;}
~~{for(int i = 0; i<n; i++)
~~~{if(id[i]==temp){id[i] = id[q];}
}}}
union is not fast as we can see
m*n for m unions of n objects so O(n)

Question 4

QUICK UNION

Answer 4

using trees: find is slower
id[i] is parent of i
find gets the root of two numbers and compares
change id[i] to root of j
find is slower depending on tree height O(n)
code:

quickU(n)
~{int id[] = new int[n];
~for(int i = 0; i<n; i++)
~~{id[i] = i;} //initialization no connections
~for(In.init(); !In.empty();)
~~{int i, j, p =In.getInt(), q = In.getInt();
~~for(i = p; i != id[i]; i = id[i]) //finds root of p
~~for(j = q; j != id[j]; j = id[j]) //finds root of q
~~if(i == j)){continue;}
~~id[i] = j;} //makes root of i equal to root of j
}}`

Question 5

WEIGHTED QUICK UNION

Answer 5

use additional array size[] for nodes of every tree
put smaller tree under bigger one to minimize height extension
size is initially 1
add to quickU code:
if(size[i] <size[j]){id[i] = j; size[j] += size[i];}
else{id[j] = i; size[i] += size[j];}

find complexity proportional to height of tree (O(logn))
for m pairs mlogn
much better that quickU and quickF

it can still be optimized

Question 6

UNION WITH PATH COMPRESSION

Answer 6

full compression:
1st loop to find root
2nd loop to make parent of every node the root
2 iterations until root is not the best
half compression:
during root finding we make every second node change to it’s parent’s parent
~~for(i = p; i != id[i]; i = id[i]) //finds root of p
{id[i] = id[id[i]];}
~~for(j = q; j != id[j]; j = id[j]) //finds root of q
{id[j] = id[id[j]];}
half compression seems to have better performance than all other methods

Question 7

SUMMARY

Answer 7

basic abstract functionalities -> simple implementation -> stepwise refinement and optimization

for n objects and m input pairs:
-quick find, union: O(mn)
-weighted union: O(mlogn)
-weighted union with path compression: o(m+n)

in terms of stable n and m increasing to n weighted path compression is optimal since nlogn > 2n (this is our case since n is decided at the beginning of the program and doesnt change)
but in case of n increasing exponentially non compression is best since logn< n