\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/3390/S99/macros/localmacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}
\newcommand{\k}{{\it key}}
\newcommand{\twolists}{{\sc 2List-Select}}
\head{3390}{Analysis of Algorithms}{Winter 2000}{7 March 2000}{14}

\begin{center}
\Large{\bf Practice Problems for Final}
\end{center}

\bigskip 

{\bf 1.} 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.\]

{\bf 2.} 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.

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

{\bf 3.} For each of the following claims, indicate
whether it is true or false.  Briefly justify your answers.
\begin{Itemize}
\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.

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

{\bf 4.} 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.

{\bf 5.} 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.
\end{document}
