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

\newtheorem{claim}{Claim}

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

\begin{enumerate}
\item \textbf{[15 Points] Bellady's Anomaly Revisited.}
Recall that the class notes show a strange case in which the FIFO page replacement
algorithm actually does worse with a large fast memory than it does with a small fast memory.  That is,
given the same request sequence, a computer with smaller fast memory can actually incur fewer page
faults than a computer with larger fast memory when FIFO is used.
This is known as \emph{Bellady's Anomaly}.  Prove that the LRU algorithm does not have this anomaly.
Recall that LRU simply evicts the least recently used page from fast memory when a page fault occurs.

\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.

\end{enumerate}

\end{document}



