课程名称︰演算法设计与分析 课程性质︰必修 课程教师：萧旭君 开课学院：电资学院 开课系所︰资工系 考试日期（年月日）︰2014.11.07 考试时限（分钟）：30分钟 试题 : ┌─────────────────────────────────────┐ │Decide whether the following statement, particularly the underlined │ │phrase, is true or false. Explanation is not required in this quiz but │ │will be required in the midterm. │ └─────────────────────────────────────┘ 1) 2^(n+1) = O(2^n) 2) 2^(2n) = O(2^n) 3) The solution to the recurrence T(n) = 4T(n/2) + (n^2)log(n) is Θ((n^2)(log(n))^2) 4) Divide-and-Conquer algorithms will always output incorrect answers if the problem has overlapping subproblems.￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ 5) Finding a counterexample to a greedy choice proves that there exists no greedy algorithm to this problem. ￣￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ 6) A 0/1 Knapsack Problem can be solved in O(mn) even if the values of the objects are not integers. ￣￣￣￣￣￣￣￣￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣ 7) To prove the correctness of a greedy algorithm, we must prove that every optimal solution contains the greedy choice. ￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ 8) Any dynamic programming algorithms with n subproblems will run in O(n) time. 9) Recall the Stable Matching Problem. If a man M and a woman W each put each other at the top of their respective preference lists, then M must be paired with W in every stable matching. ￣￣￣￣￣ ￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣￣ 10) Short answer: In a bottom-up dynamic programming algorithm, given the recurrence relation A(i,j) = F(A(i,j-1), A(i-1,j-1), A(i-1,j+1)), provide a valid traversal order to fill the DP table. Answer: 1) T. The growth rate of 2*(2^n) is same as 2^n. 2) F. 4^n can't be asymptotically bounded by 2^n. 3) T. Verify the solution by inserting it back to the recursive function. 4) F. Think about Fibonacci. The DC algorithm is inefficient but correct. 5) F. There might be other greedy choices that work. 6) T. Values can be non-integer, not weights. 7) F. We need to prove that our solution is as good as the optimal solutions without the greedy choice, if exist. 8) F. The time to solve a subproblem may be more than O(1). 9) T. If M and W are not matched, they have incentive to leave their respective partners, resulting in instability. 10) Value at [i,j] in the 2D DP array depends on values at [i,j-1], [i-1,j-1], [i-1, j+1]. Hence, we can fill the array row by row, from top-left to bottom-right. --

※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 1.160.216.70 ※ 文章网址: https://webptt.com/cn.aspx?n=bbs/NTU-Exam/M.1435558574.A.D86.html