Homework 5
COMS 311 Points: 100
Due: Oct 16, 11:59PM
Late Submission Due: Oct 17 (20 % penalty)
Late submission policy. If you submit by Oct 17, 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 Oct 17, 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, Dijkstra, Prim)
3. Write Pseudo-code for your algorithms.
4. For all graph problemt the vertex set is V = {1,2,··· ,n}
Learning outcomes.
1. Graphs Algorithms: DFS, Shortest Paths, MST 2. Greedy Algorithms
1
1. Let G = (V,E) be a directed graph. Given a vertex v let from(v) denote the set of vertices that have a path from v (excluding v), and let to(v) be the set of vertices from which there is a path to v. A vertex v is (1/4, 3/4)-bridge, if the size of f rom(v) is (n − 1)/4, the size of to(v) is 3(n − 1)/4,and from(v) ∩ to(v) = ∅. Given a graph (where n − 1 is divisible by 4), give an algorithm that outputs all (1/4, 3/4)-bridge vertices. If the graph does not have such bridge vertices, then the algorithm returns null. Prove the correctness and derive the runtime.
2. Let G = (V, E) be a directed, weighted graph with positive edge weights and let s ∈ V . Recall that any tree Π rooted at s can be represented by a parent array as follows: Π(s) = null and Π(x) = parent of x in the tree.
• Suppose that Π is a shortest path tree of G rooted at s. Give an algorithm, that gets G and Π as input, and computes the length of the shortest path from s to every vertex. Derive the runtime.
• You are given a candidate shortest path tree Π. Given an algorithms that gets G and Π as input, and checks if Π is indeed a shortest path tree. Justify the correctness and derive runtime.
3. Let G = (V,E) be an undirected, connected and weighted graph and let T be its Minimum Spanning Tree. Let G′ be a graph obtained by decreasing weight of an edge e ∈ E by a positive quantity x. Give an algorithm that gets G,T , e and x and computes a MST of G′. Your algorithm must run in O(m + n) time. Prove correctness of your algorithm and state its runtime.
4. Consider a simplistic pipeline of a car manufacturing plant consisting of two phases. In the first phase, a robot assembles all the parts of a car. The second phase paints the assembled car. There is only one robot and thus only one car can be assembled at a time. However, the plant has enough employees (and supplies) who can paint the car. Thus multiple cars can be painted at the same time (in parallel). Different types of cars take different amounts of time to be assembled (by the robot) and painted (by the employees). Suppose that car Ci requires ai minutes of assembling time, plus pi minutes of painting time. The goal is to write an algorithm that, given a set of n cars C1, C2, · · · Cn along with their assembling and painting times, determines a schedule Ci1 , Ci2 , . . . , Cin such that all the cars are completely finished (assembled and painted) in the shortest overall time.
• Consider the schedule obtained by sorting the assembly times in decreasing order. Show that this algorithm does not produce optimal answer.
• Consider the schedule obtained by sorting the paint times in decreasing order. Prove that this algorithm produces optimal solution. Use exchange argument to prove the correctness.
You may assume that all assembly as well as paint times are distinct.
2