课程名称︰资料结构与演算法下 课程性质︰系必修 课程教师︰蔡欣穆 开课学院：电资学院 开课系所︰系讯系 考试日期（年月日）︰2011/4/22 考试时限（分钟）：180min 是否需发放奖励金：是的，感谢 （如未明确表示，则不予发放） 试题 : Prob1.In each of the following question, please specify if the statement is true or false. If the statement is true, explain why it is true. If it is false, explain what the correct answer is and why. (20 points. For each question, 1 point for the true/false answer and 3 points for the explanations.) 1.n㏒n is polynomially larger than n. 2.n^(1+10^(-100)) is polynomially larger than n㏒n. 3.As long as a problem exhitbits optimal substructure, it can be solved by using a greedy algorithm. 4.The solution of T(n)=4T(n/2)+n^2 is T(n)=Θ(n㏒n). 5.As long as a recurrence is of the form T(n)=a(Tn/b)+f(n), it can be solved by using the master method. Prob2."Short answer" questions: (25 points) 1.What is the main job of a Quality Assurance(QA) engineer in a software company?(4 points) 2.Give a formal definition of "uniform random permutation".(4 points) 3.Derive an optimal Huffman code for the frist n Fibonacci numbers, i.e., {C1:1 C2:1 C3:2 C4:3 C5:5 C6:8 C7:13 C8:21 ... Cn:F(n)}. in other words, show the general form of the codeword for the i-th charater Ci(with F(i) as its frequency). (5 points) 4.Give two reasons for implementing the paper prototype instead of the "real" prototype in a software project. (4 points) 5.How do we roughly estimate the cost of a software product? (4 points) 6.Give two reasons for writing down the specifications of a software project before we start writing codes.(4 points) Prob3.Given a list of n distinct numbers (not sorted), please derive a divide- and-conquer algorithm to return the first k smallest numbers in the list. Your algorithm should have a running time of O(n). Note that you cannot use the number selection algorithm taught in the class for k times, as the running time will be Θ(kn)=O(n^2). Sorting does not work either as it will take O(n㏒n). In addition to the algorithm, please write down the recurrence representing the running time, solve the recurrence, and prove your solution by induction.(15 points, 7 points for the algorithm, 3 points for the recurrence, and 5 points for the proof) Prob4.Use the recursion-tree method to derive an asymptotic tight upper bound for T(n)=T(n/2)+T(n/4)+T(n/8)+n. You can assume that T(n) is a constant when n is sufficiently small. Prove that your bound is correct by induction.(10 points, 5 points for the recursion-tree and 5 points for proof) Prob5.For bit strings X=X1...Xm, Y=Y1...Yn and Z=Z1...Zm+n, we say that Z is an interleaving of X and Y if it can be obtained by interleaving the bits in X and Y in a way that maintains the left-to-right order of the bits in X and Y. For example if X=101 and Y=01 then X1X2Y1X3Y2=10011 is an interleaving of X and Y, whereas 11010 is not.(15 points) 1.Please come up with the definition of the subproblem. Use your definition and prove that this problem has optimal substructure. (5 points) 2.Give the most efficient algorithm you can to determine if Z is an interleaving of X and Y. (7 points) 3.Analyze the time complexity of your algoithm as a function m=|X| and n=|Y| Prob6.Consider the problem of making change for n dollars using the fewest number of coins. Assume that each coin's value is an integer. The same coin can be used for any number of times in the change. (25 points) 1.Prove that the problem exhibits optimal substructure. (5 points) 2.Assume the following set of coins is available to you:1,5,10,50. Prove that under this codition, the problem ahs the greedy property. (5 points) 3.Describe a greedy algorithm to solve the problem with the coin set in 2. 4.Give a set of coins for which the greedy algorithm in 3 does not yield an optimal solution. Your set should nclude a one-dollar coin so that there is a solution to every value of n. Explain the intuition behind your choice of coins in the set. (3 points) 5.Describe a dynamic programming algorithm which solve the problem with any coin set with k different coins, assuming that one of them is a one-dollar coin. (7 points) Prob7.This problem examines three algorithms for searching for a value x in an unsorted array A consisting of n elements(x appears in A for k times, k≧0): (20 points) ˙Algorithm α: We pick a random index i into A. If A[i]=x, then we terminate; otherwise, we continue the search by picking a new random index into A. We continue picking random indices into A until we find an index j such that A[j]=x or until we have checked every element of A. Note that we pick from the whole set of indices each time, so that we may examine a give element more than once. ˙Algorithm β: The algorithm searches A for x in order, considering A[1],A[2], ...,A[n] until either it finds A[i]=x or it reaches the end of the array. Assume that all possible permutations of the input array are equally likely. ˙Algorithm γ:We uniformly and randomly permute the input array A and then run Algorithm β 1.For each algorithm, derive the expected running time when (a)k=0 (b)k≧1. (18 points, 3 points for each answer) 2.Which algorithm would you use? Please explain your answer. (2 points) Prob8.This semestere we made lots of changes in the course compared to last semester (homeworks, programming assignments, course content), and we are curious about how you feel about the current form of the course. If you have the power of changing 3 things in the course, what would these 3 things be and how would you change them? Your feedbacks are very important to the teaching team; we thank you for your valuable opinion.:) (10 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 123.193.6.232