CS570 Summer 2018 Analysis of Algorithms Exam III Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total Points 20 16 16 16 16 16 100 Instructions 1 This is a 2 hr exam Closed book and notes 2 If a description to an algorithm or a proof is required please limit your description or proof to within 150 words preferably not exceeding the space allotted for that question 3 No space other than the pages in the exam booklet will be scanned for grading 4 If you require an additional page for a question you can use the extra page provided within this booklet However please indicate clearly that you are continuing the solution on the additional page 5 Do not detach any sheets from the booklet Detached sheets will not be scanned 6 If using a pencil to write the answers make sure you apply enough pressure so your answers are readable in the scanned copy of your exam 7 Do not write your answers in cursive scripts 1 20 pts Mark the following statements as TRUE or FALSE No need to provide any justification TRUE FALSE An undirected graph is said to be Hamiltonian if it has a cycle containing all the vertices Based on this definition is the following true or false Any DFS tree on a Hamiltonian graph must have depth V 1 TRUE FALSE At the termination of the Bellman Ford algorithm even if the graph has a negative length cycle a correct shortest path is found for a vertex for which shortest path is well defined TRUE FALSE The main difference between divide and conquer and dynamic programming is that divide and conquer solves problems in a top down manner whereas dynamic programming does this bottom up TRUE FALSE If problem A is polynomial time reducible to a problem B i e A p B and B is NP complete then A must be NP complete TRUE FALSE If problem A is polynomial time reducible to a problem B i e A p B and A is NP complete then B must be NP complete TRUE FALSE Flow f is maximum flow if and only if there are no augmenting paths TRUE FALSE If P NP then the general optimization problem TRAVELING SALESPERSON has a poly time approximation algorithm with approximation factor 1 5 TRUE FALSE We currently only have a weakly polynomial time solution for the 0 1 knapsack problem but not a strongly polynomial time solution TRUE FALSE Suppose that all edge capacities c e is a multiple of Then the value of the maximum flow is also a multiple of TRUE FALSE Suppose that all edge capacities c e is a multiple of In a maximum flow f the flow f e on edge e is always a multiple of 2 16 pts Recall that in exam 1 just a couple of weeks ago you were asked to find a polynomial time solution to this problem Input Undirected connected graph with edge weights We are also given U which is a subset of vertices of the graph Output Find the spanning tree of minimum total weight such that all nodes of U have degree 1 Now prove that the following problem MST D2 is NP Hard Input Undirected connected graph with edge weights We are also given U which is a subset of vertices of the graph Output Find the spanning tree of minimum total weight such that all nodes of U have degree 2 if such a tree exists Solution Show that Hamiltonian Path p MST D2 Given G an undirected graph an instance of the Hamiltonian Path problem we will construct G an undirected graph with unit weights on all edges Then for every pair of nodes in G say v and u we will call the black box that solves MST D2 and set U V v u There will be O n2 calls to the black box If any of these calls returns a tree such that all nodes in the tree have degree 2 except for v and u it means that we have found a Hamiltonian Path in G with v and u as its end points If none of the calls to the black box manage to return such a tree then we can conclude that G has no Hamiltonian Paths Rubric 8 pts if the transformation is correct and sound 8 pts for the proof 3 16 pts You are traveling by renting cars from car rental locations of cities There are n cities along the way Also a company named Trojan Rental dominates the car rental market and therefore there is only one car rental location in each city Before starting your journey you are given for each 1 i j n the fee fi j for renting a car from city i to city j which is arbitrary For example it is possible that f2 3 8 and f2 5 6 Also city j charges tj in taxes on the fee fi j collected in city j when the car is dropped off You begin at city 1 and must end at city n Your goal is to minimize the rental cost Give the most efficient algorithm you can for this problem Be sure to prove that your algorithm yields an optimal solution and analyze the time complexity a Define in plain English subproblems to be solved 3 pts The sub problem is to calculate the minimum rental cost with taxes from a city i to n where 1 i n b Write the recurrence relation for subproblems 5 pts Solution 0 min 89 38 A B DE FD 0 3 4 Points given for correct recurrence relations base condition 1 rest 4 c Write pseudo code to solve the above problem using the recurrence relation in part b 6 pts Initialization and returning correct value 2 1 Pseudocode implemented correctly from correct recurrence relation 3 d Compute the runtime of the algorithm in terms of n 2 pts Solution 2 points for time complexity of n 2 Since the question asked for the most efficient solution 2D array implementation which is not optimal has been given partial credits even if they yield a correct result 4 16 pts Suppose you have 4 production plants for making cars Each works a little differently in terms of labor needed materials and pollution produced per car Plant 1 Plant 2 Plant 3 Plant 4 Labor 2 3 4 5 Materials 3 4 5 6 Pollution 15 10 9 7 Suppose we need to produce at least 400 cars at plant 3 according to a labor agreement We have 3300 hours of labor and 4000 units of material available We are allowed to produce 12000 units of pollution and we want to maximize the number of cars produced Formulate a linear programming problem using minimal number of variables to solve the above task of maximizing the number of cars You need to provide a Clear definition of all variables in the LP formulation 3 pts b Objective function and constraints 13 pts Solution We need four variables to formulate the …