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

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

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

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

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

38. Professor Chen uses the following algorithm for merging k sorted lists, each having n/k elements. He takes the first list and merges it with the second list using a linear-time algorithm for merging two sorted lists, such as the merging algorithm used in merge sort. Then, he merges the resulting list of 2n/k elements with the third list, merges the list of 3n/k elements that results with the fourth list, and so forth, until she ends up with a single sorted list of all elements. What is the worst-case running time of the professor Chen's algorithm in terms of n and k. (A)θ(log(nk))(B)θ(nk) (C)θ(nlogk) (D)θ(lognlogk) (E)θ(n)

39. A hiker faces the Knapsack problem. There are 7 items to be packed into the knapsack, each with value viand weight wi as shown in the following table. The knapsack, which is initially empty, can hold a maximum weight of 16, so some item(s) must be left behind. The optimality criterion is to maximize the total value of the items that are placed in the knapsack.The hiker fills the knapsack one item at a time. Now consider the following two cases: (a) fractions of items cannot be packed, and (2) fractions of items can be packed. What are the optimal values of the items that are packed in these two cases respectively? Give the answer in the form of (no-fractions-allowed, fractions-allowed). (A)(28,30.5) (B)(37,40)(C)(30,34) (D)(38,40) (E)(34,38.5)