CS570 Analysis of Algorithms Fall 2006 Exam 1 Name Student ID Problem 1 Problem 2 Problem 3 Problem 4 Problem 5 Problem 6 Problem 7 Maximum 20 10 10 10 10 20 20 Note The exam is closed book closed notes Received 1 20 pts Mark the following statements as TRUE or FALSE No need to provide any justification TRUE FALSE True By definition it is true If T n is both O f n and f n then T n is f n TRUE FALSE True 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 False Counter example Fibonacci Heap Complexity of the Decrease Key operation is always O lgn for a priority queue TRUE FALSE True See the solution of HW4 For a graph with distinct edge weights there is a unique MST TRUE FALSE True yes and store all the possible solution in a table Dynamic programming considers all the possible solutions TRUE FALSE False The graph a b c d a with three edges are 1 and the one left is 4 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 True 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 False Counter example Shortest Path in a Graph Problems solved using dynamic programming cannot be solved thru greedy algorithms TRUE FALSE False union Find data structure is for Kruskal s algorithm it is not for the reverse delete Check the textbook for more details The union Find data structure can be used for an efficient implementation of the reverse delete algorithm to find an MST TRUE FALSE False Prim algorithm Vs Kruskal algorithm return can be different 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 n n n c 2n n2 3 2 B 3 n 2 n k n 2log n O Yes Yes No Yes Yes Yes Yes Yes No 3 10 pts a What is the minimum and maximum numbers of elements in a heap of height h The minimum is 2 n 1 The maximum number is 2 n 1 b What is the number of leaves in a heap of size n The smallest integer that no less than n 2 Or When n is even the number of leave is n 2 When n is odd the number of leaver is n 1 2 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 Answer No The sequence in heapify is 23 7 14 17 13 10 1 5 6 12 23 17 14 7 13 10 1 5 6 12 d Where in a max heap might the smallest element reside assuming that all elements are distinct The smallest element might reside in any leaves Grading policy 2 points for a 2 points for b 3 points for c 3 points for d 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 False Consider the graph A B C D A with weight 1 2 3 4 Grading policy Any one says that the statement is true and try to prove it of course with wrong proof may get partial credit up to 3 marks Any one says it is false without correct disproof counter example may get partial credit up to 6 marks In Question 5 any one says it is false and give a counter example that has one or more nodes in both G1 and G2 may get partial credit up to 6 marks Because that is a mistake nodes in G1 can not exist in G2 and vice versa Any one says it is false and give correct disprove counter example get 10 out of 10 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 Solution False Counter example Consider a graph G composed of 4 nodes A B C D with edge w A B 1 w B C 1 w B D 1 w C D 2 Let V1 A B with edge AB V2 C D with edge CD Then the weight of M1 U M2 U is 4 while the weight of the MST of G is 3 Grading policy Any one says that the statement is true and try to prove it of course with wrong proof may get partial credit up to 3 marks Any one says it is false without correct disproof counter example may get partial credit up to 6 marks In Question 5 any one says it is false and give a counter example that has one or more nodes in both G1 and G2 may get partial credit up to 6 marks Because that is a mistake nodes in G1 can not exist in G2 and vice versa Any one says it is false and give correct disprove counter example get 10 out of 10 6 20 pts There are n workers in the factory with heights of p1 p2 pn and n workingclothes with height sizes of s1 s2 sn The problem is to find best matching strategy such that we minimize the following average differences 1 pi s i n Present an algorithm to solve this problem along with its proof of correctness Solution Sort the height of workers in increasing order p1 p2 pn Sort the height size of clothes in increasing order s1 s2 sn Match hi with si is the best matching strategy such that we minimize the following average differences 1 pi s i n The algorithm is correct for the problem of minimizing the average difference between the heights of workers and their clothes The proof is by contradiction Assume the people and clothes are numbered in increasing order by height …