CS570 Analysis of Algorithms Summer 2007 Exam 1 Name Student ID Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Total Maximum 20 10 10 15 20 15 10 100 Received 1 20 pts Mark the following statements as TRUE or FALSE No need to provide any justification TRUE FALSE Given a connected graph G with at least two edges having the same cost there will definitely be two distinct minimum spanning trees TRUE FALSE You can use Dijikstra s shortest path algoritm in a graph with negative edge weights TRUE FALSE Prim s algorithm can be implemented in O m log n time TRUE FALSE In a dynamic programming problem the solution to a sub problem might change at certain steps and therefore has to be recomputed TRUE FALSE In the Gale Shapley algorithm the order in which the men propose to the women i e the order in which the algorithm might pick a man to propose to a woman might affect the final matching that is formed TRUE FALSE if f n Theta g n then g n Theta f n TRUE FALSE Given a graph G with unit edge costs we can use the BFS algorithm to calculate the shortest path between two nodes TRUE FALSE A Pseudo polynomial algorithm will always be inefficient no matter what the magnitude of the input TRUE FALSE The shortest path between two nodes that are both on the minimum spanning tree consists only of those edges that are in the minimum spanning tree TRUE FALSE A Breadth First Search Tree on graph G can be used to determine distances between all nodes in G 2 10 pts Fill in the following table Each box should have a yes or no indicating whether or not the condition at the top of the row is true The first row has already been answered for you Basically for each box you should ask yourself Is B and upper lower asymptotic bound on A A n n2 n n2 n n 5 10 n10 B 1 n lgn n3 200n n 2 lg n 2n A O B A B A B 3 10 pts What is the big O running time in terms of n of the following code fragment a for i 1 i n i i 2 Sum b int fact int n if n 1 return 1 else return n fact n 1 c int silly int n if n 0 return 0 else return 1 silly n 1 silly n 1 4 15 pts Suppose that you are given a strongly connected directed graph G V E with positive edge weights and let v0 V You want to find the shortest paths between all pairs of nodes however you are only interested in paths that go through the particular node v0 Present an efficient algorithm that solves this problem 5 20 pts Assume that you have a complete binary tree with values vi on each node Starting at the root you have the choice of picking up the value at a node If you pick up the value at a node x say vx you cannot pick up the values at any of the children of x Give a dynamic program to calculate which nodes to pick maximizing the sum of the values of the nodes picked 6 15 pts The object of the Coin Problem is to come up with the minimum number of coins to pay X cents a Consider the greedy approach to solving the coin problem for US coins where we start with the largest coin 25 coin and use it as many times as possible then use as many 10 coins as possible on the remainder then 5 then 1 Prove or disprove that this greedy algorithm always gives an optimal solution i e gives the minimum number of coins to pay X cents b Now suppose that 5 coins are not allowed only 1 10 and 25 Prove or disprove that the corresponding greedy approach 25 then 10 then 1 always gives an optimal solution 7 10 pts Given a connected graph G V E an edge e is called an isthmus if the removal of e from G disconnects G Prove that every spanning tree of G must contain all the isthmus edges Additional Space Additional Space