\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 3} \quad {\em Due: Thursday, Mar.\ 8}
\end{center}

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

\paragraph{Geometric basics.}

Recall that in class we introduced the geometric view for binary search tree execution.  Using only this view, prove that for any set of $m$ queries on $n$ items, there is a BST that will answer the queries in total time $O(m \lg n)$.  You should reason only about point sets, not about BSTs.

\paragraph{Working-set is harder.}

In class we introduced the \emph{entropy bound} and the \emph{working-set property} for BSTs.  The entropy bound holds if all searches in the BST have amortized time $O(\sum_{k=1}^n{p_k \lg\frac{1}{p_k}})$, where $p_k$ is the fraction of the time that key $k$ is queried.  The working-set property holds if the time to search for an element $x_i$ is $O(\lg{t_i})$, where $t_i$ is the number of elements queried since the last access to $x_i$.  Prove that any BST with the working-set property also has the entropy bound.


\end{document}
