\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.
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}