\documentclass[12pt]{article}

\newtheorem{claim}{Claim}
  
\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 182} \\ Advanced Topics in Algorithms \\ Spring 2003 \\
Problem Set 4b \\ Due Tuesday, February 18 in class
\end{center}

\begin{enumerate}

  \item \textbf{[20 Points]  The Investment Problem!}
You've been hired as Chief Algorithms Officer
at the investment firm of Weil, Proffet, and Howe. 
(``Chief Algorithms Officer'' is a real job title at several big companies now!  Search Google on ``chief algorithms officer'' and you will find an astounding number of hits!)
 Here's your first task:  
Over the course of the next $n$ days, you will be presented each day with a share price 
for a particular company's stock.  Your company owns one share of that stock.   You must sell your share sometime during that $n$ day period. Your objective is to find the best sell date in that period.  Once you sell on a given day, the
game is over and you walk away with the value at which you sold the stock.  

Unfortunately, you get the share value data day-by-day.  You must either sell at the price quoted that day or take your chances and see what you are offered subsequently.  Fortunately, there is a known range on the value of that stock:  The stock is guaranteed (or in real life, perhaps ``confidently estimated'') to stay in the range $m$ to $M$, $m \leq M$.
  Moreover, if you haven't sold your stock at the end of the $n$ days (when the offers end) you may cash it in for its low value of $m$.

  Let $\phi = \frac{M}{m}$
(this ratio is sometimes called the ``global fluctuation ratio'').
\begin{enumerate}

    \item Describe a deterministic online algorithm for this problem.  Your algorithm should
    be strictly $\sqrt{\phi}$ competitive.  You may assume that you know $m$ and $M$.

    \item Assume that you are told $\phi$ but you are not given $m$ nor $M$. Show that
    no deterministic online algorithm can be better than $\phi$ competitive in this case.
  \end{enumerate}


  \item \textbf{[25 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.



\end{enumerate}
\end{document}