CS570 Analysis of Algorithms Spring 2017 Exam III Name: _____________________ Student ID: _________________ Email Address:________________ _____Check if DEN Student Maximum Received Problem 1 20 Problem 2 16 Problem 3 16 Problem 4 16 Problem 5 16 Problem 6 16 Total1) 20 pts Mark the following statements as TRUE or FALSE. No need to provide any justification. [ TRUE /] Given a minimum cut, we could find the maximum flow value in O(E) time. [/ FALSE ] Any NP-hard problem can be solved in time O(2^poly(n)), where n is the input size and poly(n) is a polynomial. [ TRUE /] Any NP problem can be solved in time O(2^poly(n)), where n is the input size and poly(n) is a polynomial. [ TRUE /] If 3-SAT ≤p 2-SAT, then P = NP. [/ FALSE ] Assuming P ≠ NP, there can exist a polynomial-time approximation algorithm for the general Traveling Salesman Problem. [/ FALSE ] Let (S,V−S) be a minimum (s,t)-cut in the network flow graph G. Let (u,v) be an edge that crosses the cut in the forward direction, i.e., u ∈ S and v ∈ V−S. Then increasing the capacity of the edge (u, v) necessarily increases the maximum flow of G. [/ FALSE ] If problem X can be solved using dynamic programming, then X belongs to P. [/ FALSE ] All instances of linear programming have exactly one optimal solution. [/ FALSE ] Let Y ≤p X and there exists a 2-approximation for X, then there must exist a 2-approximation for Y. [ TRUE /] There is no known polynomial-time algorithm to solve an integer linear programming.2) 16 pts A set of n space stations need your help in building a radar system to track spaceships traveling between them. The ith space station is located in 3D space at coordinates (xi, yi, zi). The space stations never move. Each space station i will have a radar with power ri, where ri is to be determined. You want to figure how powerful to make each space station’s radar transmitter, so that whenever any spaceship travels in a straight line from one space station to another, it will always be in radar range of either the first space station (its origin) or the second space station (its destination). A radar with power r is capable of tracking space ships anywhere in the sphere with radius r centered at itself. Thus, a space ship is within radar range through its trip from space station i to space station j if every point along the line from (xi, yi, zi) to (xj, yj, zj) falls within either the sphere of radius ri centered at (xi, yi, zi) or the sphere of radius rj centered at (xj, yj, zj). The cost of each radar transmitter is proportional to its power, and you want to minimize the total cost of all of the radar transmitters. You are given all of the (x1, y1, z1), ... ,(xn, yn, zn) values, and your job is to choose values for r1,...,rn. Express this problem as a linear program. (a) Describe your variables for the linear program. (3 pts) Solution: ri = the power of the ith radar transmitter., i=1,2,….,n (3 pts) (b) Write out the objective function. (5 pts) Solution: Minimize r1 +r2 +···+rn. Defining the objective function without mentioning ri : -3 pts (c) Describe the set of constraints for LP. You need to specify the number of constraints needed and describe what each constraint represents. (8 pts) Solution: ri +rj ≥ sqrt((xi - xj)2 + (yi - yj)2 + (zi - zj)2). Or, ri +rj ≥ di, j for each pair of stations i and j, where di, j is the distance from station i to station j (6 pts) we need Sigma_(i=1 to n-1) i = (n2-n)/2 constrains of inequality (2 pts)3) 16 pts Given a row of n houses that can each be painted red, green, or blue with a cost P(i, c) for painting house i with color c. Devise a dynamic programming algorithm to find a minimum cost coloring of the entire row of houses such that no two adjacent houses are the same color. a) Define (in plain English) subproblems to be solved. (4 pts) Solution: Let C(i, c) be the minimum possible cost of a valid coloring of the first i houses in which the last house gets color c. b) Write the recurrence relation for subproblems. (6 pts) Solution: The recurrence is C(i, c) = min c`≠ c {C(i − 1, c` ) + P(i, c)}. The base case: C(1, c) = P(1, c), for all colors c. c) Describe (using pseudocode) how the value of an optimal solution is obtained using iteration. (4 pts) Set r[1] = P(1,r),g[1] = P(1,g), b[1] = P(1,b) for i=2 to n r[i] = P(i,r) + min(g[i-1],b[i-1]) g[i] = P(i,g) + min(r[i-1],b[i-1]) b[i] = P(i,b) + min(r[i-1],g[i-1]) endfor return min{r[n], g[n], b[n]} d) Compute the runtime of the algorithm. (2 pts) Solution: O(n) The runtime is O(n) since there are n subproblems each of which takes O(1) time. Grading rubric: A. Part (a): a. Missing color in subproblem definition -2 b. Unclear description -2 ~ -3 B. Part (b): a. Missing color in recurrence -4b. Totally wrong recurrence -6 c. Fail to consider no same color in adjacent choice -2 d. Wrong symbols or typos in the recurrence -1 ~ -2 C. Part (c): a. If wrong answer in part (b) -2 b. If no pseudo code -2 c. If the answer is not according to wrong answer in part (b) -4 d. If wrong order of for loop, color before house id -2 D. Part (d): a. The question is graded according to recurrence and pseudo on part (b) and (c) b. If there is additional constant in big O notation -1 Common errors: 1. Failed to include the color of house in the definition of subproblem. a. Score if there are no other mistakes: part (a) -2, part (b) -4, part (c) -2 = 8 2. Each house must be painted into one of the three colors. a. Score if there are no other mistakes: part (a) -4, part (b) -4, part (c) -2 = 6 3. Use interval (2d state + 2 colors for the ends) a. Score if there are no other mistakes: part (a) -1, part (b) -1, part (c) -1 = 134) 16 pts In the network below, the demand values are shown on vertices (supply value if negative). Lower bounds on flow and edge capacities are shown as (lower bound, capacity) for each edge. Determine if there is a feasible circulation in this graph. You need to show all your steps. a) Turn the circulation with lower bounds problem into a circulation problem without lower bounds (6 pts) (2,4) (2,5) (2,6)(2,5)(2,3)(1,4) (3 4)9 -4 5 3 -11 2 3 4 3 1 3 1 0 5 -4 7 -6Grading rubric 1) a) There are total 12 values in the network-flow graph that needs to be written, 5 values (demands) on vertices and 7 values on edges (modified capacities). For each correct value 0.5 marks will be awarded. b) 2 marks will be