\documentclass[12pt]{article}

\newtheorem{claim}{Claim}

\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 181b} \\ Advanced Topics in Algorithms \\ Spring 2002 \\
Problem Set 3b \\ Due Tuesday, February 12 in class
\end{center}

\begin{enumerate}
  \item \textbf{[20 Points] LFD is an Optimal Offline Paging Algorithm.}
In class we mentioned that LFD (Longest-Forward-Distance) is an optimal
offline algorithm for the paging problem.  Recall that the algorithm
works as follows:   On each page fault, the algorithm evicts the page
from fast memory whose next request is latest.

It may seem intuitive that LFD is optimal, but intuition on these
problems is often misleading!  Here we'll prove the optimality of LFD
formally in two parts.

\begin{enumerate}
\item  First, consider the following claim:
\begin{claim}
Let ALG be any offline paging algorithm.  Without loss of generality (as
we saw in class!), ALG is a demand paging algorithm.  Let
$\sigma$ be any request sequence.  For any $i$, $1 \leq i \leq |\sigma|$,
it is possible to  construct another offline algorithm $\mbox{ALG}_i$ that
satisfies the following properties:
  \begin{enumerate}
    \item $\mbox{ALG}_i$ processes the first $i-1$ requests exactly as
does ALG.
    \item If the $i^{th}$ request in $\sigma$ is a page fault, then
$\mbox{ALG}_{i}$ evicts from memory the page with the longest forward
distance.
   \item $\mbox{ALG}_i(\sigma) \leq \mbox{ALG}(\sigma)$. 
  \end{enumerate}
\end{claim}

Prove this claim.  (\emph{Note:} To do so, you will want to specify how
$\mbox{ALG}_i$ behaves with respect to ALG after the $i^{th}$ request.)
Make sure that your proof is entirely rigorous.

\item Now show how the above claim can be applied repeatedly to prove that
LFD is optimal.
\end{enumerate}

\item \textbf{[15 Points] LFU and LIFO are not Competitive!}
Prove that LFU and LIFO are not competitive online paging algorithms.
LFU,  Least-Frequently-Used, is a demand paging algorithm which evicts
the page which has been used least since entering fast memory.
LIFO, Last-In-First-Out, evicts the page that was most recently moved
into fast memory.  To show that these algorithms are not competitive, you
must show that there is no constant $c$ for which these algorithm
are $c$-competitive.

\item \textbf{[15 Points] Conservative Paging Algorithms.}
An online paging algorithm using a fast memory of size $k$ is said to be
\textbf{conservative} if for any request sequence, every subsequence
containing
$k$ or fewer distinct page references incurs at most $k$ page faults.
(A subsequence is a consecutive sequence of requests.)

Note that the definition of a conservative algorithm is similar, but not
the same, as the definition of a marking algorithm.  Prove that every
conservative online algorithm is $k$-competitive.


\item \textbf{[20 Points] Adventures at Millisoft!}
You have been hired by Millisoft as Director of Advanced Algorithms
Design.  You answer directly to the big guy, Gill Bates.
Your first job is to help with the algorithmic issues on Millisoft's
new operating system, Portholes 1998, which will be released in the
very near future.  On the first day on the job, Gill comes to your office
sipping on a Diet Coke and sits in your bean bag chair.
``I'd like to add a feature to Portholes 1998,'' he says, taking a chug of
Diet Coke.  ``The user should be able to choose the paging algorithm that
they want to use when they first install Portholes.  Before we do this, we
need to know whether or not each paging algorithm is a marking algorithm
and whether or not it is a conservative algorithm.'' Fill in
Gill's table below, putting a ``Yes'' or ``No'' in each cell.  For any
cell that we ``filled in'' in class, you may just put the answer down
followed by a
$\star$ to indicate that this was already shown.  For each remaining
cell, fill in the answer and then give a careful and rigorous proof.  
If an algorithm is not a marking algorithm or is not conservative,
you should demonstrate how it can violate those definitions.

  \begin{center}
  {\large       
  \begin{tabular}{|l||c|c|}
        \hline
        Algorithm & Marking & Conservative\\
        \hline
        \hline
        {\sc lru}   &  &  \\
        \hline
        {\sc fifo}  &     &     \\
        \hline
        {\sc clock} &     &     \\
        \hline
        {\sc fwf}   &     &     \\
        \hline
  \end{tabular}}
  \end{center}








\end{enumerate}
\end{document}