[試題] 102-1 呂學一 演算法設計與分析 2nd期中
課程名稱︰演算法設計與分析
課程性質︰必修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊系
考試日期（年月日）︰102/12/5
考試時限（分鐘）：180分鐘
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
總共五題，每題二十分，可按任何順序答題。
1. Let G be an n-node m-edge directed acyclic graph. A set P of node-disjoint
paths of G is a "path cover" of G if each node of G is included in exactly one
path of P. Note that paths in P may start and end anywhere, and they may be of
any length, including 0. Therefore, the node set V(G) of G is a trivial path
cover of G with n paths. Now, please design an algorithm for finding a path
cover P of G whose number of paths is minimized over all path covers of G. The
time complexity of your algorithm is required to be polynomial in the input
size Θ(n+m). Justify the correctness and polynomial-time efficiency of your
algorithm. You may directly use any results shown in class.
2. Argue that Edmonds-Karp's shortest-path heuristics for finding an augmenting
path in the residual network in each iteration of Ford-Fulkerson's maximun-flow
algorithm enforces the algorithm to halt in O(mn) iterations of flow increases
via augmenting paths, where n is the number of nodes and m is the number of
edges, for any nonnegative edge capacity c.
3. Let G be an n-node m-edge undirected graph. The edge weights of G are
distinct. That is, no two edges of G have the same edge weight. Show how to
obtain a minimum-weight spanning tree of G in O(m+nlogn) time. You may directly
use any data structures shown in class. Justify the correctness and time
complexity of your algorithm.
4. Let T be an n-node tree with node price p. That is, the price of node v is
p(v). The price of any subset S of V(T) is p(S) = Σp(v). A subset S of V(T) is
(v in S)
"stable" if any two distinct nodes u and v in S are not adjacent in T. For
instance, the empty set is stable. So is any set consisting of exactly one node
of T. Now you are asked to design an O(n)-time algorithm to output a stable
subset S of V(T) whose price p(S) is maximized.
5. Recall that the time T(n) of Strassen's algorithm for multiplying two n ×n
matrices satisfies the recurrence relation
7 ×T(n/2) +O(n^2) if n≧2
T(n) = {
O(1) otherwise.
Prove T(n) = O(n^((log2)7)) by mathematical induction. You may assume that n is
a power of 2.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.217.36
推
12/05 22:34, , 1F
12/05 22:34, 1F
推
12/05 22:36, , 2F
12/05 22:36, 2F
※ 編輯: penknife211 來自: 140.112.104.68 (12/06 09:59)
→
12/06 10:00, , 3F
12/06 10:00, 3F