作者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
1F：推 jack2749:八百銀= = 第一大題是 是非題耶! 06/24 17:02
2F：推 tang76430:821銀 這篇真賺XD 06/24 17:05
3F：推 Courake:NCDP T_T 06/24 17:09
4F：推 Jimmy0398:DP T_T 06/24 18:45
5F：推 loveflames:因為PαNP，所以將P代換成CDP，即為CDPαNCDP 06/24 18:47
6F：推 dacapo:ncdp T_T 怎不是SATY >< 06/24 22:02
7F：→ loveflames:因為SATY的證明太無聊了? 06/24 22:11
8F：推 abibas:全是習題 科科 06/24 22:51
9F：→ final01:老師專考習題已經不是一天兩天的事了 06/25 00:05
10F：推 JohnRoyer:是非題 T_T 06/25 00:06
11F：推 loveflames:(11)Do you want to pass? 06/25 00:14
12F：推 pppsa: (11)Do you want to pass? (60%) 06/25 00:25
13F：→ coolsprite:(11)Do you want to pass? 如果有這題就好了 06/25 13:48
※ XX9:轉錄至看板 FCUProblems 01/16 21:22