\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 {Sample Solutions}
\end{center}

\paragraph{\boldmath Transposing a matrix.}

Consider a point set $\left \{ (x_i, i) \right \rbrace$ of $k^2$ points on a
$k^2 \times k^2$ lattice representing the access sequence. For each
point $(x_i, i)$ we introduce three new points at $(x_i - 1, i)$,
$\left ( k\left \lfloor \frac{x_i}{k} \right \rfloor, i \right )$ and
$\left ( k\left \lceil \frac{x_i}{k} \right \rceil, i \right )$.

The newly formed set is \emph{Aborally Satisfied}, hence it represents a
valid BST execution. The set contains $O(k^2)$, giving amortized cost
of $O(1)$ per access.

\paragraph{\boldmath Logarithmic redux.}

Consider the access sequence, the point set $X = \left \{ (x_i, i) \right
\}$ of $m$ points on a $n \times m$ lattice. Let $\hat{x}$ be the
median of all $x \in X$. Inserting $m$ points $(\hat{x}, i)$ will
ensure that each rectangle connecting a point left of or at $\hat{x}$
and a point right of or at $\hat{x}$ contains a point.

Now consider the two subsets of $X$, $X_{x \le \hat{x}}$ and $X_{x \ge \hat{x}}$,
each with at most $m$ points, and at most $\frac{n}{2}$
distinct $x$ values.

We recursively apply the same technique, to obtained point set that
is \emph{Aborally Satisfied}. We get the number of newly inserted
points by solving the recursion
$N(m, \frac{n}{2}) = 2N(m, \frac{n}{2}, n) + m$.

The total number of accesses is then
$O(N(m, n) + m) = O(m \log n + m) = O(m \log n)$.




\end{document}
