**Unformatted text preview:**

CS570 Analysis of Algorithms Spring 2005 Final Exam Name Student ID 1 10 pts a The NP complete problem X has a polynomial time 2 approximation algorithm A X can be reduced to problem Y Can A be used to find a 2 approximation to Y Answer Yes No or Sometimes Then explain your answer b The NP complete problem X has a polynomial time 2 approximation algorithm A Problem Y can be reduced to X Can A be used to find a 2 approximation to Y Answer Yes No or Sometimes Then explain your answer 2 20 pts You are given an m by n matrix of real numbers such that the sum of the values in each row and each column are exact integer numbers Design an algorithm that rounds all the entries in the matrix up or down to the closest integer value without affecting the row or column sums An example of such a transformation is shown below Analyze the complexity of your solution Example Input is the 2x3 matrix shown in the shaded area Men Women Men Women Output is the 2x3 matrix shown in the shaded area CS570 16 6 10 4 27 CS570 16 11 27 CS571 18 1 17 9 36 CS571 19 17 36 CS585 21 3 15 7 37 CS585 21 16 37 Total 56 44 100 Total 56 44 100 Hint Show how this problem can be reduced to one of the variants of the network flow problem we have studied 3 20 pts Assume that you have an n by n checkerboard You must move a checker from the bottom left corner square of the board to the top right corner square In each step you may either 1 move the checker up one square or 2 move the checker diagonally one square up and to the right or 3 move the checker right one square If you move a checker from square x to square y you get p x y dollars You are told all of the p x y a priori The p x y may be negative zero or positive You want to get as much money as possible Give an efficient algorithm for this problem Analyze the complexity of your algorithm 4 10 pts Prove or disprove the following Given a graph G V E with edge costs Ce we can always swap any 2 edge costs without affecting the cost of the Min Spanning Tree of G 5 10 pts a We have seen a polynomial time solution to the integer network flow problem using the Ford Fulkerson algorithm Can we also apply linear programming to solve this problem in polynomial time Explain your answer b Can you apply linear programming to solve the network flow problem when capacities are allowed to take on real numbers If no explain why not If yes briefly explain how the linear programming problem can be formulated 6 20 pts The input to the Fixed Hamiltonian path problem is an undirected graph G and two vertices x and y in G The problem is to determine if there is a simple path between x and y in G that spans all the vertices in G A path is simple if it doesn t include any vertex more than once Show that the Fixed Hamiltonian path problem is NP complete Problem continued Problem continued Problem continued Problem continued

View Full Document