\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\input{epsf}

\newif\ifexam
%\examfalse
\examtrue

\ifexam
\newcommand{\answer}[1]{}
\else
\newcommand{\answer}[1]{{\bf Answer:} #1}
\fi

\ifexam
\head{CSU690}{Algorithms and Data}{Fall 2006}{December 1, 2006}{20}
\else
\head{CSU690}{Algorithms and Data}{Fall 2006}{November 7, 2006}{17}
\fi

\ifexam
\begin{center}
\Large{{\bf Makeup Midterm}} 
\end{center}
\else
\begin{center}
\Large{{\bf Sample Solution to Midterm}} 
\end{center}
\fi

\ifexam
{\bf Instructions.}
\begin{itemize}
\item This is a 90 minute midterm. 

\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
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 & & 25 \\ \hline
2 & & 12 \\ \hline
3 & & 8 \\ \hline
4 & & 5 \\ \hline
Bonus & & 6 \\ \hline
Total & & 50 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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

\newpage

\fi

{\bf Problem 1.  (5 $\times$ 5 = 25 points)} 
\begin{itemize}
\item[{\bf (a)}]
For all monotonically increasing functions $f(n)$ and $g(n))$, does
$f(n) = O(g(n))$ imply $\log(f(n)) = O(\log(g(n)))$?  Give a proof or a
counterexample.

\answer{False.  The relationship $f(n) = O(g(n))$ indicates that $f$'s
growth rate can exceed that of $g(n)$ by only a constant.  For
instance, if $g(n)$ is $n$, then $f(n)$ can be $n$, $2n$, $100n$, but
cannot be $n^2$ or $n\log n$.  A constant-factor blowup, however, when
applied to the exponent makes a huge difference.  Let $f(n) = 2n$ and
$g(n) = n$.  Then, we have $f(n) = O(g(n))$.  But $2^{f(n)} \neq
O(2^{g(n)})$ because
\[
\lim_{n\rightarrow \infty} \frac{2^{2n}}{2^n} = \lim_{n\rightarrow
\infty} 2^{n} = \infty.
\]
}
\vfill

\item[{\bf (b)}]
Solve the following recurrence relation.  (Assume that $T(1) = 1$.)
\[
T(n) = 3 T(n/3) + n.
\]
\answer{
\begin{eqnarray*}
T(n) & = & n + 2T(n/3)\\
& = & n + 2n/3 + 4T(n/9)\\
& = & n + 2n/3 + 4n/9 + 8T(n/27)\\
& = & n (1 + 2/3 + 4/9 + \ldots (2/3)^i + \ldots) + 2^{\log_3 n}T(1)\\
& = & n (1 + 2/3 + 4/9 + \ldots (2/3)^i + \ldots) + n^{\log_3 2}\\
& \le & \frac{n}{1-2/3} + n^{\log_3 2}\\
& = & 3n + n^{\log_3 2}\\
& = & O(n).
\end{eqnarray*}
Clearly $T(n) \ge n$, so $T(n) = \Omega(n)$.  We thus have $T(n) =
\Theta(n)$.

An alternative argument, using the recursion tree approach yields a
contribution of $n$ for the first level, $2n/3$ for the second, $4n/9$
for the third, and so we see a pattern.  Since this is a geometrically
decreasing series, the first term dominates the sum, and we obtain
$T(n) = \Theta(n)$.
}
\vfill

\newpage

\junk{

\item[{\bf (c)}]
Let $G$ be a undirected graph with distinct weights on the edges.  Let
$T$ be an MST and $(u,v)$ be an edge of $T$.  Is it true that for any
cut $C$ of $G$ that separates $u$ from $v$, $(u,v)$ is a
minimum-weight edge of the cut.  Give a proof or a counterexample.

\answer{ False.  Note that the cut property about MSTs refers to a
specific cut, for each edge of the MST.  So it does not apply here.
Consider a graph with three vertices, $u$, $v$, and $x$, with two
edges $(u,v)$ and $(u,x)$ of weights $2$ and $1$, respectively.  There
is only one spanning tree, which is also an MST.  Consider the cut
with $\{u\}$ on one side and $\{v,x\}$ on the other.  The edge $(u,v)$
is not the min-weight edge in the cut.}

\newpage
}
\item[{\bf (c)}]
Recall the stable marriage problem.  We say a perfect matching $X$
over $n$ men and $n$ women has a {\em cycle}, if for some $k > 1$,
there exist $k$ men $M_1, \ldots, M_k$ and $k$ women $W_1, \ldots,
W_k$ such that (a) $M_i$ is matched to $W_i$, for all $1 \le i \le k$,
while (b) $M_1$ prefers $W_2$ to $W_1$, $M_2$ prefers $W_3$ to $W_2$,
\ldots, $M_{k-1}$ prefers $W_{k}$ to $W_{k-1}$, and $M_k$ prefers
$W_1$ to $W_k$.  

