\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/W00/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}

\newcommand{\cp}{\mbox{{\em copy}}}
\newcommand{\ins}{\mbox{{\em insert}}}
\newcommand{\rep}{\mbox{{\em replace}}}
\newcommand{\del}{\mbox{{\em delete}}}
\newcommand{\twi}{\mbox{{\em twiddle}}}
\newcommand{\kil}{\mbox{{\em kill}}}
\newcommand{\cost}{\mbox{cost}}
\newcommand{\op}{\mbox{{\em op}}}
\newcommand{\Compute}{\mbox{{\sc Compute}}}

\newcommand{\remaining}{\mbox{{\em remaining}}}
\newcommand{\print}{\mbox{{\bf print}}}
\newcommand{\minpair}{\mbox{{\em minpair}}}
\newcommand{\Max}{\mbox{{\em Max}}}

\renewcommand{\insert}{\mbox{{\sc Insert}}}
\newcommand{\exmin}{\mbox{{\sc Extract-Min}}}
\newcommand{\exmax}{\mbox{{\sc Extract-Max}}}
\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\sempty}{\mbox{{\sc Stack-Empty}}}
\newcommand{\Nil}{\mbox{{\sc Nil}}}
\newcommand{\pop}{\mbox{{\sc Pop}}}
\newcommand{\push}{\mbox{{\sc Push}}}

\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 2000}{9 March 2000}{18}

\begin{center}
  \Large{\bf Sample Solution to Problem Set 5}
\end{center}

\bigskip

{\bf 1. (15 points)} Exercise~24.1-5, page 503.

