课程名称︰演算法设计与分析 课程性质︰必带 课程教师︰蔡欣穆 开课学院：电机资讯学院 开课系所︰资讯工程学系 考试日期（年月日）︰101/11/8 考试时限（分钟）：180 是否需发放奖励金：是 （如未明确表示，则不予发放） 试题 : Algorithm Design and Analysis, Fall 2012 Midterm Examination 128 points Time: 2:20pm-5:20pm (180 minutes), Thursday, November 8 ,2012 Problem 1. 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.nlogn is asymptotically larger than n. 2.√n √logn is polynomially larger than √n. 3.The specification should be written by a group of people, as the result of teamworks. 4.We can initialize a heap with only O(n) time. 5.Usually the bottom-up approach is less efficient than the top-down approach when implementing a dynamic programming algorithm. Problem 2. "Short answer" questions: (38 points) 1.Derive a Huffman code for the following frequencies of characters: {a:100, b:300, c:300, d:400, e:600, f:700}.Draw the decoding tree for the code you derive. (6 points) 2.Explain when the master theorem cannot be applied to solve the recurrences (4 points) 3.Explain what a paper prototype is. Give two advantage of using a paper prototype. (6 points) 4.Write down the recurrences that represent the running time of the quick sort algorithm in the worst case, and solve the recurrences. (6 points) 5.Write down the recurrences that represent the running time of the quick sort algorithm in the best case, and solve the recurrences. (6 points) 6.Explain the difference between functional specifications and technical specifications. (4 points) 7.Recall the divide-and-conquer algorithm that we introduce to solve the closest pair of points in 2D space problem in the lecture. Explain why it only takes O(n) time to combine the solutions of the subproblems. (6 points) Problem 3. A palindrome is a string which is not changed when it is reversed. For example, "ADA" and "BOB" are both palindromes. Derive an algorithm which will convert a given string to a palindrome with a minimum number of insertions of characters to the input string. Note that the maximum number of insertions required for any input string with a length of n is n-1. Examples: abcd -> 3insertions, abcdcba abababaabababa -> 0 insertions, abababaabababa abcdbnmzabcd -> 7 insertions, abcdcbanzmznabcdcba (22 points) 1.Write down recurrences which represent the cost of converting the string to a palindrome. Please explain clearly what the parameters of your cost function represent. (6 points) 2.Prove that this problem exhibits the optimal substructure property. (6 points) 3.Write down the algorithm which uses dynamic programming to solve this problem and outputs the minimum number of insertions. (6 points) What is the time complexity of the algorithm? (4 points) Problem 4. n people wish to cross a bridge at night. A group of at most two people may cross at any time, and each group must have a flashlight. Only one flashlight is available among the n people, so some sort of shuttle arrangement must be arranged in order to return the flashlight so that more people may cross. Each person has a different crossing speed and as a result the time for different persons to cross the bridge is different. The time for two people to cross the bridge is determined by the slower of the two. You are given a list of people and the respective time for them to cross the bridge,{t_1,t_2,...,t_n }. Your jobs is to determine the minimum time that gets all n people across the bridge. (22 points) 1.Show that this problem exhibits the optimal substructure property and how you define a subproblem. (6 points) 2.Derive the cost function using the recurrences. Explain what each parameter of the cost function means. (6 points) 3.If you use dynamic programming to solve this problem, what would be the time complexity? Please explain. (4 points) 4.Show a greedy strategy (choice) and prove that it exists in the optimal solution. (6 points) Problem 5. Use a recursion tree to give an asymtotically tight solution to the recurrence T(n) = T(αn) + T((1-α)n) + cn, where α is a constant in the range 0<α<1 and c>0 is also a constant. Then, use the substitution method to prove the solution. (10 points) Problem 6. Assume you have an array A[1..n] of n elements. A majority element of A is any element occurring in more than n/2 positions (so if n=6 or n=7, any majority element will occur in at least 4 positions). Assume that elements cannot be ordered or sorted, but can be compared for equality. (You might think of the elements as chips, and there is a tester that can be used to determine whether or not two chips are identical.) (10 points) 1.Design an efficient divide-and-conquer algorithm to determine whether a majority element exists. (6 points) 2.Determine the time complexity of your algorithm. (4 points) Problem 7.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. 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). (6 points) --

※ 发信站: 批踢踢实业坊(ptt.cc) ◆ From: 140.112.25.108 ※ 编辑: asjh612 来自: 140.112.25.108 (11/10 11:12)