\documentstyle[12pt,handout]{article}
\begin{document}
\input{macros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\head{3390}{Analysis of Algorithms}{16 December 1998}{28}

\begin{center}
\Large{{\bf Final}} 
\end{center}

{\bf Instructions.}
\begin{Itemize}
\item
The answerscripts are due by 10 P. M. today in my office (113 Cullinane).
This is a hard deadline!

\item
This exam consists of two parts.  Part~A, which is worth a total of 40
points, contains short-answer problems.  Every problem in Part~B, which is
worth a total of 60 points, asks you to design an algorithm.  There is also
a bonus problem worth 10 points.

\item 
While describing an algorithm, you may use any of the algorithms covered in
class or in the text as a subroutine.  You need to provide a proof of
correctness and/or an analysis of the running time only for those problems
where they are explicitly required.

\item
Show your work, as partial credit will be given.  If you need extra space, use
the blank facing page.  

\item
There should be absolutely no collaboration on the exam!  If you have any
questions or clarifications, please ask me.

\item
Best of luck!
\end{Itemize}

\vfill

{\large
\begin{center}
\begin{tabular}{||c|c|c|c||}\hline
Part & Problem & Score & Maximum \\ \hline
& 1 & & 15 \\ \cline{2-4}
A & 2 & & 10 \\ \cline{2-4}
& 3 & & 15 \\ \hline
& 4 & & 15 \\ \cline{2-4}
B & 5 & & 15 \\ \cline{2-4}
& 6 & & 15 \\ \cline{2-4}
& 7 & & 15\\ \hline
Bonus & 8 & & 10\\ \hline
Total & & & 100 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

\begin{center}
{\bf Name:} {\vrule height0.4pt width3in}
\end{center}
\vfill
\vfill

\newpage

\begin{center}
\large{{\bf Part~A}} 
\end{center}

{\bf Problem~1. (15 points total)} 
\begin{Itemize}
\item[{\bf (a) (7 points)}\Hspace] 
Arrange the following functions in order from the slowest growing function to
the fastest growing function.  You may simply state the answer without any
additional justification.  ({\em Hint:} Express each function as a power of
$2$.)

\[ 
n^{\lg n} \hs (\lg n)^n \hs n^{100} \hs 2^{\sqrt{\lg n}}
\]

\vfill

\item[{\bf (b) (8 points)}\Hspace]
Using the iteration method, derive the asymptotic growth rate of the solution
for the following recurrence.  Assume that $T(n)$ is $\Theta(1)$ for $n\le 2$.

\[ T(n) = T(n/2) + \lg n.\]

\vfill
\vfill
\end{Itemize}
\newpage

{\bf Problem~2. (10 points total)\Hspace} 
\begin{Itemize}
\item[{\bf (a) (5 points)}\Hspace] 
Let $T$ be an $n$-node red-black tree that has no red nodes.  What is the
height of $T$?  What is the maximum number of rotations that might be
performed when a new record is inserted into $T$ using the insertion routine
given in the text?  Briefly justify your answers.

\vfill

\item[{\bf (b) (5 points)}\Hspace]
Give an optimal Huffman code for an $n$-character data file in which the
frequency of the $i$th character is $2^i$.  (You may simply state the answer
without any additional justification.)
\vfill
\end{Itemize}
\newpage

{\bf Problem~3. (15 points total)\Hspace} For each of the following statements, indicate
whether it is true or false.  Briefly justify your answers.
\begin{Itemize}
\item[{\bf (a) (5 points)\Hspace}] 
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$.

\vfill

\item[{\bf (b) (5 points)\Hspace}] 
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$.

\vfill

\item[{\bf (c) (5 points)\Hspace}]
At the end of every phase of the Bellman-Ford algorithm (as described in the
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.  )

\vfill
\end{Itemize}

\newpage

\begin{center}
\large{{\bf Part~B}} 
\end{center}

{\bf Problem~4. (15 points total)\Hspace} 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) (2 points)\Hspace}]
Give an $O(1)$ time algorithm to find the maximum of a given bitonic sequence.

\item[{\bf (b) (8 points)\Hspace}]
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) (5 points)}\Hspace]
Give an $O(\lg n)$ time algorithm to find the median of a given bitonic
sequence.  ({\em Hint:} Use part~(b).)
\end{Itemize}

\newpage

\newpage

{\bf Problem~5. (15 points total)\Hspace} 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) (10 points)}\Hspace]
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) (5 points)} \Hspace]
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}

\newpage

{\bf Problem~6. (15 points total)\Hspace} A {\em hamiltonian path}\/ of a
directed graph $G$ is a simple path in $G$ that visits every vertex in $G$
exactly once.
\begin{Itemize}
\item[{\bf (a) (8 points)}\Hspace] 
Design a linear time algorithm to determine whether a given directed acyclic
graph has a hamiltonian path.

\item[{\bf (b) (7 points)}\Hspace]
Prove that a directed acyclic graph $G$ has a hamiltonian path if and only if
$G$ has exactly one topological sort.
\end{Itemize}

\newpage

{\bf Problem~7. (15 points)\Hspace} One can model a communication network by
a weighted directed graph $G$, in which the vertices of $G$ represent the
nodes of the network, the edges of $G$ represent the communication links of
the network and the weight of an edge is the bandwidth of the link.  We define
the {\em effective bandwidth}\/ of a path $p$ as the bandwidth of the
minimum-bandwidth link in $p$.  

Design and analyze an efficient algorithm to determine a path with the largest
effective bandwidth from a given node $s$ to a given node $t$.  If no path
from $s$ to $t$ exists, then your algorithm must indicate so.  Briefly justify
the correctness of your algorithm.  (Assume that the bandwidth of every link
is positive.)

\newpage

\begin{center}
\large{{\bf Bonus Problem}} 
\end{center}

{\bf Problem~8. (10 points)\Hspace} Two art thieves share a collection of $n$
paintings.  They have agreed on a value for each painting, say $x_1$, $x_2$,
\ldots, $x_n$.  They would like to split the paintings into two halves of
equal value.  

Design an algorithm that determines whether it is possible for the thieves to
fairly split the paintings.  Your algorithm should run in $O(n T)$ time, where
$T$ is the sum of the $x_i$'s.

\junk{
{\bf (10 points total)\Hspace} Assume we are given a supply of two-input,
one-output gates, most of which are OR gates and some of which are AND gates.
Unfortunately the OR and AND gates have been mixed together and we can't tell
them apart.  For any integer $k\geq 0$, we would like to construct a
two-input, one-output ``$k$-OR'' circuit from our supply of two-input, one
output gates such that the circuit satisfies the following property: If at
most $k$ of the gates in the circuit are AND gates then the circuit correctly
implements OR.
\begin{Itemize}
\item[{\bf (a) (1 point)}\Hspace]
Design a 0-OR circuit.
\vfill

\item[{\bf (b) (3 points)}\Hspace]
Design a 1-OR circuit using three gates.  Briefly justify your
construction.
\vfill
\vfill

\item[{\bf (c) (3 points)}\Hspace]
For $k>0$, show how to build a $2^k$-OR circuit out of three $2^{k-1}$-OR
circuits.  Briefly justify your construction.
\vfill
\vfill

\item[{\bf (d) (3 points)}\Hspace]
State a $\Theta$-bound (in terms of the parameter $k$) for the number of gates
in a $2^k$-OR circuit constructed using the recurrence suggested in parts~(a)
through~(c) above.
\vfill
\vfill
\end{Itemize}
}
\end{document}
