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

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'12)} \\[1ex]
{Prof.~Erik Demaine \qquad TAs: Tom Morgan, Justin Zhang} \\[2ex]
\framebox{Problem 6} \quad {\em Due: Thursday, Apr.\ 5}
\end{center}

Be sure to read the instructions on the assignments section of the
class web page.  Remember to keep your solutions to one page!

\paragraph{Concise van Emde Boas.}

Develop and analyze a data structure that supports insert, delete, successor and predecessor in the word-RAM model in $O(\lg\lg u)$ worst-case time.  Your data structure should use $O(u)$ bits of space.  Note that the van Emde Boas data structure from lecture used $\Theta(u)$ words of space, and thus $\Theta(u \lg u)$ bits of space.

\paragraph{Union-Split-Find.}

Develop and analyze a word-RAM data structure to maintain a set of disjoint intervals of the form $[a,b)$ such that $a, b \in \mathcal{U}$.  Your data structure should support the following operations in $O(\lg \lg u)$ time:

\begin{itemize}
\item {\tt make}$(a, b)$ : Create the interval $[a,b)$ (must not overlap existing intervals).
\item {\tt union}$(a, b, c)$ : Merge the adjacent intervals $[a,b)$ and $[b,c)$ into $[a,c)$.
\item {\tt split}$(a, b, k)$ : For $k \in [a,b)$, split the interval $[a,b)$ into $[a,k)$ and $[k,b)$.
\item {\tt find}$(k)$ : Return the interval $[a,b)$ that contains $k$, or report that no interval contains $k$.
\end{itemize}

\end{document}
