**Unformatted text preview:**

CS570 Fall 2017 Analysis of Algorithms Exam III Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Total Points 20 15 10 15 15 10 15 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 To prove that a problem X is NP complete it is sufficient to prove that 3SAT is polynomial time reducible to X TRUE FALSE Finding the minimum element in a binary max heap of n elements takes O log n time TRUE FALSE We are told that in the worst case algorithm A runs in O n log n and algorithm B runs in O n2 Based on these facts there must be some N that when n N algorithm A runs faster than algorithm B TRUE FALSE The following recurrence equation T n 3T n 3 0 1 n has the solution T n n log n2 TRUE FALSE Every problem in NP can be solved in exponential time by a deterministic Turing machine TRUE FALSE In Kruskal s MST algorithm if we choose edges in decreasing instead of increasing order of cost we will end up with a spanning tree of maximum total cost TRUE FALSE If all edges in a graph have capacity 1 then Ford Fulkerson runs in linear time TRUE FALSE If problem X can be solved using dynamic programming then X belongs to P TRUE FALSE If Vertex Cover P then SAT P TRUE FALSE Assuming P NP and X is a problem belonging to class NP There is no polynomial time algorithm for X 2 15 pts We have a directed graph G V E where each edge u v has a length l u v that is a positive integer Let n denote the number of vertices in G Suppose we have previously computed a n x n matrix d where for each pair of vertices u v V d u v stores the length of the shortest path from u to v in G The d matrix is provided for you Now we add a single edge a b to get the graph G V E where E E a b Let l a b denote the length of the new edge Your job is to compute a new distance matrix d which should be filled in so that d u v holds the length of the shortest path from u to v in G for each u v V a Write a concise and efficient algorithm to fill in the d matrix You should not need more than about 3 lines of pseudocode 12 pts For each pair of vertices u v V Set d u v min d u v d u a l a b d b v Solution Grading Considering all pairs of vertices 6 points Comparing the current shortest path with the length of the path going through edge a b and choosing the smaller path 6 points b What is the asymptotic worst case running time of your algorithm Express your answer in O notation as a function of n and E 3 pts Solution O n2 Grading Correct Answer 3 points Incorrect answer 0 points 3 10 pts Recall the 0 1 knapsack problem Input n items where item i has profit pi and weight wi and knapsack size is W Output A subset of the items that maximizes profit such that the total weight of the set W You may also assume that all pi 0 and 0 wi W We have created the following greedy approximation algorithm for 0 1 knapsack Sort items according to decreasing pi wi breaking ties arbitrarily While we can add more items to the knapsack pick items in this order Show that this approximation algorithm has no nonzero constant approximation ratio In other words if the value of the optimal solution is P prove that there is no constant 1 0 where we can guarantee our greedy algorithm to achieve an approximate solution with total profit P Solution The definition of a constant factor is that P P Giving an example were P P and saying 1 or giving two different examples and showing the ratio P P is not always the same does not mean there does not exist a constant approximation ratio The correct way to show this is not possible is to provide an example with multiple at least two items and their respective weights and profits Then you need to show that the greedy algorithm and the optimal algorithm will generate two different solutions profits and need to show in your example the ratio P P can be unboundedly small One example can be as follows Consider an item with size 1 and profit 2 and another with size W and profit W Our greedy algorithm above will take the first item while the optimal solution is taking the second item so this algorithm has approximation ratio 2 W which can go arbitrarily close to zero Grading A correct solution has 10 points Common Mistakes Giving two different examples and showing that the ratio of greedy to optimal is different doesn t mean there is no constant approximation ratio The existence of a constant approximation factor will not imply P NP Greedy is not optimal 4 15 pts The graph five coloring problem is stated as follows Determine if the vertices of G can be colored using 5 colors such that no two adjacent vertices share the same color Prove that the five coloring problem is NP complete Hint You can assume that graph 3 coloring is NP complete Solution Show that 5 coloring is in NP Certificate a color solution for the network i e each node has a color Certifier i Check for each edge u v the color of node u is different from the color of node v ii Check at most 5 colors are used This process takes O m n time Show that 5 coloring is NP hard prove that 3 coloring p 5 coloring Graph construction Given an arbitrary graph G Construct G by adding 2 new nodes u and v to G Connect u and v to all nodes that existed in G and to each other G can be …

View Full Document