CS 570Analysis of AlgorithmsSpring 2008Final Exam SolutionsKenny Daniel ([email protected])Question 1[ FALSE ] In a flow network whose edges have capacity 1, the maximum flow always corresponds to themaximum degree of a vertex in the network.[ FALSE ] If all edge capacities of a flow network are unique, then the min cut is also unique.[ TRUE ] A minimum weight edge in a graph G must be in one minimum spanning tree of G.[ TRUE ] When the size of the input grows, any polynomial algorithm will eventually become more efficientthan any exponential one.[ FALSE ] NP is the class of problems that are not solvable in polynomial time.[ FALSE ] If a problem is not solvable in polynomial time, it is in the NP-Complete class.[ TRUE ] Linear programming can be solved in polynomial time.[ FALSE ] 102 log 4n+3+ 92 log 3n+21is O(n).[ FALSE ] f(n) = O(g(n)) implies g(n) = O(f(n)).[ FALSE ] If X can be reduced in polynomial time to Y and Z can be reduced in polynomial time to Y ,then X can be reduced in polynomial time to Z.Question 2Suppose you are given a number x and an array A with n entries, each being a distinct number. Also it isknown that the sequence of values A[1], A[2], . . . , A[n] is unimodal. In other words for some unknown indexp between 1 and n, we have A[1] < . . . < A[p − 1] < A[p] > A[p + 1] > . . . > A[n]. (Note that A[p] holds thepeak value in the array).1Give a algorithm with running time O(log n) to determine if x belongs to A, if yes the algorithm shouldreturn the index j such that A[j] = x. You should justify both the correctness of your algorithm and therunning time.Solution: Since the array is unimodal, if we know where the maximum value is in the array, we can split thearray in two and perform a binary search on each half (since each half is sorted in increasing and decreasingorder respectively). So the real problem is finding the maximum value in time O(log n).To find the maximum value, we use a divide and conquer algorithm which cuts the size of the search in 2/3each time. We compare the 1/3 median and 2/3 median, and discard the bottom 1/3 or top 1/3 dependingwhich is larger (convince yourself why this works!).int find max(start, end) {length := end - start;m1 := start + length / 3;m2 := start + length * 2 / 3;if(length = 0)return start;if(A[m1] < A[m2])return find max(m1, end);elsereturn find max(start, m2);}Question 3You are given two sequences a[1], ..., a[m] and b[1], ..., b[n]. You need to find their longest common subse-quence; that is, find a subsequence a[i1], ..., a[ik] and b[j1], ..., b[jk], such that a[i1] = b[j1], . . . , a[ik] = b[jk]with k as large as possible. You need to show the running time of your algorithm.Solution: First note that this problem is actually to find the longest common substring (not subsequence,since they must be contiguous). That being said, we solving this problem using dynamic programming. Werecursively build up the solution from the following subproblem: Let LCSuffix(i, j) be the length of the longestcommon suffix of the strings a[1], ..., a[i] and b[1], ..., b[j].LCSuffix(i, j) =(LCSuffix(i − 1, j − 1) + 1 if a[i] = b[j]0 otherwiseConstructing the above table for 1 ≤ i ≤ m and 1 ≤ j ≤ n takes time O(mn). Then we find the longestcommon substring by finding the maximal value in the table:LCSubstring = max1≤i≤m,1≤j≤nLCSuffix(i, j)2Question 4In Linear Programming, variables are allowed to be real numbers. Consider that you are restricting vari-ables to be only integers, keeping everything else the same. This is called Integer Programming. IntegerProgramming is nothing but a Linear Programming with the added constraint that variables be integers.Prove that integer programming is NP-HardSolution: Integer Programming is in NP (since it is easy to check solutions), and is in NP-hard by reductionfrom Independent Set. Suppose we are given an instance of the Independent Set problem, consisting of agraph G such that we want to find the largest set S of vertices such that no two vertices share an edge.We can express this as an Integer Program as follows: Each vertex v is represented by a variable xvwhichis either 0 or 1. For each edge (u, v), we add one constraint such that xu+ xv≤ 1. Then we maximizethe sum: maxPv ∈Sxv. It can then be shown that a solution to this Integer Program gives a solution to theIndependent Set problem, and so Integer Programming must be NP-hard.Question 5A carpenter makes tables and bookshelves, and he wants to determine how many tables and bookshelves heshould make each week for a maximum profit. The carpenter knows that a net profit for each table is $25and a net profit for each bookshelf is $30. The wooden material available each week is 690 units, its workinghours are 120 hours per week. The estimated wood and working hours for making a table are 20 units and5 hours respectively, while for making a bookshelf are 30 units and 4 hours. Formulate the problem usingany technique we have covered in class. You do not need to solve it numerically.Solution: This problem can be solved using Integer Programming. We define two variables t for the numberof tables made, and b for the number of bookshelves. The maximum wood available is 690, so we have theconstraint:20 · t + 30 · b ≤ 690The maximum working hours is 120 hours, so we have the constraint:5 · t + 4 · b ≤ 120Then the carpenter wishes to maximize profit:max 25 · t + 30 · bQuestion 6A variation of the satisfiability problem is the MIN 2-SAT problem. The goal in the MIN 2-SAT problemis to find a truth assignment that minimizes the number of satisfied clauses. Give the best approximationalgorithm that you can find for the