\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 November 21 in Recitation
\end{center}
\begin{quote}
What's terrible is to pretend that second-rate is first-rate.
To pretend that you don't need love when you do; or you like
your work when you know quite well you're capable of better.
\\ Doris Lessing, 1919-2013
\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 wrestlers. Between any two
pairs of wrestlers 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 wrestlers (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 wrestles as {\tt GOOD} and the others
as {\tt BAD} such that each rivalry is between a {\tt GOOD}
wrestler and a {\tt BAD} wrestler. 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 wrestlers 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}