课程名称︰演算法设计与分析 课程性质︰系必修 课程教师︰蔡欣穆 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2011/11/18 考试时限（分钟）：180 是否需发放奖励金：是 谢谢 （如未明确表示，则不予发放） 试题 : Problem1. In each of the following question,please specitfy 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 true/false answer and 3 points for the explanations.) 1.The person who should close the bug report is the one who fixes the bug. 2.nlogn is ploynomially larger than n. 3.nlogn is ploynomially smaller than n^1.001. 4.Master theorem sometimes cannot be applied even if the recurrence is in the form of T(n)=aT(n/b)+f(n). 5.In all cases,using a top-down approach when using dynamic programming to solve a problem is slower than using a bottom-up approach since former would usually involve the overhead of recursively calls(setting up stack and local variables). Problem 2. "Short answer" questions: (32 points) 1.Describe two benefits of using paper prototype instead of the regular software prototype. (4 points) 2.What are the 3 things required in every bug report? (6 points) 3.Explain why a binary tree cannot correspond to an optimal prefix code if it is not full(no internal node has only one children). (4 points) 4.Show how you would use an adjacency matrix to represent directed graph G in Figure 1.(3 points) 5.Show how you would use an adjacency list to represent directed graph G in Figure 1.(3 points) 6.Draw a breadth-first tree of directed graph G in Figure 1. Assume that we start the breadth-first search on vertex 2.(4 points) 7.Draw a depth-first tree of directed graph G in Figure 1. Assume that we start the depth-first search on vertex 2.(4 points) 8.Following the previous question,after the depth-first search you performed on G,mark the type of each edge in the original graph G.The types of the edges include tree edges,forward edges,back edges,cross edges.(4 points) －→ 1←－－2←－3 ↑ ↖↙↗↖ ↙ ∣ 4 5 ∣↙↗ ↘↖ 6 ← 7←－－8 Figure 1.:Directed Graph G i∣ 0 ∣ 1 ∣ 2 ∣ 3 ∣ 4 ∣ 5 ∣ 6 ∣ 7 | －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ pi∣ ∣ 0.04∣ 0.06∣ 0.08∣ 0.02∣ 0.10∣ 0.12∣ 0.14| －－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－ qi∣ 0.06∣ 0.06∣ 0.06∣ 0.06∣ 0.05∣ 0.05∣ 0.05∣ 0.05| Table 1:Keys and Their Probabilities Problem 3. Determine the cost and the structure of an optimal binary search tree for a set of n=7 distinct keys with the probabilities in Table 1. If you do not remember what pi and qi represents,here are some hints.You are given a sequence K = <k1,k2,...,k7> of 7 distinct keys in sorted order(so that k1<k2<...<k7). For each key ki,we have a probability pi that search will be ki Some searches may be for value not in K,and so we also have 7+1 "dummy keys", d0,d1,...,d7 representing values not in K. In particular,do represents all values less than k1,dn represents all values greater than kn,and for i=1,2,..6 and dummy key di represents all values between ki and k(i+1).For each dunmmy key di,we have a probability qi that a search will correspond to di.(10 points) Problem 4. Use a recursion tree to determine a good asymptotic upper bound on the recurrence T(n) = T(n/2) + n^2. Use the substitution method t verify your answer.(10 points,5 points for the recursion tree and 5 points for substitution method) Problem 5. Given an unweighted directed graph G=(V,E),we need to find the shortest path from u to v,where u,v € V.Show that the problem of finding the shortest path from u to v exhibits th optimal substructure property.( Hint:prove that the shortest path between u and v contains the shortest paths from u to another vertex w and from w to v)(5 points) Problem 6. Suppose you are given an array A[1...n] of sorted integers that has been circularly shifted k positions to the right.For example,[35,42,5,15,27,29] is a sorted array that has been circularly shifted k=2 positions,while [27,29, 35,42,5,15] has been shifted k=4 positions.We can obviously find the largest element in A in O(n) time.Describe an O(logn) algorithm based on the divide -and-conquer strategy to find the largest element in A.(You need to show that your algorithm's time complexity is O(logn))(10 points) Problem 7.There is a river which flows horizontally through a country.There are N cities on the north side of the river are n1,n2...,nN,and the X coordinates of the N cities on the south side of the river are s1,s2,...sN. Assume that we can only build bridges between cities with th same number; that is,we can only build bridges between cities with coordinates ni ans si, where 1 <=i<= N .In this problem,we ask you to determine the maximum number of bridges we can build without any bridges crossing with each other.Note that n1 through nN an s1 through sN are both not sorted. 1.Describe your definition of a subproblem.Use that definition,prove that this problem exhibits optimal substructure.(5 points) 2.Describe a dynamic-programming algorithm to solve the problem.(10 points) 3.What is the time complexity of your algorithm ?(3 points) Problem 8. Modern computers use a cache to store a small amount of data in a fast memory.Even though a program may access large amounts of data,by storing a small subset of the main memory in the cache - a small but fast memory - overall access time can greatly decrease. When a computer program executes,it makes a sequence <r1,r2,...,rn> of n memory request,where each request is for a particular data element.For example,a program that access 4 distinct elements {a,b,c,d} might make the sequence of request <d,b,d,b,d, a,c,d,b,a,c,b>. Let k be the size of the cache.When the cache contains k elements and the program request (k+1)st element,the system must decide,for this and each subsequent request,which k elements to keep in the cache.More precisely,for each request ri,the cache-management algorithm checks whether element ri is already in the cache.If it is,then we have a cache hit; otherwise,we have a cache miss.Upon a cache miss,the system retrieves ri from the main memory ,and the cache-management algorithm must decide whether to keep ri in the cache.If it decides to keep ri and the cache already holds k elements,then it must evict one element to make room for ri.The cache -management algorithm evicts data with the goal of minimizing the number of the cache misses over the entire sequence of requests. Typically,caching is an on-line problem.That is,we have to make decisions about which data to keep in the cahe without knowing the future requests.Here, however,we consider the off-line version of this problem,in which we are given in advance the entire sequence of n requests and the cache size k,and we wish to minimize the total number of cache misses. We can solve this off-line problem by a greedy strategy called furthest-in -future, which choose to evict the item in the cache whose next access in the request sequence comes furthest in the future. 1.Write pseudocode for a cache management that uses the furthest-in-future strategy.The input should be a sequence <r1,r2,...,rn> of requests and a cache size k ,and the output should be a sequence of decisions about which data element(if any) to evict upon each request.What is the running time of your algorithm?(10 points) 2.Show that the off-line caching problem exhibits optimal substructure. (5 points) 3.Prove that furthest-in-future produces the minimum possible number of cache misses(prove that this greedy choice is correct).(5 points) Problem 9.I have the tradition of letting the students write some feedbacks about the course in the exam and I would like to continue this tradition (though you have just given me some feedbacks in homework 2,but hey,10 exam points for free!):please write down 3 things you like about this course and 3 things that you would like to see some changes(and your suggestion about how we should change them).(10 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.245.136 ※ 编辑: garychou 来自: 140.112.4.182 (11/19 02:22) ※ 编辑: garychou 来自: 140.112.4.182 (11/19 02:25)