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

[XX9 ( 佛曰: ....)]

※ [本文轉錄自 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:八百銀= =     第一大題是 是非題耶!
推 tang76430:821銀 這篇真賺XD
推 Courake:NCDP T_T
推 Jimmy0398:DP T_T
推 loveflames:因為PαNP，所以將P代換成CDP，即為CDPαNCDP
推 dacapo:ncdp T_T 怎不是SATY ><
→ loveflames:因為SATY的證明太無聊了?
推 abibas:全是習題  科科
→ final01:老師專考習題已經不是一天兩天的事了
推 JohnRoyer:是非題  T_T
推 loveflames:(11)Do you want to pass?
推 pppsa:     (11)Do you want to pass? (60%)
→ coolsprite:(11)Do you want to pass?   如果有這題就好了
--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.132.214.27