\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{\ran}{\mbox{{\sc Rank}}}
\newcommand{\subtreenum}{\mbox{\sc SubtreeNum}}
\newcommand{\rt}{\mbox{\em root}}


\head{1390}{Algorithms}{Winter 2001}{15 March 2001}{24}

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

{\bf Instructions.}
\begin{Itemize}
\item This is a 120 minute final worth a total of 200 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 & & 20 \\ \hline
2 & & 30 \\ \hline
3 & & 60 \\ \hline
4 & & 50 \\ \hline
5 & & 40 \\ \hline
Total & & 200 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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


\newpage


{\bf Problem~1. (20 points) \Hspace} Consider the following sorting
algorithm.
\begin{tabbing}
{\sc New-Sort}$(A,p,s)$ \hs (to sort $A[p..s]$)\\
1. \= $n = s - p + 1$\\
2. \> If $n > 1$ \= then\\
3.\> \> $q \leftarrow p + \lfloor n/3 \rfloor$\\
4.\> \> $r \leftarrow p + \lfloor 2n/3 \rfloor$\\
5.\>\> {\sc New-Sort}$(A,p,q)$\\
6.\>\> {\sc New-Sort}$(A,q+1,r)$\\
7.\>\> {\sc New-Sort}$(A,r+1,s)$\\
8.\>\> Merge $A[p..q]$ and $A[q+1..r]$ and store the sorted result in
$A[p..r]$\\
9.\>\> Merge $A[p..r]$ and $A[r+1..s]$ and store the final sorted
result in $A[p..s]$ 
\end{tabbing}

Derive and solve a recurrence for the worst-case running time of {\sc
  New-Sort} on an array of $n$ elements.  You may ignore floors and
ceilings in your calculation.  

\newpage

{\bf Problem~2. (10 + 20 = 30 points) \Hspace} A {\em unimodal}\/
sequence is a sequence of numbers that monotonically decreases and
then monotonically increases.  That is, a sequence $X = x_1, x_2,
\ldots, x_n$ is unimodal if there exists a $t$ in $[1, n]$ such that
$x_{i+1} < x_i$ for $1 \le i < t$ and $x_{i+1} > x_i$ for $t \le i <
n$.  For example, $11, 9, 6, 5, 1, 4, 7$ is unimodal since the sequence
first decreases from $11$ to $1$ and then increases from $1$ to $7$.
\begin{Itemize}
\item[{\bf (a)}]
Give an $O(1)$ time algorithm to find the maximum of a given unimodal sequence.

\newpage


\item[{\bf (b)}] Give an $O(\lg n)$ time algorithm to find the minimum
of a given unimodal sequence of length $n$.

\newpage
\end{Itemize}

\newpage

{\bf Problem~3. (10 + 25 + 25 = 60 points) \Hspace} Suppose $S$ is a
list of numbers that is stored in a binary search tree.  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 consider a new operation: Given an element $x \in
S$, $\ran(x)$ returns the rank of element $x$ in $S$.  Recall that the
{\em rank}\/ of an element $x$ in $S$ is the position of $x$ in the
sorted list.  For example, if $S = \{5, 1, 3, 11, 9\}$, the rank of
$9$ is $4$.

We would like to augment the binary search tree in such a way that the
operation \ran\ can be performed in $O(h)$ time.  For this purpose, we
add a new field called $\subtreenum[x]$, which stores for each node
$x$ the total number of nodes (including $x$) in the subtree rooted at
$x$.

\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.  For each node, also fill in the value of the $\subtreenum$
field.  Write the number in the left cell and the $\subtreenum$ field
value in the right cell of each node.

\vspace{.4in}

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

\newpage

\item[{\bf (b)}] Given $x \in S$, describe how to calculate $\ran(x)$
in $O(h)$ time, using the $\subtreenum$ field values.

\newpage

\item[{\bf (c)}] Describe how to modify the \ins\ operation so as to
maintain the $\subtreenum[\cdot]$ field and yet keep the worst-case
running time of the operation to be $O(h)$.

\newpage
\end{itemize}

{\bf Problem~4. (20 + 30 = 50 points) \Hspace} Given a graph $G = (V,
E)$, we would like to determine whether there exists a vertex $v$ such
that every vertex in $G$ is reachable from $v$.  Design an efficient
algorithm for the problem in each of the following two cases.  In each
case, 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.

\begin{itemize}
\item[{\bf (a)}] The graph $G$ is undirected.

\newpage

\item[{\bf (b)}] The graph $G$ is directed.
\end{itemize}

\newpage

{\bf Problem~5. (20 + 20 = 40 points) \Hspace} For each of the following
statements, indicate whether it is true or false.  Briefly justify
your answers.

\begin{Itemize}
\item[{\bf (a)}] An undirected graph with $n$ vertices is a tree if
and only if it has exactly $n-1$ edges.


\junk{
\item[{\bf (b)}] For any connected weighted undirected graph $G$ with
distinct weights on its edges, every minimum spanning tree of $G$
contains the smallest weight edge of $G$.
}

\vfill

\item[{\bf (b)}] Let $G$ be a connected weighted undirected graph.
Let $T$ be a minimum spanning tree of $G$ and $T'$ be any other
spanning tree of $G$.  Let $e$ denote the edge with maximum weight in
$T$ and $e'$ denote the edge with maximum weight in $T'$.  Then, $w(e)
\le w(e')$.

\vfill
\end{Itemize}

\end{document}

