Homework 3 Solution

Following are the problems to be handed in, 25 points each. Maximum score for this homework is 100 points.




(Graphs, 2-page limit { your solutions should t on two sides of 1 page).



You are managing the creation of a large software product. You have the following information:




A set V of n small projects that are part of your software product.



A set E of pairs of projects in V . A pair (u; v) is in E if project u must be completed before project v is started. There are no cycles in E.



For each project u 2 V , a duration tu 2 N. This is the amount of time the project will take from start to nish.



You can do any number of projects in parallel, but you can’t start a project before all of its predecessors (according to the list E) are completed.




Given this information, you want to know two things: First, how soon can each of the projects be completed? Second, which projects are critical? We say a project is critical if increasing its duration by 1 would delay the completion of the entire product.




For example, in the following picture, nodes represent projects, and numbers inside nodes are durations. Critical nodes are colored gray.







6!
2!
3!




4!
5!


6!
2!


5!


2!






Give an algorithm that takes the inputs above and returns:




(a) For each project u 2 V , the earliest possible completion time c(v).




2
(b) A list of the critical projects.




Give the running time and space complexity for your algorithm. Prove that your algorithm is correct. (Hint: You may want to compute the completion times c(v) rst, then look for critical projects.)




(Dynamic Programming, 2-page limit { your solutions should t on two sides of 1 page).



You are managing the construction of power plants along a river. As opposed to the last problem that involved construction along a river, this time around the possible sites for the power plants are given by real numbers x1; :::; xn, each of which speci es a position along the river measured in miles from its spring. Assume that the river ows in a completely straight line. Due to di erences in the water ow, the position of each power plant in uences its capacity for energy production. In other words, if you place a power plant at location xi, you will produce a quantity of electricity of ri 0 MW1.




Environmental regulations require that every pair of power plants be at least 5 miles apart. You’d like to place power plants at a subset of the sites so as to maximize total energy production, subject to this restriction. The input is given as a list of n pairs (x1; r1); :::; (xn; rn) where the xi’s are sorted in increasing order.




Your foreman suggests some very simple approaches to the problem, which you realize will not work well. For each of the following approaches, give an example of an input on which the approach does not nd the optimal solution:



Next available location: put a power plant at i = 1. From then on, put a power plant at the smallest index i which is more than ve miles from your most recently placed power plant.



Most pro table rst: Put a power plant at the most pro table location. From then on, place a power plant at the most pro table location not ruled out by your current power plant.



Give a dynamic programming algorithm for this problem. Analyze the space and time complexity of your algorithm.



To make it easier to present your answer clearly, try to follow the steps below (as with any design process, you may have to go back and forth a bit between these steps as you work on the problem):




Clearly de ne the subproblems that you will solve recursively (note: weighted interval scheduling should be a good source of inspiration here).



Give a recursive formula for the solution to a given subproblem in terms of smaller subproblems. Explain why the formula is correct.



Give pseudocode for an algorithm that calculates the pro t of the optimal solution. Analyze time/space and explain why the algorithm is correct (based on previous parts).



Give pseudocode for an algorithm that uses the information computed in the previous part to output an optimal solution. Analyze time/space and explain why the algorithm is correct.



(Dynamic Programming, 2-page limit { your solutions should t on two sides of 1 page). Let G = (V; E) be a directed graph with nodes v1,...,vn. We say that G is an ordered graph if it has the following properties.






this stands for megawatts, but don’t concern yourself with the unit of measurement






3
Edges go from a node with a lower index to a node with a higher index. In other words, every directed edge has the form (vi; vj ) with i < j.



Each node with the exception of vn has at least one edge leaving it. In other words, for every node vi; i = 1; 2; :::; n 1, there is at least one edge of the form (vi; vj ).



The length of a path is the number of edges in it. See the following example.







v1 v2










v4







v3 v5







The correct answer for the above graph is 3: The longest bath from v1 to vn uses the three edges (v1; v2), (v2; v4), and (v4; v5). The goal in this question is to solve the following problem.

Given an ordered graph G, nd the length of the longest path that begins at v1 and ends at vn.




Show that the following algorithm does not correctly solve this problem, by giving an example of an ordered graph on which it does not return the correct answer.



Set a = v1




Set L = 0




While there is an edge out of node a

Choose the edge (a; vj ) for the smallest possible j

Set a = vj




Increase L by 1




Return L as the length of the longest path




In your example, say both what the correct answer is and what the algorithm above nds.




Give an e cient algorithm that takes an ordered graph G and returns the length of the longest path that begins at v1 and ends at vn.



(Graphs, 2-page limit { your solutions should t on two sides of 1 page).



Suppose that you have a directed graph G = (V; E) with an edge weight function w and a source vertex s 2 V . The weights can be negative, but there are no negative weight cycles. Furthermore, assume that all edge weights are distinct (i.e. no two edges have the same weight). The single source shortest path problem is to nd the shortest path distances from s to every vertex in V .




Suppose that you also guaranteed that for all v 2 V , a shortest path from s to v has increasing edge weights. Give an algorithm to nd the shortest path distances from s to every vertex in V . Analyze the running time of your algorithm and explain why it is correct. For full credit, your algorithm should run in time O(V + E log E).



4
A sequence is bitonic if it monotonically increases and then monotonically decreases, or if by a circular shift it monotonically increases and then monotonically decreases. For example the sequences (1; 4; 6; 8; 3; 2), (9; 2; 4; 10; 5), and (1; 2; 3; 4) are bitonic, but (1; 3; 12; 4; 2; 10) is not bitonic. Now, suppose that the sequences of edge weights along the shortest paths are no longer guaranteed to be increasing, but instead are guaranteed to be bitonic. Give a single source shortest path algorithm, explain why it is correct, and analyze its running time. For full credit, your algorithm should run in time O(V + E log E).











































































































































































5