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

\head{1390}{Algorithms}{Winter 1999}{17 March 1999}{24}

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

{\bf Instructions.}
\begin{Itemize}
\item
This is a 120 minute final worth a total of 300 points.

\item
Read all the problems through first and attack them in the order that allows
you to make the most progress.

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

\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 only for those problems where they are explicitly required.  

\item
Your grade on any problem that asks you to design an algorithm will be
determined on the basis of its correctness, running time, and the clarity of
the description.

\item
Best of luck!
\end{Itemize}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 30 \\ \hline
2 & & 30 \\ \hline
3 & & 40 \\ \hline
4 & & 60 \\ \hline
5 & & 70 \\ \hline
6 & & 70 \\ \hline
Total & & 300 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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


\newpage


{\bf Problem~1. (30 points) \Hspace}  Solve the following recurrence. 
\[T(n) = 9T(n/4) + n^2.\]

\vfill

{\bf Problem~2. (30 points) \Hspace} Determine the heap that is obtained after
calling {\sc Build-Heap} on the array $A = [3, 2, 5, 12, 8, 6]$.  (You may
simply state the final result without any additional justification.)

\vfill

\newpage


{\bf Problem~3. (40 points) \Hspace} Given an unsorted list $S$ of $n$ numbers and an
integer $k \le n$, design an efficient algorithm to list the $k$ smallest
numbers in $S$ in sorted order.  Analyze the worst-case running time of your
algorithm.

\newpage

{\bf Problem~4.} \Hspace For each of the following statements, indicate whether it is
true or false.  Briefly justify your answers.

\begin{Itemize}
\item[{\bf (a) (30 points) \Hspace}]
If vertex $u$ appears before vertex $v$ in the topologically sorted order of a
directed acyclic graph $G$, then there is a directed path from $u$ to $v$ in $G$.
\vfill

\item[{\bf (c) (30 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
\end{Itemize}

\newpage

{\bf Problem~5. (70 points) \Hspace} Give an efficient algorithm to determine
the longest common subsequence of three given sequences of length $m$, $n$,
and $p$, respectively.  Analyze the worst-case running time of your algorithm.

\newpage

{\bf Problem 6. (70 points) \Hspace} Let a directed graph $G=(V,E)$ be given.  Further
assume that each vertex has been assigned a color, either red or blue.  A
directed path in $G$ is called an {\em alternating red-blue path}\/ if and
only if no two consecutive vertices on the path have the same color.  Give an
efficient algorithm that determines for {\em all}\/ pairs of vertices $u,v$ in
$V$ whether $v$ is reachable from $u$ via an alternating red-blue path.
Briefly justify the correctness of your algorithm and analyze its worst-case
running time.
\end{document}

