Unformatted text preview:

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 …

View Full Document

USC CSCI 570 - 2018 Spring Solution

Download 2018 Spring Solution
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...

Join to view 2018 Spring Solution and access 3M+ class-specific study document.

We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view 2018 Spring Solution and access 3M+ class-specific study document.


By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?