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

\head{1390}{Algorithms}{Winter 2000}{13 March 2000}{19}

\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 & & 40 \\ \hline
2 & & 60 \\ \hline
3 & & 40 \\ \hline
4 & & 40 \\ \hline
5 & & 80 \\ \hline
6 & & 40 \\ \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. (40 points) \Hspace} Derive tight upper and lower
bounds for the following recurrence relation.  You may assume that
$T(n)$ is constant for $n \le 4$.

\[T(n) = T(n/4) + T(3n/4) + 4n.\]

\newpage

{\bf Problem~2. (30 + 30 = 60 points) \Hspace} We are given two lists
$X$ and $Y$, each containing $n$ numbers.
\begin{itemize}
\item[{\bf (a)}] Design an efficient algorithm to find whether $X$ and
  $Y$ have an element in common.  Analyze the running time of your
  algorithm.  The more efficient your algorithm is in terms of its
  {\em worst-case}\/ running time, the more credit you will get.

\vfill

\item[{\bf (b)}] Design an algorithm for the same problem with smaller
  {\em expected}\/ running time.  Analyze the running time of your
  algorithm.

\vfill
\end{itemize}

\newpage

{\bf Problem~3. (40 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


{\bf Problem~4. (40 points) \Hspace} Let $G$ be a given weighted undirected graph.
Let $T_1$ and $T_2$ be two minimum spanning trees of $G$ that differ
in only one edge.  Let $e_1$ be the edge in $T_1$ that is not in $T_2$
and $e_2$ be the edge in $T_2$ that is not in $T_1$.  Prove or
disprove the following statement: The cycle obtained when $e_1$ is
added to $T_2$ contains $e_2$.
\vfill

\newpage

{\bf Problem~5. (30 + 50 = 80 points) \Hspace} 
\begin{itemize}
\item[{\bf (a)}] Give an example of a directed graph, that includes
  negative-weight edges, for which Dijkstra's algorithm for shortest
  paths produces incorrect answers.  Explain why.

\newpage

\item[{\bf (b)}] 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 probability that the
  link will not fail.  (Thus, the weight of every edge is a real
  number in $[0,1]$.)  The probability that a given path will not fail
  equals the product of the probabilities that the individual links of
  the path will not fail.
  
  Design and analyze an efficient algorithm to determine the {\em most
    reliable path}\/ (that is, the path with the highest probability
  of not failing) from a given node $s$ to a given node $t$.  If no
  path from $s$ to $t$ exists, then your algorithm must indicate so.
\end{itemize}

\newpage

{\bf Problem~6. (40 points) \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.  Give a greedy
algorithm for computing an optimal pairing.  Analyze the running-time
of your algorithm.
\end{document}

