\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\num}[1]{\mbox{{\em num}}[#1]}
\newcommand{\numnoargs}{\mbox{{\em num}}}
\newcommand{\btrsearch}{{\sc B-Tree-Search}}

\head{3390}{Analysis of Algorithms}{Spring 1999}{2 June 1999}{24}

\begin{center}
\Large{\bf Practice Problems}
\end{center}

{\bf 1.} A {\em bitonic}\/ sequence is a sequence of numbers that
monotonically decreases and then monotonically increases.  That is, a sequence
$X = x_1, x_2, \ldots, x_n$ is bitonic if there exists a $t$ in $[1, n]$ such
that $x_{i+1} < x_i$ for $1 \le i < t$ and $x_{i+1} > x_i$ for $t \le i < n$.
\begin{Itemize}
\item[{\bf (a)}]
Give an $O(1)$ time algorithm to find the maximum of a given bitonic sequence.

\item[{\bf (b)}]
Give an $O(\lg n)$ time algorithm to find the minimum of a given bitonic
sequence of length $n$.  Briefly justify the correctness of your algorithm.

\item[{\bf (c)}]
Give an $O(\lg n)$ time algorithm to find the median of a given bitonic
sequence.  ({\em Hint:} Use part~(b).)
\end{Itemize}

{\bf 2.} A group of $n$ men and $n$ women are attending a dance class.  The
instructor wants to pair each man with a woman in such a way that the sum of
the absolute value of the height differences between partners is minimized.
\begin{Itemize}
\item[{\bf (a)}]
Let $A$ be a tallest woman in the class (there could be a tie), and let $B$ be
a tallest man.  Prove that there is an optimal pairing in which $A$ is paired
with $B$.

\item[{\bf (b)}]
Based on the result of part~(a), give a greedy algorithm for computing an
optimal pairing.  Analyze the running time of your algorithm.
\end{Itemize}

{\bf 3.} For each of the following statements, indicate whether it is true or
false.  Briefly justify your answers.
\begin{Itemize}
\item[{\bf (a)}] 
If $T$ is a minimum spanning tree of a weighted undirected graph $G$, then the
unique path connecting any two vertices $u$ and $v$ in $T$ is a shortest path
between $u$ and $v$ in $G$.

\item[{\bf (b)}] 
If $T$ is a minimum spanning tree of a weighted undirected graph $G$, then the
minimum-weight edge of $T$ is also a minimum-weight edge of $G$.

\item[{\bf (c)}]
At the end of every iteration of the Bellman-Ford algorithm (that is, t the
end of every iteration of the for-loop on line 2 of the pseudocode on page 532
of text), the inequality $d[v] \le d[u] + w(u,v)$ holds for every edge $(u,v)$
of the graph.  (Assume that $G$ has no negative weight cycles.)
\end{Itemize}

{\bf 4.} Problem~25--2.

{\bf 5.} A group of reporters want to cover a set of sporting events in an
Olympiad.  The sports events are held in several stadiums throughout a city.
We know the starting time and ending time of each event, and the stadium where
it is held.  We are also given the travel time between different stadiums.
Design a polynomial-time algorithm to determine the least number of reporters
needed to cover these events.  ({\em Hint:} Given a positive integer $k$,
determine whether $k$ reporters suffice by solving an appropriate network flow
problem.)


\end{document}