Dr$.$ Snevets is working on an algorithm that uses a Union$-$Find to maintain

a set partition, but her algorithm also needs to efficiently determine the

smallest element in each partition. Answer the following about developing

an improved Union$-$Find that efficiently supports a FindMin$(x)$ operation

that can return the minimum element in the same partition as $x.$

$($a$)$ One way to implement this improved data structure is to store a

third array min such that min$[r]$ is the minimum element in the tree

rooted at $r,$ for every root element $r.($ min can equal any value at

indexes that are not roots.$)$ Describe how to modify the perudocode

for the Union$-$Find initialize operation $($below$)$ to also initialize min

appropriately.

Input: n: size of the Union$-$Find to initialize

Output: a Union$-$Find of size n where every element

points to itself

Algorithm: Union$-$Find.Initialize

uf$\}=\backslash$operatorname$\{$Array$($n$)$

Initialize uf to $1..$n

size $=$ Array$($n$)$

Initialize size to $1$

return $($uf$,$size$)$

$($b$)$ What is the worst$-$case time complexity for your modified Initialize

algorithm? Justify your answer.

$($c$)$ Describe how to modify the Union operation $($below$)$ so that min

always stores the minimum element of the tree at every root $($min

can store anything at an index that is not a root of the Union$-$Find.$)$

$($d$)$ What is the amortized time complexity of your modified Union algo$-$

rithm? Show your work. Note that the Find operation does not need

to be changed from the optimized Union$-$Find presented in class.