Homework 3
COMS 311 Points: 100
Due: Sept 18, 11:59PM
Late Submission Sept 19, 11:59PM (20% penalty)
Late submission policy. If you submit by Sept 19, 11:59PM, there will be 20% penalty. That is, if your score is x points, then your final score for this homework after the penalty will be 0.8 × x. Submission after Sept 19, 11:59PM will not be graded without explicit permission from the instructors.
Submission format. Your submission should be in pdf format. Name your submission file:
If you are planning to write your solution and scan+upload, please make sure the submission is readable (sometimes scanned versions are very difficult to read – poor scan quality to blame).
If you plan to snap pictures of your work and upload, please make sure the generated pdf is readable – in most cases, such submissions are difficult to read and more importantly, you may end up submitting parts of your work.
If you would like to type your work, then one of the options you can explore is latex.
Rules for Algorithm-design Problems.
1. For all algorithm design problems, part of the grade depends on the run-time. Better the run-time, higher the grade.
2. You may use any standard algorithms that we have covered as part of the lecture sessions (e.g., Binary Search, heap operations, Breadth-first exploration with Layers)
3. Write Pseudo-code for your algorithms.
Learning outcomes.
1. Design algorithms (e.g., Graph Exploration)
1
1. There are n tennis players. There are m-pairs among these players who are bitter rivals of each other. Write an algorithm which checks whether the players can be arranged in two groups such that rival players are in separate groups; and if the check is successful, then your algorithm also outputs the two groups. Derive the runtime of your algorithm.
2. Given an undirected connected graph G = (V,E), write an algorithm to determine whether there exists a cycle in the graph. Derive the runtime of your algorithm.
3. Given an undirected connected graph, we define the diameter of the graph as the length of the longest shortest path between any two vertices in the graph. In other words, in a graph with n vertices {v0, v1, . . . , vn−1}, if the shortest path between the vertex pair vi, vj is denoted by πij, then the diameter of the the graph is maxi∈[0,n−1],j∈[0,n−1](|πij|). Write an algorithm that determines the diameter of an undirected connected cycle-free graph. Derive the runtime of your algorithm.
4. Let G = (V, E) is a directed graph representing the road network of the village Totorum. The roads are one-way represented by directed edges and are of equal length L; each house in the village is represented by the nodes in the graph. Every day, the village doctor visits every house in the graph. For this, the doctor does the following
for every house v in the village
the doctor takes the shortest path from her residence to v
the doctor takes the shortest path from v to her residence
Determine the total distance traveled by the doctor every day. (Assume every house can be reached from the doctor’s residence and doctor’s residence can be reached from every house)
5. Suppose that an n-node undirected graph G = (V,E) contains two nodes s and t such that the distance between s and t is strictly greater than n/2. Show that there must exist some node v, not equal to either s or t, such that deleting v from G destroys all paths between s and t. Write an algorithm to find such a v. Derive the runtime of your algorithm.
2