作者penknife211 (老闕的學生)
看板NTU-Exam
標題[試題] 102上 呂學一 演算法設計與分析 2nd小考
時間Thu Nov 21 18:22:46 2013
課程名稱︰演算法設計與分析
課程性質︰必修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊系
考試日期（年月日）︰2013.11.21
考試時限（分鐘）：60
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
總共兩題，每題五十分：
1. We showed Johnson's reweighting technique for computing all-pairs shortest
paths in an n-node m-edge directed graph G with general edge weight w.
Specifically, Johnson proposed adding a new node v0 to G and a zero-weight
directed edge from v0 to each node v of G. Let G0 denote the resulting graph
with n+1 nodes. The adjusted edge weight ^w for each directed edge
(u, v) in E(G) is
^w(u, v) = w(u, v) + dG0(v0, u) - dG0(v0, v),
satisfying the following properties.
Property 1. For any two nodes r and s of G, a shortest path form r to s in G
with respect to the original edge weight w has to be a shortest path from r
to s in G with respect to the adjusted edge weight ^w.
Property 2. For any edge (u, v) of G, ^w(u, v) >= 0.
Now consider the following two variants of Johnson's reweighting function.
Variant 1. Let ^w(u, v) = w(u, v) - min{ w(e) : e in E(G) }
Variant 2. Let x be an arbitrarily chosen node of G.
Let ^w(u, v) = dG(x, u) - dG(x, v).
(Every nodes in G is reachable from x, and dG(x, i) denotes the distance
from x to i in G)
Prove or disprove each of Properties 1 and 2 for each of the above two
variants of Johnson's reweighting function.
2. Consider the following "combo problem". The input is an array P of n
positive integers P[1], ......, P[n]. We additionally define P[0] = 0.
The output is an array Q of n numbers Q[1], ......, Q[n] with the following
three requirements.
Requirement 1. For each i = 1, ......, n, Q[i] is a nonnegative integer.
Requirement 2. Q[1] + Q[2] + ...... + Q[n] = n.
Requirement 3. P[ Q[1] ] + P[ Q[2] ] + ...... + P[ Q[n] ] is meximized over
all Q that satisfy Requirements 1 and 2.
Prove or disprove that the above combo problem can be solved in O(n^2) time.
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.7.214
1F：推 hil :最後一行problems --> problem ^__^ 11/21 21:28
2F：→ hil :第一題第三行 Specially --> Specifically 11/21 21:29
3F：→ hil :第一題第六行belongs to --> in 11/21 21:30
4F：→ hil :Variant 1之前一行 varient -> variant 11/21 21:31
5F：→ hil :Variant1的the minimun w(e) with e belongs to E(G) 11/21 21:33
6F：→ hil :可以寫成 min{w(e) : e in E(G)} 11/21 21:34
7F：→ hil :dG(x, i)應該是distance from x to i in G (不是 11/21 21:35
8F：→ hil :shortest path) 11/21 21:35
9F：→ hil :謝謝! 辛苦了! ^__^ 11/21 21:36
10F：→ penknife211 :老師看得好仔細...打錯這麼多真是不好意思，已改正！ 11/21 22:51
※ 編輯: penknife211 來自: 140.112.217.36 (11/21 22:54)
11F：推 ALegmontnick:已重收 12/09 15:41