\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{11 March 1999}{22}

\begin{center}
\Large{\bf Practice Problems for Final Exam}
\end{center}

\bigskip

{\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.
\end{Itemize}

{\bf 2.}  Suppose we want to make change for $n$ cents using coins of
arbitrary denominations $d_r > d_{r-1} > ... > d_1 > d_0 = 1$.  We would like
to minimize the number of coins used.
\begin{Itemize}
\item[{\bf (a)}] Give an example of a set of denominations for which the
greedy algorithm studied in class does not work.

\item[{\bf (b)}] Design an $O(rn)$ time algorithm for the problem using dynamic
programming.
\end{Itemize}

{\bf 3.} Exercise~23.3--8.

{\bf 4.} Exercise~26.2--5.

{\bf 5.} Prove that a minimum spanning tree of a graph $G$ also minimizes the
maximum edge-weight over all spanning trees of $G$.  That is, prove that the
maximum edge-weight in a minimum spanning tree of $G$ is at most the maximum
edge-weight in any other spanning tree of $G$.

\end{document}