\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\newif\ifanswer
\answertrue
\head{CS5800}{Algorithms}{Spring 2011}{14 February 2011}{8}

\begin{center}
\Large{\bf Quiz 2}
\end{center}

\noindent {\Large Name:~}\leaders\hrule\hfill\ 

\smallskip

{\bf (10 points) Selection in Bitonic lists}

You are working for an investment firm that prides on its analysis of
the past.  (You have heard this before!)  You have been regularly
asked to analyze historical data, which are being updated every minute
and hence result in huge lists (of the order of several millions).
One of the problems you repeatedly face is to find the minimum,
maximum, or median value in such a list.

Of course, you know that the maximum, the minimum, or, in fact,
element of any given rank, in any list can be computed in linear time.
But since the lists are huge, even linear time is prohibitively large.
Fortunately, most of the lists you analyze are {\em bitonic}: that is,
the list is composed of two contiguous (possibly empty) segments, the
first is an increasing segment and the second is a decreasing segment.

Formally, an array $A[1\ldots n]$ is bitonic if there exists an
integer $k$ , $1 \le k \le n$ such that for $1 \le i < k$, $A[i] <
A[i+1]$, and for $k \le i < n$, $A[i+1] < A[i]$.  For example, the
lists $[2, 4, 6, 7, 5, 3, 2]$ and $[1, 2, 5, 6, 8]$ are bitonic while
the list $[9, 10, 12, 10, 7, 8]$ is not bitonic.

For each of the following parts, {\em give an efficient algorithm for
  finding the desired element of an $n$-element bitonic list, and
  state the worst-case running time (as a function of $n$) of your
  algorithm.}  Note that the running-time is measured by the number of
basic arithmetic and logical operations and the number of list entries
that your algorithm accesses in the worst case.  For each part, make
your algorithm as efficient as you can, in terms of its worst-case
running time.  (You need not prove the correctness of your algorithm
or give an analysis of its running time.)

\begin{itemize}
\item[{\bf (a)}] {\bf (6 points)} Maximum element.

\newpage

\vspace*{2in}

\item[{\bf (b)}] {\bf (2 points)} Minimum element.

\vfill


\item[{\bf (c)}] {\bf (2 points)} Median element.  

\vfill

\vfill

\end{itemize}

\end{document}