\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}{8 March 2001}{20}

\begin{center}
\Large{{\bf 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 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 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}

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

\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)$.
\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 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.)

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

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

\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$.
\end{Itemize}
\end{document}

