\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\newcommand{\proc}[1] {\textnormal{\scshape#1}}
\begin{document}
\begin{center} \Large
{\scshape 6.897 Advanced Data Structures (Spring'05)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Mihai P\v{a}tra\c{s}cu} \\[2ex]
\framebox{Problem 4} \quad {\em Due: Monday, Feb.~28}
\end{center}
Incremental connectivity is the problem of maintaining an undirected
graph under edge insertions and connectivity queries (no
deletions). This is essentially equivalent to the union-find
problem. This problem asks to maintain a forest of rooted trees, under
the following operations:
\begin{description}
\item[$\proc{union}(a,b)$:] assume $a$ is the root of a tree, and $b$
lies in a different tree; this operation creates an edge from $a$ to
$b$, so that $a$ is no longer a root.
\item[$\proc{find}(a)$:] return the root of the tree containing $a$.
\end{description}
Incremental connectivity is easy to implement:
\begin{description}
\item[$\proc{connected}(u,v)$:] answer true iff $\proc{find}(u) =
\proc{find}(v)$.
\item[$\proc{insert}(u,v)$:] if $\proc{connected}(u,v)$, ignore this
edge. Otherwise, run $\proc{union}(\proc{find}(u), v)$.
\end{description}
You should know that union-find can be solved in a running time given
by the inverse Ackerman function, which is very-very close to
constant. However, this running time is only amortized.
\bigskip
{\bf Prove the following:} For any given $b$ satisfying $b =
\Omega(\lg_b n)$, one can support \proc{union} in $O(b)$ time, and
\proc{find} in $O(\lg_b n)$ time, where both running times are
worst-case.
\bigskip
It is known that this tradeoff is tight, so there is a very
interesting separation between what is possible with and without
amortization.
\end{document}