\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 Sample Solution for Final}} 
\end{center}

{\bf Problem 1. (10 points) } 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.\]

{\bf Answer:} The first-level contribution equals $n^2$, the
second-level $(n/2)^2 + (3n/4)^2 = 13n^2/16$.  The third level,
$n^2/16 + 9n^2/32 + 81n^2/256 = 169n^2/256$.  Thus, the total
contribution equals $\Theta(n^2)$.

{\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.
 
{\bf Answer:} The operation of insertion is not commutative.  Consider
inserting $x$ then $y$.  We get $x$ as the root, and $y$ as its child.
Now consider inserting $y$ then inserting $x$.  We get $y$ as the root
and $x$ as its child.

The operation of delete is also not commutative. 
 
\item[{\bf (b)}\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.)

{\bf Answer:} Same as for Fibonacci series.

\end{itemize}  

{\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$.
  
  {\bf Answer:} True.  Otherwise, we can add the minimum-weight edge
  of $G$ to $T$ and replace a higher-weight edge of $T$.
  
\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$.
  
  {\bf Answer:} True.  Otherwise, all edges in the cycle are also in
  $T_1$.

\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$.  
  
  {\bf Answer:} False.  
\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 the node $x$.  (Recall that the depth
of a node $u$ in a tree is the number of nodes along the path from the
root of the tree 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
storing $S$ with minimum expected access cost.  ({\em Hint:} Use
dynamic programming.)

{\bf Answer:} We sort the $n$ numbers.  Let $A[i,j]$ denote the
optimal cost for $S[i..j]$.  It is easy to see that 

\[ A[i,j] = \min\{A[i,k-1] + A[k+1,j] + j - i + 1\}.\]

Running time like matrix chain multiply.  $\Theta(n^3)$.

{\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.

{\bf Answer:} Perform a dfs traversal.  Keep track of the root of each
dfs tree.  Maintain a separate graph $G'$ in which the nodes are the
roots of the various dfs trees, and we add an edge from root $u$ to
root $v$ if we reach node $v$ while performing dfs-visit$[u]$.  Once
the whole dfs-traversal completes, we perform a dfs in $G'$ from the
last root.  If this dfs covers all the roots, then yes, else no.

Proof of correctness: If the algorithm returns yes, then clearly an
arborescence.  If the algorithm returns no, then there is no path from
any node in the dfs-tree, say $T$, of the final root to some other
root.  Therefore, no node in $T$ can be a root of an arborescence.
Furthermore, there is no path from any node outside $T$ to any node in
$T$.  Therefore, no node outside $T$ can be a root of an arborescence.

{\bf Problem 6. (15 points) \hs} The lecture hall problem. ({\em
  Hint:} Use activity selection.)

{\bf Answer:} Apply activity selection repeatedly until all lectures
are accomodated.  Optimal, since you can show the greedy choice is
there in some optimal solution.

{\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.

{\bf Answer:} The parallel version of Bellman-Ford.

{\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$.  Design a
linear-time algorithm to determine the log-rank of every number in
$S$.

{\bf Answer:} Find elements of rank $1$, $2$, $2^2$, \ldots,
$2^{\lfloor\lg n\rfloor}$.  Partition around these in the process.
Takes $O(n)$ time.
\end{document}

