[試題] 102上 呂學一 演算法設計與分析 2nd小考
課程名稱︰演算法設計與分析
課程性質︰必修
課程教師︰呂學一
開課學院：電機資訊學院
開課系所︰資訊系
考試日期（年月日）︰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
推
11/21 21:28, , 1F
11/21 21:28, 1F
→
11/21 21:29, , 2F
11/21 21:29, 2F
→
11/21 21:30, , 3F
11/21 21:30, 3F
→
11/21 21:31, , 4F
11/21 21:31, 4F
→
11/21 21:33, , 5F
11/21 21:33, 5F
→
11/21 21:34, , 6F
11/21 21:34, 6F
→
11/21 21:35, , 7F
11/21 21:35, 7F
→
11/21 21:35, , 8F
11/21 21:35, 8F
→
11/21 21:36, , 9F
11/21 21:36, 9F
→
11/21 22:51, , 10F
11/21 22:51, 10F
※ 編輯: penknife211 來自: 140.112.217.36 (11/21 22:54)
推
12/09 15:41, , 11F
12/09 15:41, 11F