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

\begin{document}

\begin{center} \Large
{\scshape 6.851 Advanced Data Structures (Spring'10)} \\[1ex]
{Prof.~Erik Demaine \qquad Dr.\ Andr\'e Schulz \qquad TA: Aleksandar Zlateski} \\[2ex]
\framebox{Problem 1} \quad {\em Due: Thursday, Feb.\ 11}
\end{center}

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

\paragraph{\boldmath Transposing a matrix.}

Prove that there is a binary search tree supporting the access sequence
$0, k, 2 k, \dots, k^2 - k,
 1, k+1, 2 k+1, \dots, k^2 - k + 1,
 \dots\dots,
 k-1, 2 k-1, 3 k-1, \dots, k^2 - 1$
in constant amortized time per operation.
(This access sequence is equivalent to accessing a $k \times k$ matrix of
entries, in column-major order, when the items are stored in row-major order.)


\paragraph{\boldmath Logarithmic redux.}

Give a purely geometric argument that there is a binary search tree
supporting any $m$ searches on $n$ items in $O(m \log n)$ total time.
(Reason about point sets, not binary search trees.)


\end{document}
