
\documentclass[12pt]{article}
\usepackage{fullpage}


\begin{document}
\begin{center}
\bf 
CS 141, Advanced Topics in Algorithms \\
Spring 2004\\
Homework 4a  \\
Due Monday,  February 11
\end{center}
\vspace{0.5cm}

\begin{enumerate}

\item \textbf{[20 Points] The Dynamic List Access Problem.}
In class we looked at the MTF online algorithm for the List Access
Problem.  Specifically, we looked at the \textbf{Static} List Access
Problem where only FINDs were allowed - there were no INSERT and DELETE
operations permitted in the request sequence.

Now, consider the more general \textbf{Dynamic} List Access Problem which
differs from the static version in three ways:
  \begin{enumerate}
    \item Any FIND operation may fail.  That is, the item might not be
found.  In this case, the actual cost is $\ell + 1$ where $\ell$ was the
length of the list at the time that the FIND was performed. 

    \item INSERT operations are permitted in the request sequence.  An
inserted object is placed at the end of the list.  If the length of the
list prior to the INSERT was $\ell$, then the actual cost of this
operation is $\ell + 1$.  After inserting the element at cost $\ell + 1$,
you may move it to any position earlier in the list at no cost (just like
in a successful FIND operation).

   \item DELETE operations are permitted in the request sequence.  The
cost of the DELETE is simply the cost of finding the object.  (However,
the potential function changes as a consequence of the DELETE, so a
DELETE differs from a FIND in this way!)
  \end{enumerate}

Describe a modification of the MTF algorithm to handle all three of these operations.
Show that when your modified MTF algorithm is applied to the Dynamic List Access Problem, it
still maintains a competitive ratio of 2.  (That is, it is 2-competitive
with respect to an optimal offline algorithm.)

\end{enumerate}
\end{document}



