[考古] 演算法/黃秀芬/96下期末考

看板FCUProblems作者XX9 ( 佛曰: ....)時間17年前 (2009/01/16 21:22)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串1/1

※ [本文轉錄自 FCU_Talk 看板] 作者: coolsprite ( ) 看板: FCU_Talk 標題: [考題][資訊系][演算法][黃秀芬 96下期末考] 時間: Tue Jun 24 16:59:28 2008 本學期最後一張考卷....( ′-`)y-～ 1.(40%)True or False (1) The Huffman algorithm for constructing an optimal prefix code is a greddy algorithm. (2) The topological sort of an arbitrary directed graph G = (V,E) can be computed in linear time. (3) Prim's algorithmfor finding a minimum spaning tree of weighted, undirected graph is an example of a dynamic programming algorithm. (4) One can give an Ο(V+E) time algorithmfor the single-source shortest paths problem. (5) The Floyd-Warshall algorithm (for all-pair shortest paths) run in Θ（V^3） . (6) Johnson's algorithm (for all-pair shortest paths) requires that all edge weights are nonnegative. (7) The halting problem is an element of NP (8) 0-1 knapsack problem is NP-complete (9) S. Cook had proved that P≠NP (10)2SAT is an element of P 2.(15%) The (fractional) Knapsack problem is: maximize Σ (PiXi) 1≦i≦n PS.i表示下標 subject to Σ (WiXi) ≦ m (0≦Xi≦1,for all of 1≦i≦n) 1≦i≦n Find an optimal solution to the instance n=7,m=15, (P1,P2,....P7) = (10,5,15,7,6,18,3),and (W1,W2,....W7) = (2,3,5,7,1,2,1) 3.(10%) Write down the Bellman-Ford algorthm for signle-source shortest path problem and analyse its running time. 4.(10%) Give an Ο(n^2)-time algorthm to find the longest monotonically increasing subsequence of a sequence of n numbers. 5.(10%) Professor Wang claims that there is a simpler way to reweight edges than the method used in Johnson's algorthm. Letting w* = min(u,v){w(u,v)} ※(u,v) is an element of E just define w'(u,v) = w(u,v) - w* for all edges (u,v) is an element of E What is wrong with the professor's method fo reweighting? PS.因為打不出 w+bar 所以用w'代替 6.(15%) We are given a directed graph G = (V,E) on which each edge (u,v) is an element of E has an associated value r(u,v), which is a real number in the range 0≦r(u,v)≦1 that represent the reliability of a communication channel from vertex u to vertex v.We interpret r(u,v) as the probability that the channel from u to v will not fail, and we assume that these probability are indepent. Give an efficient algorthm to find the moreliable path between two given vertices. 7.(10%) Prove that node cover decision problem(NCDP) is NP-HARD. (Hint: CDP α NCDP) -- 這學期這科會不會過呢？會不會像組合數學一樣發生奇蹟呢？來～五樓哩工跨賣！ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 118.170.136.89

推

jack2749

06/24 17:02,

06/24 17:02

推

tang76430

06/24 17:05,

06/24 17:05

推

Courake

06/24 17:09,

06/24 17:09