[試題] 98下 呂學一 資料結構與演算法下 期中考消失
課程名稱︰資料結構與演算法下
課程性質︰系必修
課程教師︰呂學一
開課學院：電資學院
開課系所︰資工系
考試日期（年月日）︰2010/4/23
考試時限（分鐘）：180
是否需發放獎勵金：是
（如未明確表示，則不予發放）
試題 :
------------------------------------------------------------------------------
說明：可按任何順序答題，上學期的上課內容才可以直接引用。題目難度不均，慎選答題
順序。1
------------------------------------------------------------------------------
第一題 Let G be an n-node m-edge directed graph with positive edge length,
where m>=n. Let r be a node of G. For each node u of G, let d_r(u) denote the
distance (i.e., length of the shortest path) from r to u. Give an O(mlogn)-time
algorithm for computing d_r(u) for all nodes u of G. You have to describe your
algorithm (5 points), prove its correctness (5 points), and analyze its time
complexity (5 points).
------------------------------------------------------------------------------
第二題 我們在課堂上解釋Johnson的reweighting技術時，說到為了把all-pairs distance
的問題轉換成圖上所有的邊長都變成大於或等於零，在原圖之外多加一個新點r，並且讓r
到每一個原圖上的點都加一個長度為零的邊，然後替這個新圖上的d_r(u)當作點u上面的權
重進行edge reweighting。如果我們現在「簡化」Johnson的技術，直接挑一個原圖上的點
為r，在不加點不加邊的狀況下，在原圖上面計算d_r(u)，然後以這個d_r(u)為點u的權重
進行edge reweighting。請問這樣的做法還是正確的嗎？如果你覺得簡化版仍然正確，請
證明簡化版在edge reweighting之後仍然保留原圖原邊長上的shortest path (5 points)
，並維持新邊長大於或等於零的性質 (5 points)。如果你覺得簡化版有誤，請舉例說明
(10 points)。 (考試時另外加了一個條件: 圖上任兩個點之間都有路徑相連)
------------------------------------------------------------------------------
第三題 根據Hamiltonian Path問題是NP-hard，證明Longest Path問題也是NP-hard。(5
points)
另外，我們可不可以把Longest Path這個問題的圖上每個邊長乘以-1然後使用shortest-
path algorithm(例如Bellman-Ford是可以處理邊長有正有負的情況)求解，然後得證NP=P
？請說明你的理由 (5 points)。
------------------------------------------------------------------------------
第四題 Let G be an n-node m-edge undirected graph with general edge weights,
where m>=n. Give an O(mlogn)-time algorithm for computing a minimum-weight
spanning tree of G. You have to describe your algorithm (5 points), prove its
correctness (5 points), and analyze its time complexity (5 points).
另外，如果我們想要找最重的spanning tree，可否把原圖上的edge weight乘上-1，然後
以minimum weight spanning tree的演算法求解？請說明你的論證 (5 points)。
------------------------------------------------------------------------------
第五題 Edmond and Karp showed that if each iteration of the algorithm of Ford
and Fulkerson augments the current flow using a shortest path in the current
residual network, then the number of iterations can be bounded by a polynomial
in the number of nodes of the input network. You are asked to prove this bril-
liant observation of Edmond and Karp (15 points). (附註：不需要確切的時間複雜
度，只要證明number of augmentation iterations是polynomial in the number of
nodes即可。)
------------------------------------------------------------------------------
第六題 Let S be an n-bit binary string. What are the definitions of Z(i), R(i)
, and L(i) (for each i=1,2, ... ,n) used by Gusfield's Z-values algorithms (6
points). Prove or disprove that if R(i-1)>=i and Z(i-L(i-1)+1)>R(i-1)-i+1,
then R(i)=R(i-1) for each i=2,3, ... n (9 points).
------------------------------------------------------------------------------
第七題 S是二度空間平面上的n個線段。假設S之中沒有任何三個線段共交點，而且已經知
道這n個線段之間 的交點只有O(n)個。請證明或著反證「輸出S中所有線段之間的所有交
點」這個問題可以在O(nlogn)的時間內解掉。(15 points)
-----------------------------------
1 張貼於NTU-Exam時可以和「隨機客」分享版主發放的「獎勵」嗎？ ;)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
推
04/24 14:28, , 1F
04/24 14:28, 1F
推
05/02 14:32, , 2F
05/02 14:32, 2F
推
06/06 15:24, , 3F
06/06 15:24, 3F