Description
Question 1: Shortest Cycle Involving a Given Node.
You are given a directed graph G:(V,E)G:(V,E) using an adjacency list representation and a vertex (node) uu of the graph. Write an algorithm to perform the following tasks:
1(A) Write an algorithm that decides (true/false) whether the vertex uu belongs to a cycle.
What is the complexity for your algorithm in terms of the number of vertices |V||V| and the number of edges |E||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 uu.
What is the complexity for your algorithm in terms of the number of vertices |V||V| and the number of edges |E||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 00 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=0t=0.
we ask if a given person of interest PjPj could have been infected at a given time of interest t=Tt=T.
2(A) Write an algorithm that, given a person PjPj and time TT, determines if PjPj‘s mailbox was infected before or at time TT. What is the worst case complexity of your algorithm in terms of the number of persons |P||P|, and the number of emails sent |E||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 nn of e.g. moth specimen; (b) randomly select mm 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=4n=4 and the expert says that
Specimen # 11 is older than 22, 33 is older than 44, 44 is older than 22 and 22 is older than 33.
The expert’s opinion is clearly inconsistent.
Suppose n=4n=4 and the expert says that
Specimen # 11 is older than 22, 33 is older than 44 and 44 is older than 11. 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 GG with nn vertices as an adjacency list. Write an algorithm to check if GG has a cycle that runs in time Θ(n)Θ(n).
Hint A connected, undirected acyclic graph is a tree. Since you are already given that GG is connected, you are just checking if GG is a tree. How many edges would a tree have?
YOUR ANSWER HERE
