36. For a chain of matrix A₁A₂A₃A₄ with their dimensions in the following table, parenthesize the product A₁A₂A₃A₄ 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

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)

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)

40. Determine the expected search cost of an optimal binary search tree for a set of n = 5 keys with the following probabilities. We assume that all searches are successful. (A) 2.15 (B)1.15 (C)2.10 (D) 1.10 (E) 2.0

101. _____ , the company’s CEO hasn’t decided whether to fire the manager and his team who handle the publicity and all that business. (A) Even as (B) So far (C) Already (D) A while ago

102. Gabar Restaurant serves freshly cooked dishes in our live cooking stations _____ customers can watch the chefs turn fresh ingredients into delicious meals. (A) which (B) whose (C) what (D) where