\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{\myfor}{{\bf for}}

\newcommand{\enq}{\mbox{{\sc Enqueue}}}
\newcommand{\deq}{\mbox{{\sc Dequeue}}}
\newcommand{\ind}{\mbox{{\it in-degree}}}
\newcommand{\Adj}{\mbox{{\it Adj}}}

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

\head{1390}{Algorithms}{Winter 2000}{6 March 2000}{16}

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

\bigskip

{\bf 1. (7 $\times$ 5 = 35 points)} Problem~23--1, page 495.  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 have proved a more general
  result by our analysis of Dijkstra's algorithm).  We know that $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.
  
\item We need to prove that for each back edge, we have $0 \le d[v] <
  d[u]$.  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[\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 2. (10 points)} Exercise~23.3-8, page 485.  (The directed graph
should have no self-loops.)
  
{\bf Answer:} 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 3. (20 points)} Exercise~23.4-5, page 488.

{\bf Answer:} The algorithm begins by first finding the in-degree of
all vertices.  For this we initialize the in-degrees to zero and then
go through all of the edges and increases the increment the in-degrees
of the heads of the edges by $1$. 
\begin{tabbing}
1. \= \myfor\ \= $u \in V$\\
2. \> \> $\ind[u] \leftarrow 0$\\
3. \> \myfor\ $u \in V$\\
4. \> \> \myfor\ \= $v \in \Adj[u]$\\
5. \> \> \> $\ind[v] \leftarrow \ind[v] + 1$
\end{tabbing}
This takes $\Theta(V + E)$ time, since $V$ adjacency lists are
accessed and $E$ edges found.  We keep the vertices with in-degree $0$
in a FIFO queue, so that they can be enqueued and dequeued in $O(1)$
time.
\begin{tabbing}
6. \= $Q \leftarrow \emptyset$\\
7. \> \myfor\ \= $u \in V$\\
8. \> \> \myif\ \= $\ind[u] = 0$\\
9. \> \> \> $\enq(Q, u)$
\end{tabbing}
This takes $\Theta(V)$ time.  As we process each vertex from the
queue, we effectively remove its outgoing edges from the graph by
decrementing the in-degree of each vertex one of those edges enters,
and we enqueue any vertex whose in-degree goes to $0$.  Each vertex is
enqueued/dequeued at most once because it is enqueued only if it
starts out with in-degree $0$ or if its in-degree becomes $0$ after
being decremented (and never incremented) some number of times.
\begin{tabbing}
10. \= \mywhile\ \= $Q \neq \emptyset$\\
11. \> \> $u \leftarrow \deq(Q)$\\
12. \> \> output $u$\\
13. \> \> \myfor\ \= $v \in \Adj[u]$\\
14. \> \> \> $\ind[v] \leftarrow \ind[v] - 1$\\
15. \> \> \> \myif\ \= $\ind[v] = 0$\\
16. \> \> \> \> $\enq(Q, v)$
\end{tabbing} 
The processing of a vertex from the queue happens $O(V)$ times because
no vertex can be enqueued more than once.  The per-vertex work
(dequeue and output) takes a total of $O(V)$ time.  Since each
adjacency list is scanned at most once (the for-loop in line 13), the
total time spent scanning the edges is $O(E)$.  Finally, we check for
cycles.
\begin{tabbing}
17. \= \myfor\ \= $u \in V$\\
18. \> \> \myif\ \= $\ind[v] \neq 0$\\
19. \> \> \> print ``cycle exists''
\end{tabbing}
Lines 17 through 19 take $\Theta(V)$ time.  Therefore, the overall
running time of the algorithm is $O(V + E)$.

\BfPara{Proof of correctness:} The algorithm outputs vertices in the
right order because a vertex $v$ will not be output until its
in-degree becomes $0$, which happens only when every edge $(u,v)$
leading into $v$ has been ``removed'' due to the processing of $u$.
Furthermore, if there are no cycles, then all vertices are output.  We
prove this by contradiction.  Assume that some vertex $v_0$ is not
output.  This implies that some edge, say $(v_1, v_0)$ coming into
$v_0$ never got removed, which means that $v_1$ was not output.
Similarly, $v_1$ not output implies the existence of some vertex $v_2$
such that $(v_2, v_1)$ was not removed.  Since the number of vertices
is finite, this path $\ldots \rightarrow v_2 \rightarrow v_1
\rightarrow v_0$ is finite, so we must have two identical vertices in
this path, implying that the path is a cycle, thus yielding a
contradiction.

We finally show that if there is a cycle, then the in-degree of no
vertex in the cycle will go to zero and, thus, none of the vertices in
the cycle will be output.  Again, the proof is by contradiction.  Let
$v$ be the first vertex in a cycle to be output.  This implies that
the edge, say $(u,v)$, in the cycle that comes into $v$ must have been
removed.  But this can only happen if $u$ has been already output,
yielding a contradiction to the fact that the $v$ is the first vertex
in the cycle to be output.

{\bf 4. (15 points)} Let $T$ be any minimum spanning tree of $G$.  Let
$T'$ be a spanning tree of $G$, not necessarily a minimum spanning
tree.  Prove or disprove the following statement: The largest edge
weight of $T$ is at most the largest edge weight of $T'$.

{\bf Answer:} True. 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)$.  We now show that $w(e) \le w(e')$.  The proof
is by contradiction.  If $w(e) > w(e')$, then $T'' = T - e + e'$ is a spanning
of lesser weight than $T$, contradicting the fact that $T$ is an MST.
Thus $w(e) \le w(e')$, hence completing the proof.
\end{document}

