CS570 Analysis of Algorithms Spring 2008 Exam II Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 15 Problem 3 15 Problem 4 15 Problem 5 20 Problem 6 15 Total 100 Note: The exam is closed book closed notes.1) 20 pts Mark the following statements as TRUE, FALSE. No need to provide any justification. False [ TRUE/FALSE ] If all capacities in a network flow are rational numbers, then the maximum flow will be a rational number, if exist. False [ TRUE/FALSE ] The Ford-Fulkerson algorithm is based on the greedy approach. True [ TRUE/FALSE ] The main difference between divide and conquer and dynamic programming is that divide and conquer solves problems in a top-down manner whereas dynamic-programming does this bottom-up. True [ TRUE/FALSE ] The Ford-Fulkerson algorithm has a polynomial time complexity with respect to the input size. True [ TRUE/FALSE ] Given the Recurrence, T(n) = T(n/2 ) + θ(1), the running time would be O(log(n)) True [ TRUE/FALSE ] If all edge capacities of a flow network are increased by k, then the maximum flow will be increased by at least k. True [ TRUE/FALSE ] A divide and conquer algorithm acting on an input size of n can have a lower bound less than Ω(n log n) . True [ TRUE/FALSE ] One can actually prove the correctness of the Master Theorem. True [ TRUE/FALSE ] In the Ford Fulkerson algorithm, choice of augmenting paths can affect the number of iterations. False [ TRUE/FALSE ] In the Ford Fulkerson algorithm, choice of augmenting paths can affect the min cut.2) 15 pts Present a divide-and-conquer algorithm that determines the minimum difference between any two elements of a sorted array of real numbers. Let us assume the array is A[1…n] LargestDifference(n) { If n<=1, return Infinity; Else, return min(LargestDifference(n-1), abs(A[n]-A[n-1])); }3) 15 pts You are given the following directed network with source O and sink T. a) Find a maximum flow from O to T in the network. O ABCDT653123707O A B CDT 763123828b) Find a minimum cut. What is its capacity? The Capacity is 9. O ABCDT7631238284) 15 pts Solve the following recurrences a) T (n) = 2T (n/2)+ n log n By the master theorem, T(n) = nlog2n b) T (n) = 2T (n/2) + log nc) T(n) = 2T(n-1) - T(n-2) for n ≥ 2; T(0) = 3; T(1) = 3 T(n) = 2T(n-1) – T(n-2) = 2(2T(n-2) – T(n-3)) –T(n-2) = 3T(n-2) – 2T(n-3) =4T(n-3)-3T(n-4) = nT(1) – (n-1)T(0) = 35) 20 pts You are given a flow network with integer capacity edges. It consists of a directed graph G = (V, E), a source s and a destination t, both belong to V. You are also given a parameter k. The goal is to delete k edges so as to reduce the maximum flow in G as much as possible. Give a efficient algorithm to find the edges to be deleted. Prove the correctness of your algorithm and show the running time.6) 15 pts Six men and six women are at a dance. The goal of the matchmaker is to match each woman with a man in a way that maximizes the number of people who are matched with compatible mates. The table below describes the compatibility of the dancers. Note: C indicates compatibility. a) Determine the maximum number of compatible pairs by reducing the problem to a max flow problem. Ann Cindy Erin Liz Mary Nancy Bob C C - - - - Dave - - C - - - John - C C C - - Kevin - - C - C - Ron - - - C - C Sam - - - - C - B D J K R S ACELMNu vb) Find a minimum cut for the network of part (a). c) Give the list of pairs in the maximum pairs set. (B, A), (J, C), (K, E), (R, N), (S, M) B D J K R S ACELMNu