31. Which of the following algorithm employs dynamic programming?
(A)Prim's algorithm for finding a minimum spanning tree
(B) Dijksta algorithm for solving the single source shortest paths problem
(C) Floyd-Warshall for solving the all pair shortest paths problem
(D)Hufiman algorithm for constructing a Hufiman code
(E) Kruskal's algorithm for finding a minimum spanning tree

27. 1og(n!) is asymptotically equal to (A) θ(n) (B) θ(nlog(logn) (C) θ(n2logn) (D) θ(nlogn) (E) θ(logn)2)

28. Which one of the following statements is not correct? (A) If an edge is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph. (Definition: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.) (B) If a graph has a unique minimum spanning tree then, for every cut of the graph, there is a unique light edge crossing the cut. (C) A graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. (D) Let e be a maximum-weight edge on some cycle of the graph G = (V, E), then there is a minimum spanning tree of G' = (V, E-{e}) that is also a minimum spanning tree of G = (V, E). (E) Let (u, ) be a minimum-weight edge in a graph G. Then (u, v) belongs to some minimum spanning tree of G.

29. The digraph shown below is a flow network from source s to sink t, where the number on each edge represents the edge capacity. What is the minimum cut capacity between s and t? (A)20(B)21 (C)22 (D)23 (E)24

30. The digraph shown below is a flow network from source s to sink t, where the number on each edge represents the edge capacity. What is the value of the maximum flow from s to t?(A)19(B)20 (C)21 (D)22 (E)23

32. Which of the following are false? i. The worst-case running time and expected running time are equal to within constant factors for any randomized algorithm. ii. Sorting 6 elements with a comparison sort requires at least 10 comparisons in the worst case. iii. In Blum, Floyd, Pratt, Rivest, and Tarjan [1973] worst-case linear-time order statistics algorithm, instead of dividing the n elements into groups of 5, dividing them into groups of 3 gives the same linear time complexity. iv. If a dynamic programming problem satisfies the optimal substructure property, then a locally optimal solution is a globally optimal. (A)i (B)i,iii,iv (C)i,ii；,iv (D)ii,iv (E)iii,iv

33. Which of the following are true? i. The maximum flow problem is in P ii. If a problem is in P, it must also be in NP iii. If a problem is in NP, it must also be in P iv. If a problem is NP-complete, it must also be in NP (A) i,ii (B)i,ii,ii；,iv (C)i,ii,iv (D)i,ii,iv (E)i,iv

34. Huffman codes are used as a very effective technique for compressing data. A data file of 100 characters contains only the characters a-f, with frequency 45, 12, 13, 9, 16, and 5. Use the Hufiman variable-length codes, the file can be encode in how many bits? (A) 224 (B) 300 (C) 100 (D) 124(E) 324

35. Complete the pseudo code below for the counting sort algorithm. We assume Input: A[1. . n],where A[j] {0, 1, , k} forj = 1, 2,..., n. Array A and values n and k are given as parameters.Output: B[1 . . n], sorted. B is assumed to be already allocated and is given as a parameter. Auxiliary storage: C[O . . k]COUNTING-SORT(A, B, n, k)   (A) (B)(C) (D)(E)

36. For a chain of matrix A1A2A3A4 with their dimensions in the following table, parenthesize the product A1A2A3A4 to minimize the number of scalar multiplications. What is the minimum number of scalar multiplications?(A)82 (B)72 (C)112 (D)99(E)70

37. Assume that quicksort is being used to sort an array A with values 4 2 8 73 1 5 6. After the first invocation to the partition algorithm the array looks like this: 2 3 1 4 7 5 8 6. Which value could have been chosen as the pivot? (A) 4(B)7 (C)1 (D)3 (E)8