(b) T(n) = 2T(n-1) +n

4.(5 points) Five people occupy five seats. If five seats are arranged in a circle, bow many different ways can the five people select their seats?

5. (4 points) Let G = (V, E) be a graph. If V has twelve members, in which four members each has a degree of three, and the degree of each remaining member is five, how many members does E have?

6. (8 points) A class at a college consists of 19 students who sit at a circular table. The instructor wants each student to sit next to two different classmates cach day. For bow many days can they do this?

(a) T(n) = T(n-1) + 2n

8. (8 points) Given a sequence of n integers A = (a1, a2,..., an), the longest increasing subsequence problem is to find a longest subsequencealk For example, (1,2,5,8) is a longest increasing subsequence of (4,1,7,5,2,5,8,4). Please use the dynamic programming technique to design an O(n2) time algorithm for solving the longest increasing subsequence problem. Please also justify your algorithm and its time complexity.

9. (7 points) Given a set S of n numbers, the k-partition problem is to determine whether or not S can be partitioned into k subsets of the same sum. For example, let S ={1,2,9,12,18}. Then for the two-partition problem, we indeed can partition S into two subsets S1 = {1,2,18} and S2 = {9,12} such that the sum of all elements in S1 equals to the sum of all elements in S2. In fact, it can be proved that the two-partition problem is NP-complete. In the situation where the two-partition problem is already NP-complete, please prove that the three-partition problem is also NP-complete.

(a) Iff(n)= O(g(n)), we can say that g(n) ≥f(n) for n ＞ 1.

(b) Merge Sort has worst-case time complexity O(n log n), while the worst-case time complexity of Insertion Sort is O(n2. One weakness of Merge Sort is that it requires additional space. Therefore, if space allows, we should always use Merge Sort for better efficiency.

(c) Searching a specific key in a binary search tree takes O(log n) time, where n is the number of keys in the binary search tree.

(d) Given the pre-order and level-order traversal sequences, we can construct a unique binary tree.