推 jack2749:八百銀= = 第一大題是 是非題耶! 06/24 17:02
推 tang76430:821銀 這篇真賺XD 06/24 17:05
推 Courake:NCDP T_T 06/24 17:09
本學期最後一張考卷....( ′-`)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