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

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


\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 9} \quad {\em Due: Monday, Apr. 30}
\end{center}

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

\paragraph{\boldmath Cache Oblivious Median Finding.}

Describe a cache-oblivious algorithm that, given an array of $N$
elements, not necessarily in sorted order, finds the $k$th smallest
element in $O(\lceil N/B \rceil)$ time. Notice that if $k = N/2$,
then the $k$th element is the \emph{median}.

It might be helpful to review the standard linear-time algorithm for
median finding (in CLRS, for example).

\end{document}