CS570 Analysis of Algorithms Spring 2008 Exam II Name Student ID Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Total Maximum 20 15 15 15 20 15 100 Note The exam is closed book closed notes Received 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 dynamicprogramming 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 C 2 3 1 7 O 6 T 3 2 B 8 8 D a Find a maximum flow from O to T in the network A C 2 3 1 6 O 5 T 3 0 B 7 7 D b Find a minimum cut What is its capacity A C 2 3 1 7 O 6 T 3 2 B The Capacity is 9 8 8 D 4 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 n c 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 3 5 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 Bob Dave John Kevin Ron Sam Ann Cindy Erin Liz Mary Nancy C C C C C C C C C C C Note C indicates compatibility a Determine the maximum number of compatible pairs by reducing the problem to a max flow problem B A D C u v J K R S E L M N b Find a minimum cut for the network of part a B A D C u v J K R S E L M N c Give the list of pairs in the maximum pairs set B A J C K E R N S M