{\bf Answer:} Let $T$ be a minimum spanning tree of $G$.  We are given an edge
$e$ in $G$ that is a maximum-weight edge on some cycle, say $C$, of $G$.  
If edge $e$ belongs to $T$, then we construct a new minimum spanning tree for
$G$ that does not contain $e$.  The edge $e$ partitions $T$ into two subsets
of vertices, say $S$ and $V - S$.  Since $e$ crosses the cut $(S, V - S)$, the
cycle $C$ has another edge $e'$ that crosses the cut.  Therefore, $T' = T -
\{e\} \cup \{e'\}$ is a spanning tree for $G$.  Since $e$ is the
maximum-weight edge that crosses the cut, $w(e') \le w(e)$.  Hence, $w(T') \le
T$, implying that $T'$ is also a minimum spanning tree of $G$.

We now have an MST, say $T$, of $G$ that does not contain $e$.  Since every
spanning tree of $G'$ is a spanning tree of $G$ and hence has at least as much
weight as $T$, $T$ is an MST of $G'$.

{\bf 2. (15 + 10 = 25 points)} Problem~25--3, page 546.

{\bf Answer:} We view the given information as a weighted directed graph $G$
in which the the currencies form the vertices and there is a directed edge
between any two vertices.  Thus, there are $n$ vertices and $n(n-1)$ edges.

\begin{itemize}
\item[(a)] Once we have specified the graph (without yet specifying the
weights), there are two ways of solving this problem.  One is by transforming
the problem to one of finding the existence of a negative weight cycle in a
graph -- here we will judiciously choose the weights.  And the other is to set
the weight of the edge $(i,j)$ to be the exchange rate $R(i,j)$ and then
modify the Bellman-Ford algorithm to determine whether a cycle with product $>
1$ exists.  In the latter approach, we also need to show that the modification
of the Bellman-Ford algorithm works correctly.

Here we consider the first approach.  For vertices (currencies) $i$ and $j$,
in $G$, we let the weight of edge $(i,j)$ equal $- \lg (R(i,j))$.  We now show
that arbitrage exists if and only of there exists a negative weight cycle in
$G$.  This is easy to see since the weight of a cycle $i_1 \rightarrow i_2
\rightarrow \ldots \rightarrow i_k \rightarrow i_1$ equals 
\[\sum_{1 \le j \le k} - \lg (R(i_j, i_{j+1})) = - \lg\left(\prod_{1 \le j \le k}
R(i_j, i_{j+1})\right),
\] 
thus implying that the weight of the cycle is negative if and only if
$\prod_{1 \le j \le k} R(i_j, i_{j+1})$, which is the condition for arbitrage.

We have thus reduced our problem to that of finding whether there exists a
negative-weight cycle in $G$.  We simply invoke the Bellman-Ford algorithm
starting from any source.  Since every vertex is accessible from every other
vertex, if a -ve weight cycle exists in $G$, we will find its existence using
the algorithm.  The running time of the algorithm is $O(VE) = O(n \cdot n^2) =
O(n^3)$.

\item[(b)] In order to extract the cycle of currencies that yields arbitrage,
we employ $n(n-1) + 1$ iterations of the Bellman-Ford algorithm.  In iteration
$0$, we run the Bellman-Ford algorithm on $G$.  If no negative weight cycle is
found, then there is nothing to do further.  If the existence of a
negative-weight cycle is indicated, then we perform the next $n(n-1)$
iterations (one associated with each of the $n(n-1)$ edges).

We number the edges arbitrarily from $1$ to $n(n-1)$.  We also select a source
$s$ arbitrarily.  In iteration $1$, we run the Bellman-Ford algorithm on the
subgraph of $G$ obtained after removing edge $1$.  If we find no
negative-weight cycle, then this implies that $1$ lies in all negative-weight
cycles or lies along a path from the source that leads to all negative-weight
cycles.  In this case, we keep edge $1$ in all future iterations.  Otherwise,
we remove $1$ from the graph.

So, in general, at the start of iteration $i$, we have a graph $G_{i-1}$ which
is a subgraph of $G$ with a subset of the edges $\{1, 2, \ldots, i-1\}$
removed.  In iteration $i$, we run the Bellman-Ford algorithm on the subgraph
$G'$ of $G_{i-1}$ in which edge $i$ has been removed.  If a negative-weight
cycle exists, then we set $G_i$ to $G'$; otherwise, we set $G_i$ to $G_{i-1}$.

Thus, after iteration $n(n-1)$, we have a subgraph $G_n$ which consists of a
set of edges, each of which belongs to every negative weight cycle in $G_n$ or
lies on a path from $s$ to every negative-weight cycle.  Thus, the graph $G_n$
is simply a (possibly empty) path from source $s$ to a negative-weight cycle.
We can extract the negative-weight cycle from $G_n$ by a search from $s$
(depth-first or breadth-first).

Since there are $O(n^2)$ iterations, each involving a Bellman-Ford algorithm
of $O(n^3)$ running time, the running time of the complete algorithm equals
$O(n^5)$.
\end{itemize}

{\bf 3. (20 points)} One can model a communication network by a
weighted directed graph $G$, in which the vertices of $G$ represent
the nodes of the network, the edges of $G$ represent the communication
links of the network and the weight of an edge is the bandwidth of the
link.  We define the {\em effective bandwidth}\/ of a path $p$ as the
bandwidth of the minimum-bandwidth link in $p$.

Design and analyze an efficient algorithm to determine a path with the
largest effective bandwidth from a given node $s$ to a given node $t$.
If no path from $s$ to $t$ exists, then your algorithm must indicate
so.  Briefly justify the correctness of your algorithm.  Analyze the
running time of your algorithm.  You may assume that the bandwidth of
every link is positive.  ({\em Hint:} Modify Dijkstra's algorithm.)

{\bf Answer:} We can modify Dijkstra's algorithm by mainly replacing the the
``$\min$'' operation by ``$\max$'', the ``$+$'' operation by ``$\min$'', and
the ``$>$'' operation by ``$<$''.  These entail three kinds of changes in the
algorithm.  

First, consider the initialization routine {\sc
Initialize-Single-Source}$(G,s)$, defined on page~520 of text.  In line~2, we
will set $d[v]$ to $0$ and in line~4, we set $d[s]$ to $\infty$.

Second, the {\sc Relax}$(u,v,w)$ operation will change to the following code.
\begin{tabbing}
{\sc Relax}$(u,v,w)$\\
1. \= \myif\ \= $d[v] < \min\{d[u], w(u,v)\}$\\
2. \>  \> {\bf then} \= $d[v] = \min\{d[u], w(u,v)\}$\\
3. \> \> \> $\pi[v] = u$
\end{tabbing}

Finally, in {\sc Dijkstra}$(G,w,s)$ (page~527), instead of extracting the
vertex with the minimum $d$ value in line~5, we extract the vertex with the
maximum $d$ value.

The proof of Dijkstra's algorithm for shortest paths proceeds by showing two
claims: (a) $d[u] \ge \delta(s,u)$ for all $u$ at all times, and (b) at the
time $u$ is extracted from $Q$, $d[u] = \delta(s,u)$.  For establishing these
two claims, the two main properties that we need are (i) if the last edge on
the shortest path from $s$ to $v$ is $(u,v)$, then $\delta(s,v) = \delta(s,u)
+ w(u,v)$ (Corollary~25.2 on page 519 of text), and (ii) for any edge $(u,
v)$, $\delta(s,v) \le \delta(s,u) + w(u,v)$ (Lemma~25.3, page 520 -- triangle
inequality).

In our present situation, we are seeking the path with the largest effective
bandwidth -- not the shortest path.  Let $\Delta(s,u)$ denote the effective
bandwidth of the path from $s$ to $u$ with the largest effective bandwidth.
Claims (a) and (b) translate to the following two claims: (A) $d[u] \le
\Delta(s,u)$ for all $u$ at all times, and (b) at the time $u$ is extracted
from $Q$, $d[u] = \Delta(s,u)$.  We can establish these two claims by showing
properties (I) and (II) analogous to the properties (i) and (ii) above: (I) if
the last edge on the path with the largest effective bandwidth from $s$ to $v$
is $(u,v)$, then $\Delta(s,v) = \min\{\Delta(s,u), w(u,v)\}$, and (II) for any
edge $(u, v)$, $\Delta(s,v) \ge \min\{\delta(s,u), w(u,v)\}$.  Note that all
we have done is to replace $+$ by $\min$ and $\le$ by $\ge$.  Both claims~(I)
and~(II) can be proved in a manner very similar to the proofs of~(i) and~(ii),
that we went through in class.

One worthwhile remark is that the proof of claim~(i) for the shortest-paths
case can be done by establishing the optimal substructure property -- that is,
subpaths of shortest paths are shortest paths, something that is not always
true for the effective-bandwidth case!  Nevertheless, claim (I) can be proved
by a simple argument based on contradiction.

{\bf 4. (20 points)} Exercise~17.3-2, page 344.

{\bf Answer:} For the character set $a$, $b$, $c$, $d$, $e$, $f$, $g$, and
$h$, with the frequencies $1$, $1$, $2$, $3$, $5$, $8$, $13$, and $21$,
respectively, the Huffman code is $0000000$, $0000001$, $000001$, $00001$,
$0001$, $001$, $01$, and $1$, respectively.  In general, for an $n$-length
Fibonacci sequence, the Huffman encoding is $n-1$ 0's for $a_1$, and $n-i$ 0's
followed by a $1$ for $a_i$, $2 \le i \le n$.  

{\bf 5. (20 points)} Exercise~17.2-4, page 337.

{\bf Answer:} Let the gas stations on the trip be numbered $1$ through $m$.
Let the starting point be numbered $0$.  between point $i$ and point $j$.

{\sl Optimal substructure property:} We first consider the subproblems of the
overall problem.  For any point $i$, let $S_i$ denote an optimal sequence of
stops assuming Professor Midas starts from point $i$.  Let $j > i$ be the
first stop in this sequence.  Let $S$ denote the subsequence of $S_i$ that
follows $j$.  Then, we can see that $S$ should be an optimal stopping sequence
assuming Professor Midas starts from point $j$.  Why?  Because, if $S'$ were
another stopping sequence with fewer stops starting from $j$, then $S'_i = j ;
S'$ is a stopping sequence starting from $i$ that has fewer stops than $S_i$,
thus contradicting the assumption that $S_i$ is optimal.  Thus, we have shown
the optimal substructure property.

The optimal substructure property suggests the use of dynamic programming or
greedy algorithms.  Here, we show that Professor Midas can employ a simply
greedy algorithm.  Let $i$ denote the point at which Professor Midas has
stopped at any time.  Initially $i$ equals $0$.  Resuming the trip from $i$,
Professor Midas should make the next stop at the largest $j$ such that the
distance between $i$ and $j$ is at most $n$ miles; that is, greedily cover as
much of the distance as the full tank allows.  If no such $j$ exists, then the
next stop will be the destination point $m$.

{\sl Greedy choice property:} We now prove the correctness of the algorithm.
All we need to do is to establish the greedy choice property.  We will
show that for any $i$, there exists an optimal sequence of stops starting from
$i$ in which the first stop is the same as Professor Midas's choice.  That is,
there is an optimal solution that contains Professor Midas's greedy choice.

Starting from $i$, let $j$ be the next stop made by Professor Midas.  Let
$S_i$ denote an optimal sequence of stops starting from $i$.  If $j$ is the
first stop in $S_i$, then there is nothing to prove.  Otherwise, let $j'$ be
the first stop in $S_i$.  By Professor Midas's greedy choice, it is easy to
see that $j' < j$.  This is because Professor Midas picked the farthest point
allowed by a full tank.  Now suppose we replace the stop $j'$ (and any other
stop $< j$) in sequence $S_i$ by stop $j$.  We first note that this is a valid
sequence of stops.  Second, the number of stops has not increased.  Therefore,
this alternative sequence is also optimal.  We have thus proved that there is
an optimal sequence starting from $i$ that contains $j$ as its first stop.

The greedy choice property and the optimal substructure property prove that
the greedy algorithm is optimal.

{\bf 6. (30 points)} Problem~16--3, page 325.

{\bf Answer:} Given strings $x[1..m]$ and $y[1..n]$, we define two matrices
$C[0..m, 0..n]$ and $O[0..m, 0..n]$.  We first consider all the operations but
the \kil\ operation.  The entry $C[i,j]$ is the optimal cost of transforming
$x[1..i]$ to $y[1..j]$, while $O[i,j]$ is the last operation performed in an
optimal transformation of $x[1..i]$ to $y[1..j]$.  (If $i$ equals $0$, then
$x[1..i]$ is the empty string.)  We can now compute $C[i,j]$ and $O[i,j]$
using the following procedure, which we refer to as $\Compute(i,j)$.
\begin{enumerate}
\item
If $i = 0$ and $i = 0$, then set $C[i,j]$ to $0$ and return $C[i,j]$.
\item
Initialize $C[i,j]$ to $\infty$.
\item
\cp: If $i > 0$ and $j > 0$ then if $x[i] = y[j]$ and $C[i-1,j-1] + \cost(\cp)
< C[i,j]$, then set $C[i,j]$ to $C[i-1,j-1] + \cost(\cp)$ and $O[i,j]$ to \cp.
\item
\ins: If $j > 0$ then if $C[i,j-1] + \cost(\ins) < C[i,j]$, then set $C[i,j]$
to $C[i,j-1] + \cost(\ins)$ and $O[i,j]$ to \ins.
\item
\del: If $i > 0$, then if $C[i-1,j] + \cost(\del) < C[i,j]$, then set $C[i,j]$
to $C[i-1,j] + \cost(\del)$ and $O[i,j]$ to \del.
\item
\rep: If $i > 0$ and $j > 0$, then if $C[i-1,j-1] + \cost(\rep) < C[i,j]$, then
set $C[i,j]$ to $C[i-1,j-1] + \cost(\rep)$ and $O[i,j]$ to \rep.
\item
\twi: If $i > 1$ and $j > 1$, then if $x[i] = y[j-1]$, $x[i-1] = y[j]$, and
$C[i-1,j-1] + \cost(\cp) < C[i,j]$, then set $C[i,j]$ to $C[i-2,j-2] +
\cost(\twi)$ and $O[i,j]$ to \twi.
\item
Return $C[i,j]$.
\end{enumerate}

We now prove the correctness of our computation above.  The proof is by
induction on the ordered pair $(i,j)$.  For the induction basis, we note that
$C[0,0]$ is indeed zero.  For the induction step, we first make the hypothesis
that we have correctly computed $C[i',j']$ for all $(i',j')$ such that either
$i' \le i - 1$ or $j' \le j - 1$.  Consider the computation of $C[i,j]$.  Let
$C^*$ be the optimum cost for transforming $x[1..i]$ to $y[1..j]$ without
using the \kil\ operation, and let \op\ be the last operation in this optimal
transformation.  We prove that $C[i,j]$ equals $C^*$ by considering different
cases depending on the operation \op.  Here we only prove for the cases \op =
\cp\ and \op = \twi.  Similar proofs can be given for all other operations
save \kil.

If \op\ is \cp, then the optimal solution would have first
transformed $x[1..i-1]$ to $y[1..j-1]$ and then performed the \cp\ operation.
Therefore, we have $x[i] = y[j]$ and $C^* \ge C[i-1,j-1] + \cost(\cp)$ since
the induction hypothesis says that $C[i-1, j-1]$ is the optimal cost of
transforming $x[1..i-1]$ to $y[1..j-1]$.  In the computation of $C[i,j]$,
step~3 guarantees that $C[i,j] \le C[i-1, j-1] + \cost(\cp) \le C^*$.  Thus,
$C[i,j]$ is indeed the cost of an optimal transformation from $x[1..i]$ to
$y[1..j]$. 

If \op\ is \twi, then the optimal solution would have first transformed
$x[1..i-2]$ to $y[1..j-2]$ and then performed the \twi\ operation.  Therefore,
we have $x[i] = y[j-1]$, $x[i-1] = y[j]$ and $C^* \ge C[i-2,j-2] +
\cost(\twi)$ since the induction hypothesis says that $C[i-2, j-2]$ is the
optimal cost of transforming $x[1..i-2]$ to $y[1..j-2]$.  In the computation
of $C[i,j]$, step~7 guarantees that $C[i,j] \le C[i-2, j-2] + \cost(\twi) \le
C^*$.  Thus, $C[i,j]$ is indeed the cost of an optimal transformation from
$x[1..i]$ to $y[1..j]$.

So our algorithm for computing the optimal costs for transformations not
using the \kil\ operation is the following:
\begin{tabbing}
\=1. \= \for\ \= $i \leftarrow 0$ to $m$\\
\>2. \> \> \for\ \= $j \leftarrow 0$ to $n$\\
\>3. \> \> \> $\Compute(i,j)$
\end{tabbing}

After running the above algorithm, we consider the \kil\ operation by running
the following algorithm:
\begin{itemize}
\item
for $i$ from $1$ to $n$, if $C[i,n] + \cost(\kil) < C[m,n]$, then set $C[m,n]$
to $C[i,n] + \cost(\kil)$ and $O[m,n]$ to ``\kil\ from $i$ onwards''.
\end{itemize}
To prove the optimality of $C[m,n]$, we note that an optimal transformation of
$x[1..m]$ to $y[1..n]$ that ends with a ``\kil\ from $i$ onwards'' consists of
an optimal transformation of $x[1..i]$ to $y[1..n]$ followed by the ``\kil\
from $i$ onwards'' operation.  Since we consider all possible values of $i$ in
the above algorithm and pick the best one, the optimality of $C[m,n]$ holds.

In order to print the optimal transformation, we retrace the computation using
the operation matrix $O$ that we have computed.  We run {\sc Print}$(m,n)$
using the following recursive algorithm:
\begin{tabbing}
{\sc Print}(i, j)\\
\=1. \= \myif\ $i = 0$ and $j = 0$ then \ret\\
\>2. \> \myif\ $O[i,j]$ is \cp\ or \rep\ then {\sc Print}$(i-1, j-1)$\\
\>3. \> \myif\ $O[i,j]$ is \ins\ then {\sc Print}$(i, j-1)$\\
\>4. \> \myif\ $O[i,j]$ is \del\ then {\sc Print}$(i-1, j)$\\
\>5. \> \myif\ $O[i,j]$ is \twi\ then {\sc Print}$(i-2, j-2)$\\
\>5. \> \myif\ $O[i,j]$ is ``\kil\ at $k$'' then {\sc Print}$(k, j)$\\
\>6. \> \print\ $O[i,j]$
\end{tabbing}

\end{document}

