\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts}
\usepackage{geometry}

\usepackage{epsfig}%
\usepackage{graphics}%
\usepackage{enumerate}


\geometry{letterpaper,tmargin=2.5cm,bmargin=2.5cm,lmargin=2.5cm,rmargin=2.5cm}%


\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'07)} \\[1ex]
{Prof.~Erik Demaine \quad\quad TA: Oren Weimann} \\[2ex]
\framebox{Problem 3} \quad {\em  Due: Monday, Mar. 5}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.

\paragraph{Dynamic connectivity with key values.}

Show how to modify the $O(\lg^2 n)$ dynamic connectivity data structure
by Holm, de Lichtenberg, and Thorup to maintain a key value in each node
subject to two operations:
\begin{itemize}
\item find-min$(v)$: find the minimum key of any node in the
                     connected component containing node~$v$.
\item set-key$(v,x)$: change the key stored in node $v$ to value~$x$.
\end{itemize}
The asymptotic cost of old operations should remain the same, and the
new operations should be supported as fast as possible.
(Assume that keys are totally ordered and can be compared in $O(1)$ time.)

\paragraph{Dynamic connectivity with path queries.}

Show how to modify the $O(\lg^2 n)$ dynamic connectivity data structure by
Holm, de Lichtenberg, and Thorup to support a \emph{path connectivity query}:
given two vertices $v$ and $w$, find a path between $v$ and~$w$,
or report that no such path exists.  This new query should be supported
in time $O(\lg n / \lg \lg n)$ time if there is no path and
$O(\lg n / \lg \lg n + k)$ time if the output path has length~$k$.


%\paragraph{Euler-Tours with key values.}
%In class we saw how Euler-Tour trees (ET-trees) can be used to
%maintain a forest and support cut($v$), link($v,w$) and
%findroot($v$) in $O(\lg n)$ time per operation. Suppose we also want
%to maintain key values on nodes and support the following
%operations:
%
%\begin{itemize}
%\item {\em find-min}($v$) find the minimum value node in the
%tree containing $v$.
%\item {\em decrease-key}($v,x$) decrease the value of node $v$
%to $x$
%\item
%{\em split}($v$) split the tree rooted at $v$ by deleting node
%$v$ (so all of the children of $v$ become new roots). Notice
%that this operation is different from cut($v$) which deletes the
%edge connecting $v$ and it's parent.
%\end{itemize}
%
%Show how to augment the ET-tree to service a sequence of $m$
%decrease-key operations, $m$ find-min operations, $m$ cut operations
%and $n$ splits on a forest with $n$ nodes in $O(m \lg n)$ time.
%(Assume $m>n$.)

%\paragraph{Dynamic Connectivity with key values.}
%
%We would next like to augment the dynamic connectivity data
%structure proposed by Holm et al.\ to maintain key values on nodes.
%Consider adding the following operations to the data structure:
%\begin{itemize}
%\item {\em find-min}($v$) find the minimum value node in the
%connected component containing $v$.
%\item {\em decrease-key}($v,x$) decrease the value of node $v$
%to $x$.
%\item {\em find-path}($v,w$) outputs a path connecting $v$ and $w$ if such a path
%exists. Otherwise outputs ``no path''.
%\end{itemize}
%
%Using the augmented ET-tree, show how to support find-min and
%decrease-key in $O(\lg n)$ time per operation (edge deletions should
%still take $O(\lg^2n$) time). Also, show that each find-path query
%can be done in $O(n)$ time if there exists a path and in $O(\lg n)$
%time if there is no path.


\end{document}