课程名称︰算法设计与分析
课程性质︰必修
课程教师：萧旭君
开课学院：电资学院
开课系所︰资工系
考试日期（年月日）︰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.