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

\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 1} \quad {\em Due: Monday, Feb. 19}
\end{center}

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

\paragraph{\boldmath Move-To-Front Variations.}

The Move-To-Front heuristic moves the accessed item $x$ all the way
to the front of the list. In this question we examine the behavior
of Move To Front when the accessed item is moved forward but not all
the way to the front.

Prove that if we move the accessed item $x$ forward by a fixed number
of locations $k$, then the competitive ratio is not $O(1)$.
What is the worst-case competitive ratio?

In contrast, prove that if we move $x$ some fixed fraction of the
distance to the front (i.e., if $x$ is at index $i$ in the list and
our fixed fraction is $0 < r < 1$, we move $x$ exactly $\lceil
r\cdot i\rceil$ locations forward), then the performance of that
heuristic is within a constant factor of the optimal.  What
factor do you obtain?


\paragraph{\boldmath Splay Trees Bounds.}

Recall the \emph{working-set bound}: if $t_{i}(y)$ is the number
of distinct elements (including $y$) accessed since the last time
$y$ was accessed before time~$i$, then the amortized cost to access
$x_i$ is $O(1+\lg{t_i(x_i)})$.
%
This bound says that, if accesses concentrate on a smaller set of
elements (the working set), then the cost is logarithmic in this set,
not in~$n$.  Equivalently, the bound says that if you access
something you accessed recently, the access is cheap.

Also recall the \emph{entropy bound}: if element $x$ occurs $f_x$
times in a sequence of $m$ accesses, then the amortized cost to access
an element is $O({1 \over m} \sum_x f_x \lg (m/f_x))$.
For binary search trees, the entropy bound is equivalent to
static optimality, up to constant factors.

Prove that the working-set bound implies the entropy bound.


\end{document}