課程名稱︰演算法設計與分析
課程性質︰必修
課程教師：蕭旭君
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰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.