\documentclass[11pt]{article}
\usepackage{fullpage}
\usepackage{amsmath, amsfonts, amsthm}
\newtheorem{lemma}{Lemma}
\newcommand{\proc}[1] {\textnormal{\scshape#1}}
\newcommand{\poly} {\mathrm{poly}}
\newcommand{\eps} {\varepsilon}
\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 7} \quad {\em Due: Wednesday, Mar.~30}
\end{center}
{\bf Timing:} This problem is due after spring break. In the spirit of
not making you work during the break, we are making the problem due on
a Wednesday, so you can decide to only look at it after school
resumes.
\bigskip
{\bf Prove that} on a word RAM with $w$-bit words, one can sort $n$
$w$-bit integers in time $O(n \lg \frac{w}{\lg n})$. The algorithm can
be randomized (the time bound must hold in expectation).
\smallskip
{\em Hints:} Think of van Emde Boas, and find a way to reduce sorting
$n$ integers of $w$ bits to the problem of sorting $n$ integers on
$\frac{w}{2}$ bits. Bottom out the recursion in a linear-time sorting
algorithm (for $w = \lg n$). Note that you must reduce to a problem on
exactly (or at most) $n$ integers, not on $O(n)$ integers (if you
don't see why, brush up on your recursions). The only randomness
needed in the algorithm is through black-box use of hash tables.
\bigskip
In class, we saw that for $w = \Omega(\lg^{2+\eps} n)$, we can sort in
linear time. In general, the sorting time drops quickly when $w$
exceeds $\lg^2 n$. This problem shows that the sorting time also drops
quickly when $w$ approaches $\lg n$. Thus, the hardness of sorting is
concentrated in a very narrow interval for $w$: between $\lg^{1+\eps}
n$ and $\lg^2 n$. What happens in this interval remains an important
open problem.
\end{document}