\documentstyle[11pt,handout]{article}
\begin{document}
\input{macros}

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

\head{3390}{Analysis of Algorithms}{11 December 1998}{27}

\begin{center}
\Large{\bf Sample Solutions to Problem Set 4}
\end{center}

\bigskip
{\bf Problem~1. (6 points)} Exercise~24.1--3.

{\bf Answer:} Consider an edge $(u,v)$ of a minimum spanning tree $T$.
Removal of $(u,v)$ from $T$ disconnects $u$ and $v$.  Let $S$ be the set of
vertices that are connected to $u$ in $T - \{u,v\}$.  Thus, $V - S$ is the set
of vertices that are connected to $v$ in $T - \{u,v\}$. 

Consider the cut $C = (S, V - S)$.  Clearly the edge $(u,v)$ crosses the cut
$C$.  We claim that $(u,v)$ is a light edge for $C$.  The proof is by
contradiction.  If not, then let $e$ be an edge with smaller weight that
crosses $C$.  The graph $T' = T - \{(u,v)\} \cup \{e\}$ is a spanning tree
since the edge $e$ connects the sets $S$ and $V - S$, each of which is
connected.  But $T'$ has lesser weight than $T$, contradicting the fact that
$T$ is an MST.

{\bf Problem~2. (6 points)} Exercise~24.1--5.

{\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 Problem~3. (12 points)} Prove that a minimum spanning tree of a graph $G$ is also a spanning
tree whose largest edge weight is minimum over all spanning trees of $G$.

{\bf Answer:} Let $T$ be an MST of $G$.  Let $T'$ be any other spanning tree
of $G'$.  Let $e$ be a maximum-weight edge in $T$.  We now show that there is
at least one edge in $T'$ that has weight at least $w(e)$.  It then follows
that the largest edge weight of $T$ is at most the largest edge weight among
all spanning trees.

The edge $e$ partitions $T$ into two subsets of vertices, say $S$ and $V - S$.
Since $T'$ is a spanning tree of $G$, there is an edge $e'$ in $T$ that
crosses the cut $(S, V - S)$.  In Problem~1, we showed that $e$ is a light
edge for the cut.  Therefore, $w(e')$ is at least $w(e)$. 

{\bf Problem~4. (8 points)} Exercise~23.3--8.

{\bf Answer:} A trivial example would be a self-loop at $u$.  But this is not
what the problem was intended for.  Consider the graph that just consists of
the path $v \rightarrow u \rightarrow w$.  Let us assume that we start the
depth-first search at $w$, i.e., call {\sc Dfs-Visit}$(w)$ first.  Then since
there are no edges coming out of $w$, $w$ forms a depth-first search tree all
by itself.  Suppose, we next call {\sc Dfs-Visit}$(u)$.  Since $w$ is already
colored black and there are no other edges out of $u$, $u$ forms a depth-first
search tree all by itself.  Thus, even though $u$ has both an incoming edge as
well as an outgoing edge, $u$ ends up in a depth-first search tree by itself.

{\bf Problem~5. (9 + 12 = 21 points)} Problem~23--1.

{\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[]$
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[]$ 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]$.  Steven
Stuart pointed out that this claim is false if we consider a self loop $(u,
u)$.  So we will prove the above claim for edge $(u,v)$ where $u$ and $v$ are
distinct vertices.  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[]$ 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[]$ 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[]$ 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[]$ 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 Problem~6. (8 points)} Exercise~25.2--4.

{\bf Answer:} Suppose we want to compute the most reliable path from $s$ to
$t$.  Let $r[p]$ denote the reliability of the path $p$.  Since the
reliability of a path $p$ is the probability that the path will not fail,
$r[p]$ equals $\prod_{(u,v) \in P} r(u,v)$.  If we take logarithms on both
sides, we obtain that $\lg (r[p])$ equals $\sum_{(u,v) \in P} \lg (r(u,v))$.
If $p$ is a path from $s$ to $t$ that has the highest $r[p]$, it is also the
path that has the highest $\lg (r[p])$.  Therefore, the problem of finding
the most reliable path from $s$ to $t$ is equivalent to finding the longest
path from $s$ to $t$ in $G$, where the weight of an edge $(u,v)$ equals $\lg
(r(u,v))$.  This in turn is equivalent to the finding the shortest path from
$s$ to $t$ in $G$, where the weight of an edge equals $- \lg(r(u,v))$.  

Since $r(u,v)$ is a probability and hence is at most $1$, we have $-
\lg(r(u,v)) \ge 0$.  Therefore, all weights are nonnegative.  So we can use
Dijkstra's algorithm to find the shortest path from $s$ to $t$ in $G$ with
$w(u,v) = - \lg(r(u,v))$ for each edge $(u,v)$, and return the path as the
most reliable path from $s$ to $t$.  The running time for computing the
weights is $O(E)$.  The running time of Dijkstra's algorithm is $O(E \lg V)$
using priority queues.  Therefore, the total running time is $O(E \lg V)$.

{\bf Problem~7. (16 points)} 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$
``fits inside'' 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)$.

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}$ fits 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.

({\em Remark:}\/ Problem~25--2 of text is a generalization of the above
problem.  The above problem itself is a generalization of Problem~3 of Problem
Set~3 and can also be solved directly by dynamic programming.)

{\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$ fits in $B_j$.  In order to determine whether $B_i$ fits 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$ fits 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$ fits in $B_j$.  For the other
direction, we need to prove that if $B_i$ fits 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$ fits 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$ fits
in another box $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 ``fittable'' 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 fittable boxes then $B_{i_j}$ fits 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}$ fits inside $B_{i_{j+1}}$, $1\leq j<k$.  Therefore,
$B_{i_1},\ldots,B_{i_k}$ is a valid sequence of fittable boxes.  We have thus
reduced the problem of finding the maximum length sequence of fittable 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 fittable boxes.
\end{document}