\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}
