\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 7} \quad {\em Due: Thursday, Apr.\ 12}
\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{Speeding up static van Emde Boas.}

In this problem we will develop a static data structure matching the $O\left(\lg \frac{w - \lg n}{a} \right)$ predecessor time bound mentioned in class.

\begin{enumerate}
\item Develop and analyze a data structure that supports successor and predecessor queries in the word-RAM model in $O\left(\lg (w - \lg n) \right)$ worst-case time using $O(n)$ space.
\item Develop and analyze a data structure that supports successor and predecessor queries in the word-RAM model in $O\left(\lg \frac{w}{\lg\lg n} \right)$ worst-case time using $O(n \log n)$ space.
\end{enumerate}

Neither of your data structures needs to support insertions or deletions.

\end{document}
