CS570 Spring 2018: Analysis of Algorithms Exam III Points Points Problem 1 20 Problem 5 15 Problem 2 15 Problem 6 10 Problem 3 15 Problem 7 10 Problem 4 15 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𝑚"-#=𝑛 𝑛 − 12𝑚 Rubrics: Describe choosing 2 keys from n keys: 10 pts. Describe 𝑃 ℎ 𝑘"= ℎ 𝑘#"-#: 10 pts. 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: Labor Materials Pollution Plant 1 2 3 15 Plant 2 3 4 10 Plant 3 4 5 9 Plant 4 5 6 7 The goal is to maximize the number of cars produced under the following constrains: • 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. 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 -