CS570 Analysis of Algorithms Spring 2009 Final Exam A Name: _____________________ Student ID: _________________ ____2:00-5:00 Friday Section ____5:00-8:00 Friday Section ___DEN Maximum Received Problem 1 20 Problem 2 20 Problem 3 15 Problem 4 10 Problem 5 20 Problem 6 15 Total 100 2 hr exam Close book and notes1) 20 pts Mark the following statements as TRUE, FALSE, (or UNKNOWN if given as an option). No need to provide any justification. [ TRUE/FALSE ] F To prove a problem is NP hard, you have to give a polynomial time certificate and certifier. [ TRUE/FALSE/UNKNOWN ] F If there is a polynomial time algorithm for some problem in NP, then all problems in NP can be solved in polynomial time. [ TRUE/FALSE ] T The lower bound for general sorting algorithms (algorithms that work on any data type) is Ω(n log n). [ TRUE/FALSE ] T It can be decided in polynomial time whether a graph is 2-colorable, i.e., whether there is a mapping c : V → {0, 1} such that for all (u, v) ∈ E, c(u) ≠c(v). [ TRUE/FALSE ] T If you are given a maximum s − t flow in a graph then you can find a minimum s − t cut in time O(m). [ TRUE/FALSE ] T Let A, B, and C be decision problems. If A ≤P B and B≤ P C, then A ≤ P C. [ TRUE/FALSE/UNKNOWN ] F All the problems in NP take longer time to solve than all the problems in P. [ TRUE/FALSE ] T Simplex algorithm for solving LP problems is based on the greedy approach rather than dynamic programming. [ TRUE/FALSE/UNKNOWN] UNKNOWN NP hard problems cannot be solved in polynomial time. [ TRUE/FALSE ] T The problem of finding the length of the shortest path between two nodes in a directed graph can be expressed as a linear program.2) 20 pts Given a sequence of n real numbers A(1) ... A(n), determine a contiguous sub-sequence A(i) ... A(j) for which the sum of elements in the subsequence is maximized. We will solve this using dynamic programming Let OPT(i) be the sum of the max sequence ending at “i” now, I have two options, either I continue the sequence from i-1 or I start a new sequence at “i” , which just contains “i” (and hence ends at “i”) and I just need to take the max of those two so OPT(I) = max(OPT(i-1),i) This is clearly linear time We don't even have to do dynamic programming, just start from the first element and traverse over the entire array keeping two pointers and a sum and that should work out too.3) 15 pts TRUE or FALSE? If you choose FALSE , give a counter example to briefly justify the choice; otherwise, prove that the claim is TRUE. a) Consider a flow network G = (V,E) with source s, sink t, and positive integral capacity Ce on every edge e ∈ E. Let (A,B) be a minimum s-t cut. If we add 1 to each edge capacity, then (A,B) remains a minimum s-t cut with respect to the new capacities. This is False. The following graph will do the trick vertices , A, B, C, D, E edges and capacities C(AB) = 1 C(AC)=1 C(BD)=1 C( CD) = 1 C(DE) =3 Now, the two min cuts are {A}, {B,C,D,E} or {A,B,C},{D,E} If we increase edge costs by one, the min cut is {A,B,C,D},{E} which was not the min cute beforeb) Consider a flow network G = (V,E) with source s, sink t, and positive integral capacity Ce on every edge e ∈ E. Let f be a maximum flow, then for each edge e = (s, u) out of s, we must have f(e) = Ce. This is Again false. Just imagine a network vertices , s, t, A, B edges and capacities C(sA) = 2 C(sB)=1 C(At)=1 C(Bt) = 1 In this case, in the max flow, the flow through edge sA will be 1 4) 10 pts Assume that I know that a minimization problem X is NP HARD. Now, I am trying to find an α approximation algorithm to it. After much searching, I have been able to create an algorithm, A. Now, I have proven the following. Let sol(A) be the solution of algorithm A sol(A) <= α LB(OPT) where LB(OPT) is a lower bound on the optimal answer to X. Do I have an α approximation algorithm here? Please prove or disprove. Now, Since LB(OPT) <= OPTαLB(OPT) <= αOPT Sol(A) <= αLB(OPT) <= αOPT Therefore Sol(A) <= αOPT and you have an alpha approximatoin 5) 20 pts Dominating Set problem: In an undirected graph G, a dominating set is a set X of vertices such that every vertex in G is either in X or connected to a vertex of X by an edge, or both. The Dominating Set problem is to input an undirected graph and a number k, and determine whether there is a dominating set with k vertices. Prove that the Dominating Set problem is NP-complete. (Hint: Reduce from Vertex Cover by constructing a new graph from G.)Proof: (1) Dominating Set is in NP because we can verify in polynomial time thay we can check that the size of the given set is k and that every vertex in G is either in the set or connected to an element of the set by an edge. (2) Reduce from Vertex Cover: Let (G, k) be an instance of the vertex cover problem. Construct a new graph G' by adding new vertices and edges to the graph G as follows: For each edge (v, w) of G, add a vertex vw and the edges (v, vw) and (w, vw) to G' . Furthermore, remove all vertices with no incident edges; such vertices would always have to go in a dominating set but are not needed in a vertex cover of G. Overall, this transformation can be implemented in O(|E| + |V|) time. Now we claim that G' has a dominating set D of size K if and only if G has a vertex cover C of size k. This is done by proving the "if" ( ) and the "only if" ( ) parts separately. ( ) Let D be a dominating set of size K in G' . There can be two cases: Either D contains only vertices from the original G or some new vertices from G' are also in D. In the first case all the new vertices (representing an edge) have an edge to a vertex in D. This means that D covers all edges and is a valid vertex cover set for G. However, if there are any new vertices in D, they need to be replaced by a vertex from G: A new vertex vw in D needs to be replaced by v or w. In either case the edge (w,v) will be covered by D. If v or w already is in D they need not be added. After all the new edges have been removed, D will be a valid vertex cover for G. This proves the "if" part. ( ) …