\documentstyle[12pt,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}}}

\head{3390}{Analysis of Algorithms}{Winter 2000}{14 March 2000}{16}

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

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

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

\item
There are 6 questions worth a total of 100 points.  In addition, there is a
bonus problem worth 10 points.

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

\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 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
Show your work, as partial credit will be given.  If you need extra space, use
the blank facing page.  

\item
Best of luck!
\end{Itemize}

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 10 \\ \hline
2 & & 15 \\ \hline
3 & & 15 \\ \hline
4 & & 15 \\ \hline
5 & & 15 \\ \hline
6 & & 15 \\ \hline
7 & & 15 \\ \hline
Bonus & & 10 \\ \hline
Total & & 100 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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

\newpage

{\bf Problem 1. (10 points) \hs } Derive an asymptotically tight bound for
the following recurrence.  Assume that $T(n)$ is $\Theta(1)$ for $n\le
4$.

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

\newpage

{\bf Problem 2. (10 + 5 = 15 points)\hs}
\begin{itemize}
\item[{\bf (a)}\hs] Is the operation of insertion in binary search
  trees ``commutative'' in the sense that inserting $x$ and then $y$
  into a binary search tree leaves the same tree as inserting $y$ and
  then $x$.  Argue why it is or give a counterexample.  Similarly,
  determine whether the operation of deletion is commutative.
 
\vfill
 
\item[{\bf (b)}\hs] Give an optimal Huffman code for a data file
  containing $n$ distinct characters, in which the $i$th character ($1
  \le i \le n$) occurs $2^i$ times.  (You may simply state the answer
  without any additional justification.)

\vfill
\end{itemize}  

\newpage

{\bf Problem 3. (3 $\times$ 5 = 15 points) \hs} For each of the
following claims, 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 minimum-weight edge of $T$ is also a minimum-weight edge of
$G$.

\vfill

\item[{\bf (b)}]  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

\item[{\bf (c)}] Let $G$ be a weighted directed graph and $s$ be a
  vertex in $G$.  Let $p$ denote a shortest path from $s$ to $t$.  If
  we increase the weight of every edge in the graph by $1$, then $p$
  remains a shortest path from $s$ to $t$.  
  
  \vfill
\end{Itemize}

\newpage

{\bf Problem 4. (15 points)\hs } We are given a set $S$ of $n$ numbers
that we would like to store in a binary search tree.  For each number
$x$ in $S$, we have a weight $p[x]$ which defines the probability that
a search will be issued for $x$.  We are given that $\sum_{x \in S}
p[x] = 1$; that is, every search is for a number in $S$.

For a given binary search tree $T$, the cost of a search for $x$ in
$T$ equals the depth $d_T[x]$ of $x$.  (Recall that the depth of a
node $u$ in a tree is the number of nodes along the path from the root
of $T$ to $u$.)  We define the {\em expected access cost} of the tree
$T$ to be $\sum_{x \in S} d_T[x] p[x]$.

Design an efficient algorithm to determine a binary search tree for
$S$ that minimizes expected access cost.  ({\em Hint:} Use dynamic
programming.)

\newpage

{\bf Problem 5. (15 points) \hs } An {\em arborescence}\/ of a
directed graph $G$ is a rooted tree in which there is a directed path
from the root to every vertex in $G$.  Design an efficient algorithm
to determine whether a given directed graph has an arborescence.
Analyze the worst-case running time of the algorithm.

\newpage

{\bf Problem 6. (15 points) \hs} We are given a set $S$ of $n$
activites that we would like to schedule among two lecture halls.  For
each activity, we have a start time $s_i$ and a finish time $f_i$.
Two activities that overlap in time may not be scheduled in the same
lecture hall; they may, however, be scheduled separately in the two
lecture halls.

Design a greedy algorithm to select a maximum-size set of activities
from $S$ that may be scheduled among the two lecture halls.  Briefly
justify the correctness of your algorithm.

\newpage 

{\bf Problem 7. (15 points) \hs } Given a weighted directed graph $G =
(V, E)$, a source $s \in V$, a destination $t \in V$, and an integer
$k$, design an efficient algorithm to determine the shortest path (if
it exists) from $s$ to $t$ containing at most $k$ edges.  Analyze the
worst-case running time of your algorithm.

\newpage

{\bf Bonus Problem (10 points) \hs} In order to find the rank of every
number in a given unordered list $S$ numbers, we need to sort $S$,
which implies a $\Theta(n \lg n)$ complexity in the worst-case.
Define the {\em log-rank} of an element $x$ in $S$ as the smallest
integer $i$ such that the rank of $x$ in $S$ is at most $2^i$.  For
example, if $S = \{5, 8, 1, 11, 3, 6, 7, 10, 15, 9, 19, 2, 4\}$, then
the log-rank of $6$ equals $3$ since the rank of $6$ is at least $2^2$
and at most $2^3$.

Design a linear-time algorithm to determine the log-rank of every
number in $S$.
\end{document}

