課程名稱︰演算法設計與分析 課程性質︰必修 課程教師：蕭旭君 開課學院：電資學院 開課系所︰資工系 考試日期（年月日）︰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/m.aspx?n=bbs/NTU-Exam/M.1435558574.A.D86.html