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

\newcommand{\ins}{{{\sc Insert}}}
\newcommand{\del}{\mbox{{\sc Delete}}}
\newcommand{\suc}{\mbox{{\sc Successor}}}
\newcommand{\pred}{\mbox{{\sc Predecessor}}}
\newcommand{\search}{\mbox{{\sc Search}}}
\newcommand{\maxi}{\mbox{{\sc Maximum}}}
\newcommand{\mini}{\mbox{{\sc Minimum}}}
\newcommand{\subtreemin}{\mbox{\sc SubtreeMin}}
\newcommand{\rt}{\mbox{\em root}}

\head{1390}{Algorithms}{Winter 2001}{13 March 2001}{23}

\begin{center}
\Large{{\bf Solution to Practice Final}} 
\end{center}

{\bf Problem~1. (20 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/2) + T(n/3) + 4n.\]

{\bf Answer:} Use the iteration tree method.  The first level
contributes $4n$.  The second level contributes $10n/3$, the third
$25n/9$, etc.  The ratio between the contribution of successive levels
is $5/6 < 1$.  Therefore, we have $T(n) \le 4n (1 + 5/6 + (5/6)^2 +
\ldots) = 24n$.  That is, $T(n) = O(n)$.  We also have $T(n) \ge 4n$.
Therefore, $T(n) = \Theta(n)$.

