Question 1: Shortest Cycle Involving a Given Node.

You are given a directed graph $G:(V,E)$ using an adjacency list representation and a vertex (node) $u$ of the graph. Write an algorithm to perform the following tasks:

1(A) Write an algorithm that decides (true/false) whether the vertex $u$ belongs to a cycle.

What is the complexity for your algorithm in terms of the number of vertices $|V|$ and the number of edges $|E|$?

Note: Throughout this assignment you may describe your algorithms using words and definitely use algorithms that you have already learned in class. A brief description will do.

YOUR ANSWER HERE

1(B) Write an algorithm which prints the smallest length cycle involving the vertex $u$.

What is the complexity for your algorithm in terms of the number of vertices $|V|$ and the number of edges $|E|$?

YOUR ANSWER HERE

Question 2: Tracing an Epidemic

An email with a malicious attachment has evaded the antivirus software of company X. We know that the CEO’s computer was infected during a business trip last month. Since then,investigators have been trying to determine whose mailboxes could be infected. For an employee’s mailbox to be infected, he or she must have received and read an email sent by an already affected employee.

Starting from the time $0$ denoting when the CEO’s mailbox was first infected, investigators have “metadata” for all the emails from all employees in the form

(Pi,Pj,tk,tl)(Pi​,Pj​,tk​,tl​) meaning that employee PiPi​ sent an email at time tktk​ to employee PjPj​, and PjPj​ opened the email at time tl>tktl​>tk​. We assume that PjPj​‘s mailbox is infected instantaneously at time tltl​ if PiPi​‘s mailbox was infected before time tktk​.

You are given a collection of email records in the form given above, and you know that person P0P0​ is the CEO who was infected at time $t=0$.

we ask if a given person of interest PjPj​ could have been infected at a given time of interest $t=T$.

2(A) Write an algorithm that, given a person PjPj​ and time $T$, determines if PjPj​‘s mailbox was infected before or at time $T$. What is the worst case complexity of your algorithm in terms of the number of persons $|P|$, and the number of emails sent $|E|$.

Hint You need to first make a graph that represents the possible flow of the “infection” through emails. It is easier to make a complicated graph (in this case, one where each vertex represents more than just a person) and then run a simple graph algorithm (one of the vanilla algorithms we learned this week, ie BFS/DFS/Topological sort) rather than making a simple graph and running a complicated ad-hoc algorithm on it (If your algorithm requires table lookups or passing on metadata specific to the problem at hand, it’s probably too complicated).

YOUR ANSWER HERE

2(B) Write an algorithm that prints out each person who is infected in increasing order of the times in which they first got infected.

YOUR ANSWER HERE

Question 3: Testing Moth Age Expert

A person claims to have spent his life studying the emperor gum moth Opodiphthera eucalypti. Given two moth samples, he claims to tell us which one is the older. Of course, we ourselves are no experts and they all in fact look the same to us.

We test the person as follows: (a) collect a large number $n$ of e.g. moth specimen; (b) randomly select $m$ different pairs from our collection and have the person tell us which one is older; (c) record their answers and analyze them to see if they are consistent

Write an algorithm to detect if the “expert” opinions are consistent.

Hint: We have refrained from discussing what consistency means in this case. But can provide you an example as a hint.

Example

Suppose $n=4$ and the expert says that

Specimen # $1$ is older than $2$, $3$ is older than $4$, $4$ is older than $2$ and $2$ is older than $3$.

The expert’s opinion is clearly inconsistent.

Suppose $n=4$ and the expert says that

Specimen # $1$ is older than $2$, $3$ is older than $4$ and $4$ is older than $1$. The expert’s answer is consistent.

YOUR ANSWER HERE

Question 4: Testing if an undirected graph is acyclic

You are given a strongly connected, undirected graph $G$ with $n$ vertices as an adjacency list. Write an algorithm to check if $G$ has a cycle that runs in time $\Theta (n)$.

Hint A connected, undirected acyclic graph is a tree. Since you are already given that $G$ is connected, you are just checking if $G$ is a tree. How many edges would a tree have?

YOUR ANSWER HERE