\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}
\input{/home/rraj/Courses/1390/Syllabus/localmacros}
\newcommand{\hs}{\hspace{1em}}
\newcommand{\Hspace}{\hspace{1em}}
\newcommand{\myin}[1]{\mbox{{\em in}[#1]}}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{1390}{Algorithms}{Winter 1999}{11 March 1999}{23}

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

\bigskip

{\bf 1. (15 points)} Exercise~23.3--4.

{\bf Answer:} 
\begin{Itemize}
\item[{\bf a.}] If $(u,v)$ is a tree edge or a forward edge, then $v$ is a
descendant of $u$.  Therefore, {\sc Dfs-Visit}$(u)$ is called before {\sc
Dfs-Visit}$(v)$ and completes only after {\sc Dfs-Visit}$(v)$ is completed.
In other words, $v$ is discovered after $u$ is discovered and finished before
$u$ is finished.  Thus, $d[u] < d[v] < f[v] < f[u]$.

For the other direction, we note that if $d[u] < d[v] < f[v] < f[u]$, then $u$
is discovered before $v$ and finished after $v$.  By the way the $d$ and $f$
values are incremented, it follows that {\sc Dfs-Visit}$(u)$ is called before
{\sc Dfs-Visit}$(v)$ and completes only after {\sc Dfs-Visit}$(v)$ is
completed.  Therefore, $v$ is a descendant of $u$.  Hence, $(u,v)$ is a tree
edge or a forward edge.

\item[{\bf b.}] If $(u,v)$ is a back edge, then $u$ is a descendant of $v$ and
the same argument as above holds with $u$ and $v$ interchanged.

\item[{\bf c.}] Since $(u,v)$ is an edge, if $u$ is discovered first, then $v$
has to be a descendant of $u$ since we cannot finish $u$ without visiting
$v$.  Since $(u,v)$ is a cross edge, $v$ is not a descendant of $u$.
Therefore, it follows that $d[v] < d[u]$.  If $f[v]$ is greater than $d[u]$,
then $u$ will be a descendant of $v$, thus again leading to a contradiction.
Therefore, $d[v] < f[v] < d[u] < f[u]$.

If $d[v] < f[v] < d[u] < f[u]$, then $u$ is not a descendant of $v$ since $u$
is discovered after $v$ is finished.  Moreover, for the same reason, $v$ is
not a descendant of $u$.  Therefore, $(u,v)$ is a cross edge.
\end{Itemize}

{\bf 2. (35 points)} Problem~23--1.  Assume that the given graph does not have
any self-loops.

{\bf Answer:} 
\begin{Itemize}
\item[{\bf a.}] This part concerns breadth-first search in undirected graphs.
\begin{enumerate}
\item
We need to prove that there are no back edges and no forward edges.  Both back
edges and forward edges are non-tree edges that go between ancestors and
descendants.  Let, if possible, $(u,v)$ be a back edge or a forward edge.  Let
$u$ be the vertex visited first.  Since $v$ is a descendant of $u$, at this
time $v$ is colored white.  Therefore, while considering edge $(u,v)$
(line~11 of the code on page~470), we set the predecessor of $v$ to be $u$
(line~15), and thus make $(u,v)$ a tree edge -- not a back or forward edge.

\item
We need to prove that for each tree edge $(u,v)$, we have $d[v] = d[u] + 1$.
This is straightforward since if $u$ is an ancestor of $v$, then we set $d[v]$
equal to $d[u] + 1$ in line~14 when traversing $(u,v)$.  Since the $d[\cdot]$
values do not change after being set, we have the desired claim.

\item
We need to prove that for each cross edge $(u,v)$, we have $d[v] = d[u]$ or
$d[v] = d[u] + 1$.  In fact, one can prove this fact for any edge $(u,v)$
using the result that for any vertex $u$, $d[u] = \delta(s,u)$, the length of
the shortest path from the source $s$ to $u$ (see Theorem~23.4; in class, we
proved a more general result by our analysis of Dijkstra's algorithm).  By
triangle inequality, we have $d(v) = \delta(s,v) \le \delta(s,u) + 1 = d[u] +
1$.  If we take $v$ to be the vertex that has at least the same $d[\cdot]$
value as $u$, then we have $d[v] = d[u]$ or $d[v] = d[u] + 1$.
\end{enumerate}
\item[{\bf b.}] This part concerns breadth-first search in directed graphs.
\begin{enumerate}
\item We need to prove that there are no forward edges.  A forward edge is a
non-tree edge edge from an ancestor to a descendant.  Consider any edge
$(u,v)$ where $u$ is an ancestor of $v$.  This implies that there is a path
from $u$ to $v$ in the breadth-first search tree.  So at the time that $u$ is
dequeued from the queue $Q$, $v$ is white.  This implies that when the edge
$(u,v)$ is considered in line~11, $v$ passes the if-test in line~12 and we set
$\pi[v]$ to $u$, thus making $(u,v)$ a tree edge.  Therefore, $(u,v)$ is not a
forward edge.

\item
We need to prove that for each tree edge $(u,v)$, we have $d[v] = d[u] + 1$.
This follows directly from the definition of a tree edge.  For a tree edge
$(u,v)$, we have $\pi[v] = u$.  Around the same time when we set $\pi[v]$ to
$u$ (in line~15), we set $d[v] = d[u] + 1$.  Since both $\pi[v]$ and $\d[v]$
are set exactly once after the initialization, we have the desired claim.

\item
We need to prove that for each cross edge $(u,v)$, we have $d[v] = d[u] + 1$.
The proof is identical to that for undirected graphs.  One can prove this fact
for any edge $(u,v)$ using the result that for any vertex $u$, $d[u] =
\delta(s,u)$, the length of the shortest path from the source $s$ to $u$ (see
Theorem~23.4; in class, we proved a more general result by our analysis of
Dijkstra's algorithm).  By triangle inequality, we have $d(v) = \delta(s,v)
\le \delta(s,u) + 1 = d[u] + 1$.

\item
We need to prove that for each back edge, we have $0 \le d[v] < d[u]$.  We can
prove $d[x] \ge 0$ for all $x \in V$ by a simple induction on the number of
times line~14 is executed.  Initially, all the $d[\cdot]$ values are nonnegative.
Whenever line~14 is executed, we set $d[x]$ for a vertex $x$ to $d[y] + 1$ for
some other vertex $y$.  Since by the induction hypothesis, all the $d[\cdot]$
values are nonnegative, $d[y]$ is nonnegative before this execution of
line~14, thus implying that $d[x]$ is nonnegative after the execution of
line~14.  Hence all of the $d[\cdot]$ values are always nonnegative.

We now prove that for a back edge $(u,v)$, $d[v] < d[u]$.  Since $v$ is an
ancestor of $u$, there is a path from $v$ to $u$ in the breadth-first tree
of the form $v = v_0 \rightarrow v_1 \rightarrow \ldots v_i \rightarrow \ldots
\rightarrow v_k = u$ such that $\pi[v_i] = v_{i-1}$ for $1 \le i \le k$.
Moreover, at the time these $\pi$ values are set, the $d[\cdot]$ values are set.
Therefore, we have $d[v_i] = d[v_{i-1}] + 1$.  This implies that $d[u] =
d[v_k] = d[v_0] + k = d[u] + k > d[u]$.
\end{enumerate}
\end{Itemize}

{\bf 3. (20 points)} Exercise~23.4--5.

{\bf Answer:} For each vertex $v$, we maintain a field $\myin{v}$ that
represents the current in-degree of the vertex.  We also maintain a set $Z$ of
vertices that have in-degree $0$ and have not been removed from the graph.

The initialization phase is the following.  We set $\myin{v}$ to be the
in-degree of $v$ in the original graph $G$.  The set $Z$ is a linked list of
vertices in $V$ that have zero in-degree.  All of these steps can be done in
$\Theta(V + E)$ time.

In the iterative routine, we repeatedly remove a vertex $u$ from $Z$.  For every
edge $(u,v)$ coming out of $u$, we decrement $\myin{v}$ by $1$.  If in this
process, any $\myin{v}$ becomes zero, we add the vertex to $Z$.  We repeat
this process until $Z$ is empty, which is when the procedure terminates.

If $G$ has cycles, then $Z$ may become empty, yet all of the vertices will not
be output.  This is because we may reach a state in which there are vertices
in the graph and none of them have a zero in-degree.  In this situation, the
algorithm will terminate without outputting all of the vertices.  An example
of this case is when $G$ is a directed ring.

{\bf 4.} We are given a set of $n$ empty boxes $B_i=(h_i,w_i,\ell_i)$, $1\leq
i\leq n$, where $h_i$, $w_i$, and $\ell_i$ denote the height, width, and
length of box $B_i$.  Let us say that box $B_i$ {\em nests}\/ within box $B_j$
if and only if box $B_i$ can be oriented so that it is {\em strictly
smaller\/} than box $B_i$ in each corresponding dimension.  For example, even
though the box $B_i=(5,1,1)$ is taller than the box $B_j=(2,6,3)$, $B_i$ can
be placed inside $B_j$ by orienting it as a $(1,5,1)$.

\begin{Itemize}
\item[{\bf (a) (5 points)}] Describe an $O(1)$ time algorithm to determine
whether one box nests within another.

{\bf Answer:} In order to determine whether $B_i$ nests in $B_j$, we run the
following algorithm.  We sort the three dimensions of $B_i$ and $B_j$ in
nonincreasing order.  Let $(x_i, y_i, z_i)$ and $(x_j, y_j, z_j)$ be the two
vectors obtained.  We thus have $x_i \ge y_i \ge z_i$ and $x_j \ge y_j \ge
z_j$.  We claim that $B_i$ nests in $B_j$ if and only if $x_i < x_j$, $y_i <
y_j$, and $z_i < z_j$.  To see this claim, we first note that if $x_i < x_j$,
$y_i < y_j$, and $z_i < z_j$, then clearly $B_i$ nests in $B_j$.  For the other
direction, we need to prove that if $B_i$ nests in $B_j$, then $x_i < x_j$,
$y_i < y_j$, and $z_i < z_j$.  If not, then either $x_i \ge x_j$, $y_i \ge
y_j$, or $z_i \ge z_j$.  If $x_i \ge x_j$, then $x_i \ge y_j$ and $x_i \ge
z_j$.  This contradicts the fact that $B_i$ nests in $B_j$.  Similarly, we can
derive contradictions under the assumption $y_i \ge y_j$ or $z_i \ge z_j$.
Thus, we have an $O(1)$ procedure to determine whether a given box $B_i$ nests
in another box $B_j$.

\item[{\bf (b) (20 points)}] We would like to compute the maximum length $k$
of a sequence of boxes $B_{i_1},\ldots,B_{i_k}$ such that $B_{i_j}$ nests
inside $B_{i_{j+1}}$, $1\leq j<k$.  Design and analyze an $O(n^2)$-time
algorithm for the problem by expressing it as a shortest-path problem in a
suitably defined graph.

{\bf Answer:} We construct a graph $G = (V, E)$ as follows.  The set $V$ is
the set of $n$ boxes.  We have an edge from box $B_i$ to box $B_j$ if and only
if $B_i$ nests in $B_j$.  

The above process of constructing the graph takes $O(n^2)$ time since we have
to check for every pair of boxes.  We claim that $G$ is acyclic.  Our proof is
by contradiction.  Let, if possible, $B_1, B_2, \ldots, B_k, B_1$ form a cycle
in $G$.  Looking at the $x$-dimensions of each of the boxes, we get $x_1 < x_2
< \ldots < x_k < x_1$, a contradiction.

We next claim that any valid sequence of ``nestable'' boxes is a path in $G$
and vice versa.  To see this, we first note that if $B_{i_1},\ldots,B_{i_k}$
is a valid sequence of nestable boxes then $B_{i_j}$ nests inside
$B_{i_{j+1}}$, $1\leq j<k$.  Therefore, $B_{i_1}
\rightarrow \ldots \rightarrow B_{i_k}$ is a path in $G$.  Similarly, if 
$B_{i_1}\rightarrow \ldots \rightarrow B_{i_k}$ in $G$, then by our choice of
edges, $B_{i_j}$ nests inside $B_{i_{j+1}}$, $1\leq j<k$.  Therefore,
$B_{i_1},\ldots,B_{i_k}$ is a valid sequence of nestable boxes.  We have thus
reduced the problem of finding the maximum length sequence of nestable boxes
to the problem of finding the longest path in $G$.

In order to find the longest path in $G$, we augment the graph slightly to
obtain $G' = (V', E')$ by adding two new vertices $s$ and $t$, and adding
edges from $s$ to every vertex (box) in $V$ and an edge from every vertex in
$V$ to $t$.  Thus, $V'$ equals $V \cup \{s,t\}$ and $E'$ equals $E \cup \{(s,
v), (v, t): v \in V\}$.  Hence, $|V'|$ equals $n + 2$ and $|E'|$ is $|E| + 2n
= O(n^2)$.  We assign a weight of $-1$ to every edge in $E'$.  

It is easy to see that any path $p$ in $G$ from a vertex $u$ to $v$
corresponds to a path $p'$ in $G'$ which consists of the edge $(s, u)$
followed by the path $p$ to $v$ and then the edge $(v, t)$.  And vice versa.
Therefore, the problem of finding the longest path in $G$ is equivalent to
finding the shortest path in $G'$ (since the weights are all $-1$).  Since
$G'$ is a directed acyclic graph, we can compute the shortest path from $s$ to
$t$ in $O(n^2)$ time using the {\sc Dag-Shortest-Paths} algorithm of
Section~25.4.  This path yields a sequence of vertices in $V$, which is the
longest sequence of nestable boxes.
\end{Itemize}

{\bf 5. (25 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.  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$.

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)$, and (ii) for any three vertices $x$, $y$, and $z$, $\delta(x,y) \le
\delta(x,z) + \delta(z,y)$.  

In our present situation, since we are seeking the path with the largest
effective bandwidth -- not the shortest path -- claims~(i) and~(ii) translate
to the following two claims: (I) if the last edge on the shortest path from
$s$ to $v$ is $(u,v)$, then $\delta(s,v) = \min\{\delta(s,u), w(u,v)\}$, and
(II) for any three vertices $x$, $y$, and $z$, $\delta(x,y) \ge \min\{
\delta(x,z), \delta(z,y)\}$.  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.

{\bf 6. (15 points)} Exercise~26.2--1.

{\bf Answer:} For this problem, you need to run algorithm {\sc
Floyd-Warshall}, given on page~560, systematically on the following weighted
adjacency matrix that represents the graph in Figure~26.2.
\[
W = 
\left( 
\begin{array}{cccccc}
0 & \infty & \infty & -4 & -1 & \infty \\
1 & 0 & \infty & 2 & \infty & \infty \\
\infty & 2 & 0 & \infty & \infty & -8 \\
-4 & \infty & \infty & 0 & 3 & \infty \\
\infty & 7 & \infty & \infty & 0 & \infty\\
\infty & 5 & 10 & \infty & \infty & 0
\end{array}
\right).
\]

Since the solution can be obtained by mechanically going through the algorithm
code, it is omitted here. 

{\bf 7. (25 points)} Prove that if $T_1$ and $T_2$ are two minumum spanning
trees, then $T_1$ and $T_2$ have the same ``weight distribution'' (i.e., for
any weight $w$, both $T_1$ and $T_2$ contain the same number of edges with
weight $w$).

{\bf Answer:} We will prove the desired claim by matching each edge of $T_1 -
T_2$ with a unique edge of $T_2 - T_1$ of equal weight.  (The edges in $T_1
\cap T_2$ need not be considered in the argument about the same weight
distribution since they are in both trees.)  Our main claim is that for any
edge $e_1$ in $T_1 - T_2$, we can find an edge $e_2$ in $T_2 - T_1$ such that
$T_1 - \{e_1\} + \{e_2\}$ is an MST.

Before proving the main claim, let us see how this implies the desired result.
We use the main claim to transform the MST $T_1$ to MST $T_2$.  Pick an edge
$e_1$ that lies in $T_1$ but does not lie in $T_2$.  We use the main claim and
replace it by an edge $e_2$ from $T_2 - T_1$ with the same weight.  By doing
this, we obtain a new MST $T_3$ that is ``closer'' to $T_2$ than $T_1$ is, in
the sense that it has more common edges.  We now repeat the replacement
process.  In every iteration, we match an edge in $T_1 - T_2$ with an edge in
$T_2 - T_1$ of the same weight.  Once the process terminates, we have
transformed $T_1$ to $T_2$, and have completed the mapping, and have
established the equivalence of the weight distributions of $T_1$ and $T_2$.

We now prove the main claim.  We will use the Figure~24.3 in the text book,
page~501, to illustrate the proof.  Let $e_1 = (u,v)$ be an edge in $T_1 -
T_2$.  Since $e_1$ is an edge of the spanning tree $T_1$, if we remove it, the
graph becomes disconnected.  Let the two components be $S$ and $V - S$.  Since
$e_1$ is not in $T_2$, it forms a cycle with the path $p$ that connects $u$
and $v$.  Since $p$ forms a cycle along with $(u,v)$, there is at least one
edge on the path $p$ that goes from $S$ to $V - S$ (otherwise, we will not have
a cycle).  Let this edge be $e_2 = (x,y)$.  

We now claim that $w(e_2) = w(e_1)$.  If $w(e_2) > w(e_1)$, then $T_2 -
\{e_2\} + \{e_1\}$ is a spanning tree with weight less than that of $T_2$,
thus contradicting the fact that $T_2$ is a spanning tree.  If $w(e_2) <
w(e_1)$, then $T_1 - \{e_1\} + \{e_2\}$ is a spanning tree with weight less
than that of $T_1$, thus contradicting the fact that $T_1$ is a spanning tree.
We have thus shown than $w(e_2) = w(e_1)$.  Therefore, $T_1 - \{e_1\} +
\{e_2\}$ is an MST.  This completes the proof of the main claim. 
\end{document}

