The default requirements to be eligible for full credit are all of the following:

$($a$)$ Describe your algorithm clearly in English.

$($b$)$ Give pseudocode.

$($c$)$ Argue correctness, even if you don$$t give a formal proof and give a convincing

argument instead.

$($d$)$ Give with explanation the best upper bound that you can for the running time. Question: You are helping some security analysts monitor a collection of networked computers tracking the spread of an online virus. There are n computers in the system, labelled

C$1,$ C$2,...,$ Cn$.$ You are given a trace indicating the times at which pairs of computers communicated. The trace consists of m triples $($Ci

$,$ Cj $,$ tk$)$; such a triple indicates that Ci and Cj

communicated at time tk$.$ At this time, a virus could have spread from Ci to Cj $,$ and vice

versa.

We assume that the trace holds the triples sorted by time. For simplicity, we assume that

each pair of computers communicate at most once over the time of the trace. Also, it is

possible to have pairs $($Ci

$,$ Cj $,$ tk$)$ and $($Ci

$,$ C$`$

$,$ tk$)$; this would indicate that Ci communicated

with both Cj and C$`$ at time tk$,$ allowing a virus to spread in any way among the $3$ machines.

We would like to answer questions of the following form: If a virus was introduced at Ci at

time x$,$ could it have spread to Cj at time y$?$ That is$,$ is there a sequence of communications

that could have led a virus introduced at Ci at time x to move to Cj by time y$?$

Design an algorithm that, given as input a collection of $($sorted$)$ trace data and a virus query,

gives a yes$/$no answer to the query. Your algorithm should run in time O$($m $+$ n$).$