CS570 Analysis of Algorithms Summer 2017 Exam III Name: _____________________ Student ID: _________________ Email Address:________________ _____Check if DEN Student Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Problem 4 15 Problem 5 10 Problem 6 15 Problem 7 10 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.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 72) 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*runnin g*tim e *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 This is False. Counter example: Grading: • 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) 2/10 S A C B D T 5/10 2/10 2/2 2/2 5/10 3/34) 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. Otherwise, it returns false. Initialize all elements in the dp array to