CS570 Spring 2018 Analysis of Algorithms Exam III Problem 1 Problem 2 Problem 3 Problem 4 Points 20 15 15 15 Problem 5 Problem 6 Problem 7 Points 15 10 10 Total 100 Points 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 To prove that a problem X is NP hard it is sufficient to prove that SAT is polynomial time reducible to X FALSE If a problem Y is polynomial time reducible to X then a problem X is polynomial time reducible to Y TRUE Every problem in NP can be solved in polynomial time by a nondeterministic Turing machine TRUE Suppose that a divide and conquer algorithm reduces an instance of size n into 4 instances of size n 5 and spends n time in the conquer steps The algorithm runs in n time FALSE A linear program with all integer coefficients and constants must have an integer optimum solution FALSE Let M be a spanning tree of a weighted graph G V E The path in M between any two vertices must be a shortest path in G TRUE A linear program can have an infinite number of optimal solutions TRUE Suppose that a Las Vegas algorithm has expected running time n on inputs of size n Then there may still be an input on which it runs in time n2 FALSE The total amortized cost of a sequence of n operations gives a lower bound on the total actual cost of the sequence FALSE The maximum flow problem can be efficiently solved by dynamic programming 2 15 pts Consider a uniform hash function h that evenly distributes n integer keys 0 1 2 n 1 among m buckets where m n Several keys may be mapped into the same bucket The uniform distribution formally means that Pr h x h y 1 m for any x y 0 1 2 n 1 What is the expected number of total collisions Namely how many distinct keys x and y do we have such that h x h y Solution Let the indicator variable be 1 if and 0 otherwise for all Then let be a random variable representing the total number of collisions It can be calculated as the sum of all the Now we take the expectation and use linearity of expectation to get 1 1 2 10 pts Rubrics Describe choosing 2 keys from n keys 10 pts Describe Common mistaks 1 n m The mistake is that it thinks the expected number of collisions for each key is 1 m 7pts 2 2n m Similar to 1 7pts 3 n 1 m Similar to 1 7pts 4 m 1 2 Basically no clue 3 pts 5 n n 1 m Duplicates 13 pts 6 n 2 m duplicated 13 pts 7 1 1 1 m n 1 n wrong approach 5 pts 8 n m wrong approach 3pts 9 9 9 15 pts 10 n n 1 2 The mistake is that it does not consider collision probability 10 pts 11 N n 1 2m minor mistake 13 pts 3 15 pts There are 4 production plants for making cars Each plant 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 There are at most 3300 hours of labor There are at most 4000 units of material available The level of pollution should not exceed 12000 units Plant 3 must produce at least 400 cars The goal is to maximize the number of cars produced under the following constrains Formulate a linear programming problem using minimal number of variables to solve the above task of maximizing the number of cars Solution We need four variables to formulate the LP problem 9 A B C where denotes the number of cars at plant i Maximize 9 A B C s t 0 for all B 400 2 9 3 A 4 B 5 C 3300 3 9 4 A 5 B 6 C 4000 15 9 10 A 9 B 7 C 12000 Rubric Identifying 4 variables 2 pts Correct objective function 3 pts Each condition 2 pts 4 15 pts Given an undirected connected graph G V E in which a certain number of tokens t v 1 placed on each vertex v You will now play the following game You pick a vertex u that contains at least two tokens remove two tokens from u and add one token to any one of adjacent vertices The objective of the game is to perform a sequence of moves such that you are left with exactly one token in the whole graph You are not allowed to pick a vertex with 0 or 1 token Prove that the problem of finding such a sequence of moves is NP complete by reduction from Hamiltonian Path Solution Construction given a HP in G we construct G as follows Traverse a HP in G and placed 2 tokens on the starting vertex and one token on each other vertex in the path Claim G has a HP iff G has a winning sequence by construction before the last move we will end up with a single vertex having two tokens on it Making the last move we will have exactly one token on the board since there is only one vertex with 2 tokens we will start right there playing the game Each next move is forced When we finish the game we get a sequence moves which represents a HP Rubrics Didn t prove it is in NP 5 Didn t prove it is NP hard 10 Assigned two tokens on one random vertex instead of the starting vertex of Hamiltonian path 2 Since it is a reduction from Hamiltonian path not from Hamiltonian cycle 2 tokens should be assigned on the starting vertex Assigned wrong number of tokens on one vertex 3 Assigned wrong number of tokens on two vertices 6 Assigned wrong number of tokens on three or more vertices considered as not a valid reduction from Hamiltonian path 7 Not a valid reduction from Hamiltonian path 7 5 15 pts In …