CS570 Analysis of Algorithms Spring 2009 Final Exam A Name Student ID 2 00 5 00 Friday Section Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total 2 hr exam Close book and notes 5 00 8 00 Friday Section DEN Maximum 20 20 15 10 20 15 100 Received 1 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 subsequence 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 before b 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 …