CIT 596 - HW5 (deadlines as per Gradescope)

This homework deals with the following topics

* DAGs , Top sort.

* BFS.

* DFS.

Student Name: 〈 Your Name 〉

Collaborator(if any) : 〈 Your Collaborators 〉 (at most 2 other collaborators.)

Please read these instructions

• No handwritten solutions. Handwritten solutions get a 0.

• WEAPARTE = Write an Efficient Algorithm in plain English (or pseudocode if you must), Analyze its Run Time, with an Explanation.

• The homework has to be submitted in electronic form. as a pdf file. You can use any editing software you want in order to produce the pdf.

• Unless otherwise specified you HAVE to explain your answer. Please write explana-tions.

• If any question involves making a graph you have to tell us what the vertices are and what the edges are before you apply any algorithm. In many cases the question actually is mainly about how some kind of real world problem can be mapped to a graph theory problem.

• You cannot use any inbuilt function of your favourite programming language. If you are unsure what is allowed and what is not allowed in pseudocode, please look at the book. Remember that you are writing an algorithm and not Java or Python or Scala or whatever.

• If a question has a recursive algorithm, you have to provide the recurrence and then solve it using some theorem or just expanding the recurrence.

• As with all HWs, we are looking for the most efficient algorithm in terms of running time. The algorithm also has to be correct (you do not have to worry about graphs with no edges and small edge cases like that though).

• We will not worry about the distinction between O and Θ. As long as you provide a tight bound (for example if an algorithm is actually O(n log n) and you say O(n3) you will lose points) you are fine.

• If you are explaining the running time of a graph, it is important to mention whether your graph is being stored in an adjacency list representation or an adjacency matrix representation.

• The number of points associated with a question is a general guideline for toughness and/or amount of writing we expect. Sometimes a question might be worth 4 or 5 points only because it is lengthy.

• If you want to draw a graph for your HWs I would recommend using google drawing or graphviz or draw.io. Once you have a picture just use the includegraphics command (as you can see in this tex file).

• A result shown in class and/or provided by the textbook (Algorithms Unlocked) can be used as is.

• You are allowed to write things like ”Run merge sort” or ”Run binary search”. Re-member that if you do so, we will assume you mean the standard (as per the text-book/lecture) algorithm. If you want to modify an algorithm then it is your job to write out the full pseudocode. You are allowed to use the pseudocode from the textbook or from CLRS as a starting point.

Questions

1. (2 points) Assume that you want to store what we’ll call an Insta graph. Each and every person with an Instagram account is a vertex, and if person X follows person Y there is an edge from X to Y. Will you pick the adjacency list representation or the adjacency matrix representation for this graph. Why? You are allowed to and encouraged to see what following a person on Instagram means in case you do not know how Instagram works.

2. (4 points) Given the graph below (adjacency list representation), run a DFS on it start-ing from vertex b. Please compute the discovery times and finish times for every single vertex. Also, classify all edges of the graph as either tree edges, forward edges, back edges, or cross-edges.

3. (4 points) We are trying to figure out the number of collaboration groups in CIT5960. We have been given all the information in terms of a file that has each person’s collabo-rators that they listed when they submitted their HW (imagine the TAs wrote some cool code to do this from your pdf submissions). For instance we have info like this (Boulos listed no collaborators)

Arvind - Boulos, Paul

Paul - Boulos

Yi - Arvind

George - John, Muhammad

Muhammad - George, John

Boulos -

John - George, Muhammad

We know that this file has the following rules

• Every student in class appears exactly once.

• Every student is going to list at most 2 other people.

• There are N students in this class.

Using this information, determine the number of collaboration groups using the BFS algorithm as your helper.

In the above example there are 2 collab groups. [George, Muhammad, John] and [Yi, Boulos, Paul, Arvind]. The fact that it breaks perhaps some rule of the course is imma-terial. It is also reflective of the real world but let us not get swayed by emotions over here.

Write your approach using just plain English. Then analyze your algorithm for runtime with an explanation.

4. (5 points) A tree is an undirected, connected, acyclic graph. Given an undirected graph G(you know this is undirected) in adjacency list representation WEAPARTE to figure out whether the graph is a tree or not.

5. (10 points) You are given the task of assisting a group of historians make sense of some data that they have procured by conversing with citizens of a remote island to learn about the lives of people who have lived there over the past 100 years.

From these interviews, they’ve learned about a set of n people (all currently dead). Let us denote them as P1, P2, . . . , Pn. They have a collection of relative facts about these people.

There might not be a fact about every pair of people. It is also possible to not have any fact about someone.

Also (for the sake of us not having to deal with some quirks) the historians are told that no person died on the same day that someone else was born.

Each fact either tells us

• person Pi died before Pj was born. If you are concerned about how exactly this input is provided, think of it as a list of ordered pairs.

• person Pi overlapped at least partially with person Pj . If you are concerned about how exactly these facts are provided, think of it as a list of unordered pairs.

They are not sure that all these facts are correct. It has been many years and the islanders have not kept good records. So what they would like you to determine is whether the data they have collected is at least internally consistent - can this set of people actually satisfy all the facts that you got.

WEAPARTE for this problem. This problem is slightly different in that the main goal is to construct a ‘useful’ graph from the facts that have been provided. After that graph is created, the problem is relatively simple. Please walk us through how you construct the graph. What are the vertices? What are the edges?

Your algorithm should either say ‘OK’ meaning that all the facts could hold true, or it should report (correctly) that no such dates can exist - that is, the facts collected are not internally consistent.