\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS5800}{Algorithms}{Spring 2011}{13 February 2011}{7}

\begin{center}
\Large{\bf Problem Set 3 (due Wednesday, February 23)}
\end{center}

{\bf 1. (10 points)} Problem 3.16 of text.

{\bf 2. (10 points) One-way connected graphs}

Recall that a directed graph $G$ is strongly connected if for any two
vertices $u$ and $v$, there is a path from $u$ to $v$ {\em and}\/
there is a path from $v$ to $u$.  We say $G$ is {\em one-way connected} if
for any two vertices $u$ and $v$, either there is a path from $u$ to
$v$ {\em or} there is a path from $v$ to $u$ (or both).

For instance, the graph over 3 vertices $u, v, w$ and two edges $u
\rightarrow v$ and $v \rightarrow w$ is one-way connected.  On the
other hand, the graph over 4 vertices $u, v, w, x$ with four edges $u
\rightarrow v$, $u \rightarrow w$, $v \rightarrow x$, and $w
\rightarrow x$ is not one-way connected since neither there is a path
from $v$ to $w$ nor there is a path from $w$ to $v$.

Design a linear-time algorithm for determining whether a given
directed graph $G$ is one-way connected.

{\bf 3. (10 points) Network forensics} 

You are the chief network administrator of a large corporate network,
and have just been informed of a major virus infection in the network.
The entire network has been shut down to prevent further damage.  You
and your forensics team get down to business and immediately start
poring over the network logs to figure out what happened and when.
Your network consists of $n$ computers which we label $C_1$, $C_2$,
through $C_n$.  You are able to collect all communication information
in the form of $m$ triples of the form $(C_i, C_j, t)$, which means
that $C_i$ and $C_j$ communicated with each other at time $t$.

You know that the virus first infected computer $C_1$ from an external
source at time $0$.  From then on, there were no further infections
from outside the network.  But the virus is very infectious.  So if
$C_i$ communicated with $C_j$ at time $t$, and if one of them is
infected prior to the communication, then the other will certainly be
infected at time $t$.

Given the set of all communication triples, you would like to
determine (a) which computers have been infected at the current time,
(b) the precise times at which these computers were first infected,
and (c) for each infected computer, the path by which the infection
first reached the computer.  Design an efficient (time polynomial in
$n$ and $m$) algorithm to solve this problem, and analyze its
worst-case running time.  You may assume for convenience that all
times listed in the communication triples are integers.

{\bf 4. (10 points)} Problem 4.13 of text.

\end{document}