Prove or disprove: If a matching has a cycle, it cannot be stable.

\newpage


\item[{\bf (d)\hs}] If vertex $u$ appears before vertex $v$ in the
topologically sorted order of a directed acyclic graph $G$, then there
is a directed path from $u$ to $v$ in $G$.  
\vfill


\item[{\bf (e)\hs}] Let $T_1$ and $T_2$ be two minimum spanning
trees of a weighted undirected graph $G$.  Then the weight of the
maximum-weight edge of $T_1$ is the same as the weight of the
maximum-weight edge of $T_2$.
\vfill
\end{itemize}

\newpage

{\bf Problem 2. (12 points)} 

The {\em Fibonacci numbers}\/ are defined by the following recurrence:
\begin{eqnarray*}
F_0 & = & 0\\
F_1 & = & 1, \mbox{ and}\\
F_i & = & F_{i-1} + F_{i-2} \mbox{ for } i \ge 2.
\end{eqnarray*}

\begin{Enumerate}
\item[(a)] Prove using induction that for any $n \ge 2$, $F_n$ equals
$A^{n-1}_{1,1}$, where $A^n$ is the $n$th power of the following
matrix:
\[
A = \left( 
\begin{array}{cc}
1 & 1\\ 
1 & 0
\end{array}
\right).
\]

\newpage

\item[(b)] Use part~(a) to obtain an algorithm that computes $F_n$ in
$O(\log n)$ time.
\end{Enumerate}

\newpage

{\bf Problem 3. (8 points) \hs Job scheduling}  

A server has $n$ customers waiting to be served.  the service time
required by each customer is known in advance: $t_i$ minutes for
customer $i$.  So if, for example, the customers are served in order
of increasing $i$, then the $i$th customer has to wait $t_1 + t_2 +
\ldots t_i$ minutes.

We wish the minimize the total waiting time

\[
\sum_{i = 1}^n (\mbox{time spent waiting by customer }i).
\]
Give a polynomial-time algorithm for computing an optimal order in
which to process the customers.

\newpage

{\bf Problem 4. (5 points) \hs Alternating red-blue paths}

Let a directed graph $G=(V,E)$ be given.  Further assume that each
vertex has been assigned a color, either red or blue.  A directed path
in $G$ is called an {\em alternating red-blue path}\/ if and only if
no two consecutive vertices on the path have the same color.  Give a
polynomial-time algorithm that determines for {\em all}\/ pairs of
vertices $u,v$ in $V$ whether $v$ is reachable from $u$ via an
alternating red-blue path.  Analyze the worst-case running time of
your algorithm.

\newpage

{\bf Bonus Problem. (6 points) \hs }

Comparing two sequences of characters arises in several applications
including the life sciences and information retrieval.  Suppose you
are given two sequences of characters drawn from a common alphabet:
$S$ of length $m$ and $T$ of length $n$, each possibly containing a
character more than once.  We say that $S$ is a {\em subsequence}\/ of
$T$ if $S$ can be obtained from $T$ by deleting some characters from
$T$.  For instance, the sequence $A,T,C,T,G$ is a subsequence of
$G,\underline{A},A,A,\underline{T},\underline{C},G,G,\underline{T},T,\underline{G}$.

(Positions indicating the subsequence property are underlined.)

Give a polynomial-time algorithm that, given two sequences $X$ and
$Y$, determines the longest common subsequence of $X$ and $Y$.
Analyze the running time of your algorithm.
\end{document}