{\bf Problem~2. (30 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.  (Note that both $k$ and
$n$ are parameters.)

{\bf Answer:} First, we invoke the linear-time selection algorithm to
find the element of rank $k$.  Then, we partition the list $S$ around
this element of rank $k$.  We thus have the subset of the $k$ smallest
numbers.  We now sort these.  The total running time is $O(n + k\log
k)$ ($O(n)$ for selection and $O(k \log k)$ for sorting).


{\bf Problem~3. (20 + 40 = 60 points)} \Hspace 
\begin{itemize}
\item[{\bf (a)}] Label the following binary tree with numbers from the
set $\{6, 22, 9, 14, 13, 1, 8\}$ so that it is a legal binary search
tree.  Assign a red or black color to each node so that it is a valid
red-black tree.

\vspace{.1in}

{\bf Answer:} 

\centerline{\epsfxsize=4in \epsffile{sbst.eps}}

Color 13, 14, 1, and 9 as black and the remaining as red.

\item[{\bf (b)}] Recall that all of the binary search tree operations
  studied in class, namely, \ins, \del, \search, \maxi, \mini, \suc,
  and \pred\ take $O(h)$ time in the worst-case, where $h$ is the
  height of the binary tree.  In this exercise, we would like to
  augment the binary search tree in such a way that the operation
  \mini\ can be calculated in $O(1)$ time.
  
  We add a new field called $\subtreemin[x]$, which stores for each
  node $x$ the minimum key value among all of the nodes in the subtree
  rooted at $x$.  This way, for a given binary search tree $T$, we can
  perform $\mini[T]$ by simply returning $\subtreemin[\rt[T]]$.
  
  Describe how to modify the \ins\ and \del\ operations so as to
  maintain the $\subtreemin[\cdot]$ field and yet keep the worst-case
  running time of the operations to be $O(h)$.

  {\bf Answer:} For inserting key $k$, just go through the path as in
  regular insertion, and change the $\subtreemin[x]$ value at any node
  $x$ to $k$ if $k$ is smaller than $\subtreemin[x]$.  Finally, when a
  new (leaf) node is created with key $k$, initialize the
  $\subtreemin$ field for this node to be $k$.  This modification adds
  only a constant number of operations per level to the original
  insert algorithm; hence the running time is still $O(h)$.
  
  For deleting, we consider three different cases. If the deleted
  node, say $x$, is a leaf node, then we trace the path from $x$ to
  the root until we reach the first node $y$ such that $y$ is the
  right child of its parent.  During this traversal, we update the
  $\subtreemin$ value for each node traversed (until and including
  $y$) to be the key of the parent of $x$.
  
  If the node to be deleted, say $x$, has only one child, then we
  delete the node as usual and set its child, say $u$ to be a child of
  the parent of $x$.  Then, as in the above case, we trace the path
  from $u$ to the root until we reach the first node $y$ such that $y$
  is the right child of its parent.  During this traversal, we update
  the $\subtreemin$ value for each node traversed (until and including
  $y$) to be the $\subtreemin$ value in $u$.
  
  Finally, if the node to be deleted, say $x$, has both children, one
  approach is to delete the node and replace it by the predecessor,
  then set the $\subtreemin$ value for the replacement node to be the
  minimum of the predecessor key and the $\subtreemin$ value stored in
  the left child of $x$ in the original tree.
\end{itemize}


{\bf Problem~4. (30 points)} \Hspace A {\em hamiltonian path}\/ of a
directed graph $G$ is a simple path in $G$ that visits every vertex in
$G$ exactly once.  Design a linear time algorithm to determine whether
a given {\em directed acyclic graph}\/ has a hamiltonian path.  ({\em
Hint:} Use topological sort.)

{\bf Answer:} Obtain a topological sort of the graph $G$.  Let $v_1,
v_2, \ldots, v_n$ denote the sequence of vertices in the topologically
sorted order.  A hamiltonian path exists if and only if there exists a
directed edge $(v_i, v_{i+1})$ for each $i$, $1 \le i < n$.  We go
through the vertices in sequence and check whether these edges exist.
If all of these exist, then the graph is hamiltonian; otherwise, not.

The topological sort takes linear time.  So does the walk through the
vertices in topological order and the check for the particular edges.
Therefore, the algorithm is linear-time.

{\bf Problem~5. (4 $\times$ 15 = 60 points)} \Hspace For each of the
following statements, indicate whether it is true or false.  Briefly
justify your answers.

\begin{Itemize}
\item[{\bf (a)}] A breadth-first search of an undirected connected
graph yields no cross edges.  (Recall that an edge is labeled as a
cross edge if it is between two vertices that do not share an
ancestor-descendant relationship.)

{\bf Answer:} False.  Consider a graph consisting of 3 vertices $u$,
$v$, and $w$, with edges $(u,v)$, $(v, w)$, and $(u, w)$.  A
breadth-first search starting from $u$ would classify the edge $(v,w)$
as a cross edge.

\item[{\bf (b)}] An undirected graph with $n$ vertices has a cycle if
and only if it has at least $n$ edges.

{\bf Answer:} False.  The ``if'' part is true but the ``only if'' part
is not.  We first prove the ``if'' part by induction on $n$.  For the
base case, we consider $n = 2$.  With 2 vertices and 2 edges (both the
same), we have a cycle.  Suppose the claim is true for graphs with
$n-1$ vertices.  Consider a graph $G$ consisting of $n$ vertices and
at least $n$ edges.  We consider two cases.  If there exists a vertex
with degree 1, then we remove the vertex and the incident edge to
obtain a new graph with $n - 1$ vertices and at least $n - 1$ edges,
which by the induction hypothesis has a cycle.  Otherwise, all
vertices have degree at least $2$.  In this case, we can simply start
from an arbitrary vertex in $G$ and keep exploring new edges until we
return to a vertex that have already visited.  This is bound to
happen, since every vertex has at least two incident edges; so if we
reach that vertex via one edge, we can leave it via another.  Thus, we
have a cycle in $G$.

For the ``only if'' part, consider the graph with 4 vertices $A$, $B$,
$C$, and $D$ and 3 edges $(A, B)$, $(B, C)$, and $(A, C)$.  This has a
cycle.  Therefore, the ``only if'' part is not true.

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

{\bf Answer:} False.  Consider a graph with 4 vertices $A$, $B$, $C$,
and $D$ and 4 edges $(A, B)$, $(B, C)$, $(C, D)$, and $(A, D)$ with
weights $1$, $1$, $1$, and $2$, respectively.  The minimum spanning
tree consists of the edges $(A, B)$, $(B, C)$, and $(C, D)$.  In this
tree, the length of the path from $A$ to $D$ is $3$.  However, the
shortest path from $A$ to $D$ in the original graph is $2$.

\item[{\bf (d)}] 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$.
\end{Itemize}
\end{document}

