CS570 Fall 2017: Analysis of Algorithms Exam III Points Problem 1 20 Problem 2 15 Problem 3 10 Problem 4 15 Problem 5 15 Problem 6 10 Problem 7 15 Total 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) Solution: 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]). 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