%% To students who wish to submit their homework in LaTeX format:
%%   Put your name(s) in the appropriate place.
%% Don't forget to include a statement with each problem indicating
%%   the contribution of each partner!

\documentclass[11pt]{article}

\usepackage{fullpage}

\newcommand{\solution}{\bigskip\hrule\bigskip}
\newcommand{\problembreak}{\bigskip\hrule\bigskip}

\begin{document}

\begin{center}
\Large CS4104 Fall 2010 Homework Assignment 5\\
Due at 11:00pm on Thursday, September 30\\
50 Points
\end{center}
\vspace*{0.10in}
\medskip

\textbf{Pledge:
I (we) have not received unauthorized aid on this assignment.
I (we) understand the answers that I (we) have
submitted.
The answers submitted have not been directly copied from another
source, but instead are written in my (our) own words.}

\bigskip
%PutYourNameHere, PutYourIDNumberHere
%Put second name/ID here if there is one

\paragraph{1.}
[25 points]
You are a robot facing an infinitely long wall and your task is to
find a door in the wall.
You are only allowed to walk along the wall to your left or to your
right and at any time you may turn and walk in the opposite direction.
Assume that the door is an (unknown, but finite) integer number of
steps away.

As a function of the (possibly unknown) distance to the door, what is
the minimum number of steps you have to walk to find the door in the
following situations.
(Note that "minimum number of steps" means the minimum number in the
worst case, that is, using the best algorithm that you can think of.
For each situation, you should describe the procedure that the robot
should follow, and analyze its cost.)

\begin{enumerate}
\item[(a)] You know that the door is to your left.
\item[(b)] You don't know where the door is but you know that it is
$n$ steps away.
\item[(c)] You don't know where the door is but you know that it is
within $n$ steps away.
\item[(d)] You neither know where the door is nor how far away.
\end{enumerate}


\paragraph{2.}
[25 points]
Find a way to add one additional pointer to each node of a
singly-linked list so that access to the $i$th element in a list of $n$
elements requires $O(\log n)$ time.

\end{document}
