\documentclass[11pt]{article}
\pagestyle{empty}
\newcommand{\sig}{\sigma}
\newcommand{\ra}{\rightarrow}
\newcommand{\eps}{\epsilon}
\newcommand{\gam}{\gamma}
\newcommand{\ah}{\alpha}
\newcommand{\ben}{\begin{enumerate}}
\newcommand{\een}{\end{enumerate}}
\newcommand{\hsa}{\hspace*{1cm}}
\newcommand{\hsb}{\hspace*{2cm}}
\newcommand{\So}{\\ {\tt Solution:}}
\begin{document}
\begin{center} {\Large\bf Fundamental Algorithms, Assignment 9\\
Solutions}
\end{center}
\ben
\item Consider the undirected graph with vertices $1,2,3,4,5$ and adjacency
lists (arrows omitted) $1:25$, $2:1534$, $3:24$, $4:253$, $5:412$. Show the $d$ and
$\pi$ values that result from running BFS, using $3$ as a source. Nice picture, please!
\So \\ BFS: $3,2,4,1,5$ \\$d[3] = 0$, $\pi[3] = nil$ \\$d[2] = 1$, $\pi[2] = 3$ \\$d[4] = 1$, $\pi[4] = 3$ \\$d[1] = 2$, $\pi[1] = 2$ \\$d[5] = 2$, $\pi[5] = 2$
\item Show the $d$ and $\pi$ values that result from running BFS on the undirected
graph of Figure A, using vertex $u$ as the source.
\So \\$d[U] = 0$, $\pi[U] = nil$ \\$d[T] = 1$, $\pi[T] = U$ \\$d[X] = 1$, $\pi[X] = U$ \\$d[Y] = 1$, $\pi[Y] = U$ \\$d[W] = 2$, $\pi[W] = T$ \\$d[S] = 3$, $\pi[S] = W$ \\$d[R] = 4$, $\pi[R] = S$ \\$d[V] = 5$, $\pi[V] = R$
\item
We are given a set $V$ of boxers. Between any two
pairs of boxers there may or may not be a rivalry.
Assume the rivalries
form a graph $G$ which is
given by an adjacency list representation, that is,
$Adj[v]$ is a list of the rivals of $v$. Let $n$ be
the number of boxers (or nodes) and $r$ the number
of rivalries (or edges). Give a $O(n+r)$ time
algorithm that determines whether it is possible to
designate some of boxers as {\tt GOOD} and the others
as {\tt BAD} such that each rivalry is between a {\tt GOOD}
boxer and a {\tt BAD} boxer. If it is possible to
perform such a designation your algorithm should produce it.
\par Here is the approach: Create a new
field ${\tt TYPE}[v]$ with the values {\tt GOOD} and
${\tt BAD}$. Assume that the boxers are in a list $L$
so that you can program: For all $v\in L$. The idea will
be to apply {\tt BFS[v]} -- when you hit a new vertex
its value will be determined. A cautionary note: {\tt BFS[v]}
might not hit all the vertices so, just like we had {\tt DFS}
and {\tt DFS-VISIT} you should have an overall {\tt BFS-MASTER}
(that will run through the list $L$) and, when appropriate,
call {\tt BFS[v]}.
\par {\tt Note:} The cognescenti will recognize that we are
determining if a graph is bipartite!
\So The idea here is to call the first boxer {\tt GOOD}.
When someone is adjacent to someone {\tt GOOD} they are
called {\tt BAD} and if they are adjacent to someone {\tt BAD} they are
called {\tt GOOD}. But if in the adjacency list you come upon
someone who has already been labelled (that is, not white) then you
must check if there is a contradiction. A further problem: {\tt BFS[v]}
will only explore the connected component of $v$, if that is labelled
with no contradiction then you must go on to the other vertices.
So we start with everything white. The ``outside" program is:
\\ For all $v\in L$
\\ If $COLOR[v]=WHITE$ (*else skip*) then {\tt BFSPLUS[v]}.
\par {\tt BFSPLUS[v]} starts by setting ${\tt TYPE}[v]=GOOD$.
Then it runs {\tt BFS[v]} with two additions. When $u\in Adj[w]$
and $u$ is white you define ${\tt TYPE}[u]$ to be the opposite
of ${\tt TYPE}[w]$. When $u$ is not white you check if
${\tt TYPE}[w]={\tt TYPE}[u]$. If not, ignore. But if so exit
the entire program with {\tt NO DESIGNATION POSSIBLE} printout.
\item Show how DFS works on Figure B. All lists are alphabetical.
Show the discovery and finishing time for each vertex.
\So \\$Discovery\;order: R U Y Q S V W T X Z$
\\$Finishing\;order: W V S Z X T Q Y U R$
\\$Stack: push(R)\;push(U)\; push(Y)\;push(Q)\;push(S)\;push(V)\;push(W)\\pop(W)\;pop(V)\;pop(S)\;push(T)
\;push(X)\;push(Z)\;pop(Z)\\pop(X)\;pop(T)\;pop(Q)\;pop(Y)\;pop(U)\;pop(R)$
\item Show the ordering of the vertices produced by {\tt TOP-SORT}
when it is run on Figure C, with all lists alphabetical.
\So We apply {\tt DFS} to the graph. The first letter is $M$ so
we apply {\tt DFS-VISIT(M)}
\begin{center}
\begin{tabular}{rrr}
v & s[v] & f[v] \\ \hline
M & 1 & 20 \\
Q & 2 & 5 \\
T & 3 & 4 \\
R & 6 & 19 \\
U & 7 & 8 \\
Y & 9 & 18 \\
V & 10 & 17 \\
W & 11 & 14 \\
Z & 15 & 16
\end{tabular}
\end{center}
Note, for example, that though X is in Adj[M] it doesn't affect DFS.
At time $19$ R finishes and returns control to $M$. $M$ looks at
$X$ in its adjacency list but it is no longer white and so ignores
it. At this stage all vertices are black except $N,O,P,S$ which
as white. In this particular example $N$ is the letter right
after $M$ but in the general case DFS would skip over those
vertices which weren't white. Indeed, right after DFS-VISIT
all vertices are white or black. So next we do {\tt DFS-VISIT(N)}.
Note that the time does {\em not} restart! Note also that the
now black vertices, such as $U\in Adj(N)$ and $R\in Adj(O)$, do
not play a role
\begin{center}
\begin{tabular}{rrr}
v & s[v] & f[v] \\ \hline
N & 21 & 26 \\
O & 22 & 25 \\
S & 23 & 24
\end{tabular}
\end{center}
Finally we do {\tt DFS-VISIT(P)}. This one is quick. The adjacency
list of $P$ consists only of $S$ which is already black. So
\begin{center}
\begin{tabular}{rrr}
v & s[v] & f[v] \\ \hline
P & 27 & 28
\end{tabular}
\end{center}
The sort is the list of vertices in the reverse order of their
finish. In the algorithm when a vertex finishes we place it
at the {\em start} of a linked list, initially nil. At the
end, with negligible extra time, we have the list:
\[ PNOSMRYVXWZUQT \]
\item Let $G$ be a DAG with a specific designated vertex $v$.
Uno and Dos play the following game.
A token is placed on $v$. The players alternate moves, Uno
playing first. On each turn if the token is on $w$ the player
moves the token to some vertex $u$ with $(w,u)$ an edge of
the DAG. When a player has no move, he or she loses. Except
for the first part below, we assume Uno and Dos play perfectly.
\ben
\item Argue that the game {\em must} end.
\So Let $G$ have $V$ vertices. If the game went on for $V$ moves
the chip would hit $V+1$ positions $v=v_0,v_1,\ldots,v_V$ and
so some position would be hit twice -- some $i