CS570 Analysis of Algorithms Fall 2006 Exam 1 Name: _____________________ Student ID: _________________ Maximum Received Problem 1 20 Problem 2 10 Problem 3 10 Problem 4 10 Problem 5 10 Problem 6 20 Problem 7 20 Note: The exam is closed book closed notes.1) 20 pts Mark the following statements as TRUE or FALSE. No need to provide any justification. [ TRUE/FALSE ] If T(n) is both O(f(n)) and Ω(f(n)), then T(n) is Ө(f(n)) . [ TRUE/FALSE ] For a graph G and a node v in that graph, the DFS and BFS trees of G rooted at v always contain the same number of edges [ TRUE/FALSE ] Complexity of the “Decrease_Key” operation is always O(lgn) for a priority queue. [ TRUE/FALSE ] For a graph with distinct edge weights there is a unique MST. [ TRUE/FALSE ] Dynamic programming considers all the possible solutions. [ TRUE/FALSE ] Consider an undirected graph G=(V, E) and a shortest path P from s to t in G. Suppose we add one 1 to the cost of each edge in G. P will still remain as a shortest path from s to t. [ TRUE/FALSE ] Consider an undirected graph G=(V, E) and its minimum spanning tree T. Suppose we add one 1 to the cost of each edge in G. T will still remain as an MST. [ TRUE/FALSE ] Problems solved using dynamic programming cannot be solved thru greedy algorithms. [ TRUE/FALSE ] The union-Find data structure can be used for an efficient implementation of the reverse delete algorithm to find an MST. [ TRUE/FALSE ] While there are different algorithms to find a minimum spanning tree of undirected connected weighted graph G, all of these algorithms produce the same result for a given G.2) 10 pts Indicate for each pair of expressions (A,B) in the table below, whether A is O, Ω, or Ө of B. Assume that k and c are positive constants. You can mark each box with Y (yes) and N (no). A B O Ω Ө n3 + n2 + n + c n3 2n 2(n+k) n2 n . 2log(n)3) 10 pts a- What is the minimum and maximum numbers of elements in a heap of height h? b- What is the number of leaves in a heap of size n? c- Is the sequence < 23, 7, 14, 6, 13, 10, 1, 5, 17, 12 > a max-heap? If not, show how to heapify the sequence. d- Where in a max-heap might the smallest element reside, assuming that all elements are distinct.4) 10 pts Prove or disprove the following: The shortest path between any two nodes in the minimum spanning tree T = (V, E') of connected weighted undirected graph G = (V,E) is a shortest path between the same two nodes in G. Assume the weights of all edges in G are unique and larger than zero.5) 10 pts Suppose that you divided a graph G = (V,E) into two sub graphs G1 = (V1,E1) and G2 = (V2, E2). And, we can find M1 which is a MST of G1 and M2 which is MST of G2. Then, M1 U M2 U {minimum weight edge among those connecting two graph G1 and G2} always gives MST of G. Prove it or disprove it.6) 20 pts There are n workers in the factory with heights of h1, h2, …, hn , and n working-clothes with height sizes of s1, s2, …, sn. The problem is to find best matching strategy such that we minimize the following average differences. ∑−iishn1 Present an efficient algorithm to solve this problem along with its proof of correctness.7) 20 pts Given an unlimited supply of coins of denominations x1, x2, …, xn, we wish to make change for a value v, that is, we wish to find a set of coins whose total value is v. This might not be possible: for example, if the denominations are 5 and 10 then we can make change for 15 but not for 12. Give an O(nv) algorithm to determine if it is possible to make change for v using coins of denominations x1, x2, …, xn.Additional SpaceAdditional