\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}
\\ Due April 23 in Recitation
\end{center}
\begin{quote}
For every complex problem there is a simple solution. And it's always wrong.
\\ H.L. Mencken, 1880-1956, American satirist.
\end{quote}
\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!
\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.
\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}
boxers 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!
\item Show how DFS works on Figure B. All lists are alphabetical
except we put R before Q so it is the first letter.
Show the discovery and finishing time for each vertex.
\item Show the ordering of the vertices produced by {\tt TOP-SORT}
when it is run on Figure C, with all lists alphabetical.
\item Let $G$ be a DAG with a specific designated vertex $v$.
Uno and Dos (Spanish for One and Two) 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. Indeed, argue that if
$G$ has $n$ vertices then the game {\em cannot} take more than
$n-1$ moves. (Key: Its a DAG!)
\item Define {\tt VALUE[z]} to be the winner of the game
(either Uno or Dos) where the token is initially placed
at vertex $z$ and Uno plays first.
(That is, {\tt VALUE[z]}
being Uno means that the player who has the move will win,
{\tt VALUE[z]} being Dos means that the player who has the
move will lose.)
When $z$ is a leaf node
and Uno plays first, Uno has no move and so loses and therefore
{\tt VALUE[z]} is Dos. But what if $z$ is {\em not} a leaf node.
Suppose the {\tt VALUE[w]} are known for all $w\in Adj[z]$.
How do those values determine {\tt VALUE[z]}? (To give part of
the answer: Suppose there is some $w\in Adj[z]$ with {\tt VALUE[w]}
equal Dos. From $z$ Uno's winning strategy is to move to $w$.)
\item Using the above idea modify {\tt DFS-VIST[v]}
to find who wins the original game. In your modified algorithm
there will be an extra function {\tt VALUE[w]} which is originally
set to {\tt NIL} for all vertices $w$, representing that the winner
of the game starting at $w$ has not yet been determined. When
the unmodified {\tt DFS-VISIT[w]} would be finished add a couple
of lines of pseudocode to give {\tt VALUE[w]}.
Give an upper bound on the time of your algorithm.
\een
\een
\begin{quote}
I cannot live without people. -- Pope Francis
\end{quote}
\end{document}