\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 4} \quad {\em Due: Thursday, Mar.\ 15}
\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{Cache-oblivious median finding.}

Given an unordered array of $N$ elements, develop and analyze a cache-oblivious algorithm to find the median of the array in $O(\lceil N/B \rceil)$ memory transfers.  In your solution, you may assume knowledge of the standard median-of-medians deterministic selection algorithm.

\paragraph{Cache-oblivous queue.}

Develop and analyze a cache-oblivious FIFO queue.  Both the {\tt{enqueue}} and the {\tt{dequeue}} operation should take $O(1/B)$ amortized memory transfers.  Your data structure should only use external memory indices in $\{0,1,\cdots,O(N)\}$, where $N$ is the maximum number of elements stored in the queue at once.

\end{document}
