CS570 Analysis of Algorithms Spring 2017 Exam III Name Student ID Email Address Check if DEN Student Maximum Received Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total 20 16 16 16 16 16 1 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 B Part b a Missing color in subproblem definition 2 b Unclear description 2 3 a Missing color in recurrence 4 b 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 If wrong answer in part b 2 C Part c a b If no pseudo code 2 c d If wrong order of for loop color before house id 2 If the answer is not according to wrong answer in part b 4 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 D Part d 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 13 4 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 2 6 5 4 2 4 9 3 4 2 5 1 4 2 3 3 11 2 5 a Turn the circulation with lower bounds problem into a circulation problem without lower bounds 6 pts 4 3 7 1 4 1 0 3 6 2 3 …