ABAAAn1nnnnn2CS570 Analysis of Algorithms Summer 2007 Exam 1 Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 10 Problem 3 10 Problem 4 15 Problem 5 20 Problem 6 15 Problem 7 10 Total 1001) 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 B A=O(B) A=Ω(B) A=Θ(B) n 1 n2n lgn n+n2n3 n 200n + n/2 n.5lg n 1010n 2n 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 SpaceAdditional