Homework 4

Due Wednesday, February 18

1. Let $G = (V, E)$ be a connected graph and $s \in V$. Suppose that breadth-first search (BFS) on $G$ from $s$ results in a BFS tree $T$ and that depth-first search (DFS) on $G$ from $s$ results in a DFS tree $T'$. Solve one of the following:

   (a) Prove that $T = T'$.

   (b) Prove that $T = T'$ is false with a minimal counterexample with the least number of nodes.

2. For a graph $G = (V, E)$, let $\sim$ be an equivalence relation on $V$ defined by $v \sim w$ if $w$ is reachable from $v$ for $v, w \in V$. The connected components of $G$ are the connected graphs within $G$ defined by the equivalence classes of $V$ under $\sim$ and the edges of $G$ connecting the nodes within such classes. For a given graph $G = (V, E)$, based on depth-first search, design an $O(n + m)$-time algorithm to identify the connected components of $G$; in particular, if $G$ has $k$ connected components, then, for $i = 1, \ldots, k$ and $v \in V$, your algorithm should assign $i$ to $v$ in case $v$ belongs to the $i$th connected component.

3. To monitor an outbreak of an infectious respiratory disease at a college, you have been asked to develop an efficient algorithm to contact-trace students with a high risk of being infected by a virus. In particular, your goal is, upon discovery of an infected student, to contact-trace and determine whether a given student is at a high risk of being infected based on their class attendance data. Formally, a student $s$ is said to be at a high risk if $s$ attended the same class with either (i) a student who had been infected by the virus (but did not know at the time of the class) or (ii) another student who had been identified to be at a high risk (but did not know at the time of the class). There are $n$ students at the college, and, as input, you are given a list of trace data indicating the times at which pairs of students were in the same class. In particular, the data is a sequence of $m$ ordered tuples of the form $(s, s', t)$, indicating that students $s$ and $s'$ were in the same class at time $t$. The $m$ triples are given in the order of time. For simplicity, we assume that each pair of students were in the same class at most once during the given time frame. Now, given such trace data, consider the following yes/no question:

   If it was discovered that a student $s$ was already infected at time $t$, could it possibly have put another student $s'$ at a high risk of being infected by time $t'$?

   Clearly, if $s$ and $s'$ were in the same class between $t$ and $t'$, then it would immediately put $s'$ at a high risk. However, even if $s$ and $s'$ were never in the same class, $s'$ could be put at a high risk through a sequence of pairs of other classmates all of whom had been identified to be at a high risk, originally caused by $s$'s infection. For example, for $n = 4$ and $m = 5$, consider the trace data consisting of: $$ (s_1, s_2, 8), (s_2, s_4, 9), (s_3, s_4, 9), (s_1, s_4, 11), (s_1, s_3, 12) $$ If it was discovered that $s_1$ was infected at 7, then $s_3$ would be at a high risk by 9, through $s_2$ and $s_4$ (although $s_1$ and $s_3$ were not in the same class until 12). On the other hand, if it was discovered that $s_2$ was infected at 10, then $s_3$ would not be at a high risk by 12 (in fact, no one else would be at a high risk anytime). Design an $O(n + m)$-time algorithm to answer, given such a sequence of trace data, the above yes/no question; that is, given students $s$ and $s'$ and times $t$ and $t'$, whether or not $s$ being infected at $t$ could put $s'$ at a high risk of being infected by time $t'$.

CPSC 320 home page