CS570 Analysis of Algorithms Summer 2017 Exam III Name Student ID Email Address Check if DEN Student Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Total 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 Maximum 20 15 15 15 10 15 10 100 Received 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 1 20 pts Mark the following statements as TRUE or FALSE No need to provide any justification TRUE FALSE Every problem in P can be reduced to 3 SAT in polynomial time TRUE FALSE If there is a polynomial time algorithm for 2 SAT then every problem in NP has a polynomial time algorithm TRUE FALSE If all edge weights are 1 2 or 3 the shortest path problem can be solved in linear time TRUE FALSE Suppose G is a graph with n vertices and n1 5 edges represented in adjacency list representation Then depth first search in G runs in O n1 5 time TRUE FALSE The weight of a minimum spanning tree in a positively weighted undirected graph is always less than the total weight of a minimum spanning path Hamiltonian Path with lowest weight of the graph TRUE FALSE If A is in NP and B is NP complete and A p B then A is NP complete TRUE FALSE Given a problem B if there exists an NP complete problem that can be reduced to B in polynomial time then B is NP complete TRUE FALSE If an undirected connected graph has the property that between any two nodes u and v there is exactly one path between u and v then that graph is a tree TRUE FALSE Suppose that a divide and conquer algorithm reduces an instance of size n to four instances of size n 5 and spends n time in the divide and combine steps The algorithm runs in n time TRUE FALSE An integer N is given in binary An algorithm that runs in time O sqrt N to find the largest prime factor of N is considered to be a polynomial time algorithm Ex Prime factorization of 84 2 x 2 x 3 x 7 so the largest prime factor of 84 is 7 2 15 pts We are given a set of non equality constraints of the form xi xj over a set of Boolean variables x1 x2 xn We wish to determine if there is an assignment of Boolean values 0 1 to the variables that satisfies all the constraints and compute such a satisfying assignment if there is one Give an algorithm that solves this problem in time O n m where n is the number of variables and m the number of constraints Justify the correctness and time complexity of your algorithm This can be reduced to the problem of testing whether a graph is bipartite Given a set C of non equalities xi xj on a set of Boolean variables x1 x2 xn we can construct a graph G which has a node for each variable and has an edge xi xj for each constraint xi xj We claim that the graph G is bipartite if and only if the set C of constraints has a satisfying assignment First suppose that the graph G is bipartite i e there is a partition of the set N of nodes Into two sets subsets N1 N2 N1 N2 N1 N2 N so that every edge connects a node of N1 with a node of N2 Then the assignment that gives value 1 to all variables corresponding to nodes in N1 and value 0 to all variables corresponding to nodes in N2 satisfies all the constraints Since every edge connects a node of N1 with a node of N2 this assignment satisfies all the constraints Conversely if there is an assignment that satisfies all the constraints then we can form a bipartition of the node set by letting N1 be the set of all the nodes corresponding to variables that are assigned 1 and N2 the set of nodes corresponding to variables that are assigned 0 Since the assignment satisfies all the constraints in every constraint xi xj one variable is assigned 1 and the other 0 hence every edge connects a node of N1 with a node of N2 The graph G has n nodes and m edges We know that we can test in O n m time whether a graph is bipartite using DFS or BFS Grading Rubrics 1 correctly define the graph and claim that problem can be reduced into checking whether G is bipartite 5 pts 2 Justify the correctness of the algorithm 7 pts 3 Justify the running time of the algorithm 3 pts 3 15 pts Consider the following problem Given a flow network G with source s and sink t and a unique s t min cut find k edges that when deleted reduce the maximum s t flow in the graph by as much as possible Prove or disprove the following solution Find the s t min cut in G Sort edges on the min cut in decreasing order of weight Delete the first k highest capacity edges from the ordered list A 2 2 3 3 B D 2 10 5 10 T 2 10 C 2 2 Saying statement is false without a correct counterexample 5 points Proving the statement is True because all edges on the min cut are saturated and hence removing each edge from the cut will have a reduction in max flow equal to the capacity of that edge 5 points This is False Counter example 5 10 S Grading 4 15 pts Given a list of non negative numbers and a target integer k Design a dynamic programming algorithm to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k that is sums up to n k where n is also an integer Example Input 23 2 4 6 7 k 6 Output True Explanation Because 2 4 is a continuous subarray of size 2 and sums up to 6 Example Input 23 2 6 4 7 k 6 Output True Explanation Because 23 2 6 4 7 is a continuous subarray of size 5 and sums up to 42 First if k 0 we check whether these are two continuous zeros in the list If so return True Otherwise return False Then for k 0 we use the following algorithm Assume dp i j representing the sum of sub array from i to j in array If there is a pair of i j satisfies dp i j k 0 the algorithm returns true …