\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}{Spring 1999}{9 June 1999}{27}

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

{\bf Instructions.}
\begin{Itemize}
\item
The answerscripts are due by 10 P. M. today in my office (113 Cullinane).
This is a hard deadline!

\item
{\bf There should be absolutely no collaboration on the exam}!  If you have
any questions or clarifications, please ask me.

\item
There are 6 questions worth a total of 100 points.  In addition, there is a
bonus problem worth 15 points.

\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}

\vfill

{\Large
\begin{center}
\begin{tabular}{||c|c|c||}\hline
Question & Score & Maximum \\ \hline
1 & & 20 \\ \hline
2 & & 20 \\ \hline
3 & & 15 \\ \hline
4 & & 15 \\ \hline
5 & & 15 \\ \hline
6 & & 15 \\ \hline
Bonus & & 15 \\ \hline
Total & & 100 \\ \hline
\end{tabular}
\end{center}
}

\vfill
\vfill

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

\newpage

{\bf Problem 1. (2 $\times 10$ = 20 points)} 
\begin{itemize}
\item[{\bf (a)}] Derive an asymptotically tight bound for the following
recurrence.  Assume that $T(n)$ is $\Theta(1)$ for $n\le 2$.

\[ T(n) = T(n/4) + T(3n/4) + n.\]

\vfill
\item[{\bf (b)}] Suppose we insert the keys $5$, $2$, $8$, $1$, $7$, $6$, $3$,
$4$ in sequence into an empty $2$-$3$-$4$ tree.  What is the final $2$-$3$-$4$
tree obtained?  You may simply draw the final tree without any additional
justification.

\vfill

\end{itemize}

\newpage

{\bf Problem 2. (2 $\times$ 10 = 20 points) \hs} Consider the following data
encoding problem.  We have a set $S$ of $m$ {\em code words}, each being a
string of length at most $k$.  We are given a data string $D$ of length $n$.
We would like to determine whether we can encode $D$ as a concatenation of a
sequence of code words from $S$.  Furthermore, if the encoding exists, we
would like to determine an encoding that uses the minimum length sequence of
code words.

For example, if $S = \{0, 10, 0101\}$, and $D = 0101010100$, the encoding
$0101;0;10;10;0$ has length five, while the minimum-length encoding
$0101;0101;0;0$ has length four.  On the other hand, there is no encoding for
the string $111$ using code words in $S$.

\begin{Itemize}
\item[{\bf (a)}] Suppose the set $S$ of code words satisfies the following
condition: if $s \in S$, then every nonempty suffix of $s$ is also in $S$.  An
example of such a set is $\{0, 10, 110, 1110, 01110\}$.  (A string $x$ is a
{\em suffix}\/ of string $y$ if there exists another string $z$ such that $y$
is a concatenation of $z$ and $x$; that is, $y = z;x$.  Thus, for example,
$110$ is a suffix of $01110$ since $01110 = 01;110$.)

Give a greedy algorithm to determine a minimum-length encoding of a given
string $D$ using code words from $S$.  If no such encoding exists, then the
algorithm must indicate so.  Briefly justify the correctness of your
algorithm.

\newpage

\item[{\bf (b)}] Now suppose $S$ is an arbitrary set of $m$ code words.
Design an efficient algorithm to determine a minimum-length encoding of a
given string $D$ using code words from $S$. If no such encoding exists, then
the algorithm must indicate so.  

Analyze the worst-case running time of your algorithm.  The more efficient
your algorithm is in terms of its worst-case running time, the more credit you
will get.
\end{Itemize}

\newpage

{\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}
\junk{
%%% COMMENTS ADDED AFTER EXAM
%%% This should have been ``weighted'' instead of ``unweighted''.
\item[{\bf (a)}] Let $G$ be a connected unweighted undirected graph.  Let $u$
be any node in $G$ and $(u,v)$ be an edge that has minimum weight {\em among
all edges incident on $u$}.  Then, $(u,v)$ belongs to some minumum spanning
tree.  \vfill
}

\item[{\bf (a)}] Let $G$ be a connected weighted undirected graph.  Let $u$
be any node in $G$ and $(u,v)$ be an edge that has minimum weight {\em among
all edges incident on $u$}.  Then, $(u,v)$ belongs to some minumum spanning
tree.  \vfill

\junk{
%%% COMMENTS ADDED AFTER EXAM
%%% This should have been ``minimum spanning tree'' instead of ``spanning tree''.
\item[{\bf (b)}] For any spanning tree $T$ of an undirected weighted graph $G$
and any cut $C$ of $G$, there exists at least one edge in $T$ that crosses $C$
and has minimum weight among all edges crossing $C$.
}

\item[{\bf (b)}] For any minimum spanning tree $T$ of an undirected weighted
graph $G$ and any cut $C$ of $G$, there exists at least one edge in $T$ that
crosses $C$ and has minimum weight among all edges crossing $C$.  \vfill

\item[{\bf (c)}] A minimum cut $(S, T)$ of a flow network $G$ is also a
minimum cut of the flow network $G'$ that is obtained by increasing the
capacity of every edge in $G$ by a positive constant $\alpha$.  \vfill
\end{Itemize}

\newpage

{\bf Problem 4. (15 points)\hs } Given a directed graph $G = (V, E)$ with positive
weights on each edge, design an efficient algorithm to determine a directed
cycle in $G$ of minimum total weight.  If no directed cycle exists in $G$,
then your algorithm must indicate so.  

Analyze the worst-case running time of your algorithm.  The more efficient
your algorithm is in terms of its worst-case running time, the more credit you
will get.

\newpage

{\bf Problem 5. (15 points) \hs } Let $G=(V,E)$ be a directed graph in which 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 an efficient
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.  The more efficient
your algorithm is in terms of its worst-case running time, the more credit you
will get.

\newpage 

{\bf Problem 6. (15 points) \hs } Several families go out to dinner together.
To increase their social interaction, they would like to sit at tables so that
no two members of the same family are at the same table.  Show how to
formulate the problem of finding a seating arrangement that meets this
objective as a maximum flow problem.  

Assume that the dinner contingent has $n$ families and the $i$th family has
$a_i$ members.  Also assume that $m$ tables are available and the $j$th table
has a seating capacity of $b_j$.

({\em Hint:} In the network flow graph, include a vertex for each family and a
vertex for each table together with distinguished source and sink vertices.)

\newpage

\junk{
%%% COMMENTS AFTER EXAM
%%% Wrong Problem!!
%%% Cannot be solved as is.  Needs O(V + E) time or change the problem to
%%% adding an edge
{\bf Bonus Problem. (15 points) \hs } Suppose we are given a minimum spanning tree
$T$ of an undirected weighted graph $G$.  Describe an $O(V)$ time algorithm to
update the minimum spanning tree when we remove an edge $(u,v)$ from $G$.
Prove the correctness of your algorithm.
}
{\bf Bonus Problem. (15 points) \hs } Suppose we are given a minimum spanning tree
$T$ of an undirected weighted graph $G$.  Describe an $O(V)$ time algorithm to
update the minimum spanning tree when we add an edge $(u,v)$ from $G$.
Prove the correctness of your algorithm.
\end{document}

