\item For any k, give an implementation of union-find where a
$FIND$ costs
$O(\log_k n)$, and a $UNION$ costs $O(k+\log_k n)$. ($n$ is the size of the universe)\\
\underline{Hint:} Use B[k]-trees, that is B-trees with degrees
between $k$ and $2k-1$.


\item Consider the data structure for Union-Find where the sets
are represented as trees with pointers to the parent (same as the
representation that you talk about in Friday's class). Suppose the
we implement the $FIND$ operation as usual: Go up in the tree
until you get to the root, and return it.

\begin{enumerate}

\item Suppose that the operation $UNION(a,b)$ is implemented by
finding the roots, $r_a$ and $r_b$, and setting the parent of $r_b$
to be $r_a$. Suppose you are working on a universe of $n$ elements.
Prove that the worst-case total cost of $m$ operations, when $m>n$,
is $\Omega(nm)$.

\item Suppose that you always maintain for each root the size of its
tree (call this the \emph{tree-size} of the root). Suppose that the
operation $UNION(a,b)$ is implemented by finding the roots, $r_a$
and $r_b$, and setting the parent of the root with smaller tree-size
to be the root with larger tree-size. Suppose you are working on a
universe of $n$ elements. Prove that the cost of each operation is
$O(\log n)$.

\end{enumerate}