课程名称︰ 演算法 课程性质︰ 系订选修 课程教师： 张耀文 开课学院： 电资学院 开课系所︰ 电机系 考试日期（年月日）︰ 2008/11/12 考试时限（分钟）： 150mins 是否需发放奖励金： yes （如未明确表示，则不予发放） 试题 : Problem 1. (16 pts total) For each of the following recurrence relations, give the asymptotic growth rateof the solution using the θ notation. Assume in each case that T(n) is θ(1) for n≦10. (a) (5 pts) T(n) = 5T(n/2) + (n^3)(lg n). (b) (5 pts) T(n) = T(√n) + lglg n. (c) (6 pts) T(n) = T(pn) + T(qn) + n, where p + q = 1. Problem2. (20 pts total) Please give a brief answer for each of the following questions. Q1. If f(n) is asymptotically positive, is f(n) + o(f(n)) = O(f(n))? Why? Q2. Can we have a priority queue in the comparison sorting model with both the properties：(1)EXTRACT-MIN runs in O(lglg n) time, and (2)BUILD-MAX-HEAP runs in O(n) time? Why? Q3. Suppose that an array contains n numbers, each of which is 0, 1, or 2. Then, can this array be sorted in linear time in the worst case? How to do it if it can, or why it is not possible? Q4. Can we put the numbers 1,2, ...., 10 in a tree such that it is both a valid max-heap and binary search tree at the same time? Why? Problem 3. (12 pts total) Let A0 be a numerical array of length n, originally sorted into ascending order. Assume that k entries of A0 are overwritten with new values, producing an array A. Futhermore assume you have an array B containing n values (0 or 1), where B[i] is true if A[i] is one of the k values that was overwritten, and false otherwise. (a) (9 pts) Give a fast algorithm to sort A into ascending order, with time complexity better than O(nk). (Hint：Separate out A into two lists.) (b) (3 pts) Give the time complexity of your algorithm in big-O notation, as a function of n and k (the tighter, the better). Problem 4. (16 pts total) Search trees. (a) (5 pts) Give the binary search tree that results from successively inserting the keys 9,10, 2, 1, 7, 6, 8 into an initially empty tree. (b) (5 pts) Label each node in the tree with R or B denoting the respective colors RED and BLACK so that the tree is a legal red-black tree. (c) (6 pts) Give the red-black tree that results from inserting the key 3 into the tree of (b). (Hint：The pseudocode for inserting a node in a red-black tree is given below) ---------- RB-Insert(T,x) 1. Tree-Insert(T,x); 2. color[x]←RED; 3. while x ≠ root[T] and color[p[x]]＝RED do 4. if p[x]＝left[p[p[x]]] then 5. y←right[p[p[x]]]; 6. if color[y]＝RED then /*uncle's color is red*/ /*Case 1*/ 7. color[p[x]]←BLACK; 8. color[y]←BLACK; 9. color[p[p[x]]]←RED; 10. p←[p[x]]; 11. else if x＝right[p[x]] then /*uncle's color is black*/ /*Case 2*/ 12. x←p[x]; 13. Left-Rotate(T,x); /*Case 3*/ 14. color[p[x]]←BLACK; 15. color[p[p[x]]]←RED; 16. Right-Rotate(T,p[p[x]]); 17. else (same as then clause with "right" and "left" exchanged) 18. color[root[T]]←BLACK; ------------- Problem 5. (16 pts total) You are asked to determine the cost and structure of an optimal binary search tree fpr a set K＝＜k1,k2,k3,k4＞ of n＝4 keys with the following prababilities： i 0 1 2 3 4 pi - 0.10 0.10 0.20 0.05 qi 0.05 0.10 0.20 0.10 0.10 a set of probabilities P＝＜p1, p2, p3, p4＞for searching the keys in K and Q＝＜q0, q1, q2, q3, q4＞for unsuccessful searches, as discussed in class. (a) (12 pts)Fill every field in the e,w, and root tables, where e[i,j] gives the expected cost of searching an optimal binary tree containing the keys ki,...,kj, w[i,j]＝w[i,j-1] + pj + qj, and root[i,j] records the root of subtree containing the keys ki,...,kj. (b) (4 pts)Find an optimal binary search tree of the given probabilities and give the expected search cost of the tree. e w 4 1 4 1 j 3 ／＼ 2 i j 3 ／＼ 2 i 2 ／＼／＼ 3 2 ／＼／＼ 3 1 ／＼／＼／＼ 4 1 ／＼／＼／＼ 4 0 ／＼／＼／＼／＼ 5 0 ／＼／＼／＼／＼ 5 ／＼／＼／＼／＼／＼ ／＼／＼／＼／＼／＼ ＼／＼／＼／＼／＼／ ＼／＼／＼／＼／＼／ root 4 1 j 3 ／＼ 2 i 2 ／＼／＼ 3 1 ／＼／＼／＼ 4 ／＼／＼／＼／＼ ＼／＼／＼／＼／ Problem 6. (12 pts total) Proffessor Chang plans to drive a car from Taipei to Tainan along the Formosa highway (Highway #3) for a meeting. His car's gas tank, when full, holds enough gas to travel n kilometers, and his map gives the diatances between gas stations on his route. He wishes to make as few gas stops as possible along the way. Give an efficient algorithm to determine at which gas stations he should stop and prove the optimality of your algorithm. Problem 7. (18 pts total) Given a log of wood of length k, Woody the woodcutter will cut it once, in any place you choose, for the priceof k dollars. Suppose you have a log of length L, marked to be cut in n different locations labeled 1,2,...,n. For simplicity, let indices 0 and n+1 denote the left and right endpoints of the original log of length L. Let the distance of mark i from the left end of the log be di, and assume that 0＝d0＜d1＜d2＜...＜dn＜d(n+1)＝L. The wood-cutting problem is the problem of determining the sequence of cuts to the log that will (1) cut the log at all the marked places, and (2) minimize your total payment to Woody. (a) (4 pts) Give an example illustrating that two different sequences of cuts to the same marked log can result in two different costs. (b) (8 pts) Let c(i,j) be the minimum cost of cutting a log with left endpoint i and right endpoint j at all its marked locations. Suppose the log is cut at position m, somewhere between i and j. Define the recurrence of c(i,j) in terms of i,m,j,di and dj. Briefly justify your answer. (c) (6 pts) Using part (b), give an efficient algorithm to solve the wood- cutting problem. Use a table C of size (n+1)×(n+1) to hold the values C[i][j]＝c(i,j). What is the running time of your algorithm? Problem 8. (4 pts total) Please give two of your opinion(s)/comment(s) on this course (e.g., strengths and weakness)? Any specific comments that may improve the quality of this course are very much welcome. Thank you. --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 118.165.159.105 ※ 编辑: Hsnuary 来自: 118.165.155.7 (11/15 08:31)