\documentclass[12pt]{article}

\newtheorem{claim}{Claim}
  
\usepackage{fullpage}
\begin{document}
\begin{center}
\textbf{CS 182} \\ Advanced Topics in Algorithms \\ Spring 2003 \\
Problem Set 5a \\ Due Thursday, February 20
\end{center}

\begin{enumerate}

 \item \textbf{[20 Points]  The Absent-Minded Professor.}
Professor Juan I. Dalean of the Massachusetts Institute of Zymurgy walks
out of his building one evening.  Unfortunately, he can't remember if he
parked his car up the street or down the street.  He wishes to use an
online algorithm to find his car which is competitive with an optimal
offline algorithm.  

More precisely, imagine that Professor Dalean is currently at a given
point on the line (the street).  The car is parked someplace on the line
some finite distance away from Dalean.  An optimal offline algorithm
would know the location of the car and would proceed directly there. 
An online algorithm doesn't know the position and must therefore search
for it.  The online algorithm is $k$-competitive if it eventually finds
the car and traverses a distance no larger than $k$ times the distance
traversed by the online algorithm.

Find a competitive online algorithm for this problem and carefully show
that competitive ratio is 9.


\end{enumerate}
\end{document}