[理工] [資結]-台大97-資工軟體設計核對

[taitin (小南)]

1.(1) d,6
  (2) g,6
  (3) h,5
  (4) h,5
  (5) b,2

2.
      0  1  2  3  4  5  6  7  8  9  10
   a 22 88        4  15 28 17 59 31 10

   b 22    59 17  4  15 28 88    31 10

3.


          1  2  3  4  5  6  7  8  9
 taskid   2  7  1   3  5 8   0 12  6

      penalty=w4+w10+w9+w11=23


4.

 a. T(n)=7T(n/2)+Θ(n)
    by master theorem
     T(n)=Θ(n^lg7)

 b.T(n)=McT(n/c)+Θ(n^2)
    T(n)=Θ(n^log Mc)
                 c

 c.from B
   T(n)=Θ(n^log M3)
                3

    log M3       lg7
   n   3    <  n

     lgM3
     ── < lg7
     lg3

     M3<2^(lg7lg3)=α

           α=2^(lg7lg3)

5. use divde and conquer
   partition the problem in to 2 small problem

  T(n)=2T(n/2)+Θ(n)
      =Θ(nlgn)

 1.將座標依X座標排序，另外儲存Y座標排序資訊
 2.找到X座標中位數M，將數列分成兩堆L,R
 3.遞回找出L 跟R的最小距離，取較小者為d
 4.檢查X座標在 M-d，到M+d之間的座標P
 5.對每個P的Y座標yp
   找出y坐標在yp+d跟yp-d之間的點Q，令d'=PQ
 6.若d'<d d<- d'
 7.return d

step 1 O(nlogn) step2~7 T(n)=2T(n/2)+n
                            =Θ(nlogn)

                      so nearest pair prob. 可在O(nlogn)內找出


 b. a.已知farthest pair 為一convex hull 中的兩個頂點。
      若已知一convex hull，則可在O(n)時間內找出farthest pair
    b.找convex hull
      1.找出一y坐標最小中，x坐標也最小的點p
      2.求各點與p0所成向量依角度大小排序
      3.令s為一空stack，push p0 p1 p2
      4.for i=3~n
          while  Pia 到 Pib 不為left turn
                do pop(s)
         end while
          push(Pi,s)
        end for

     a.O(n)
     b. 1 O(n)
        2.O(nlogn)
        3.O(1)
        4.O(n)   pop個數不超過n
     因此得證  farthest pair 可在O(nlogn)時間被找到

6.
  1.任挑一邊，將該邊的兩個點所連結的所有邊消除
  2.重複一直到邊E為空。

step1. O(1) step.2 (M)  因此可在O(n+m)時間內完成

approximation
  令C*為此問題最佳解，A為每次任選邊的集合
  因為C*至少包含A中每個邊所cover的點
  因此 |C*|>= |A|
  又此漸進法每次選兩個點進入C，|C|=2|A|
  因此可得知|C|=2|A| 因此|C|<=2|C*|
  所以approximation=2


7. 好像是用suffix之類的方法解...
   可是我不會...請高手解之~~


歡迎來信推文回文討論





--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.44.247.251
→ taitin:剩下晚點再打
推 polomoss:binary search worst case為何不是O(n)
每次切中間，worstcase就是O(logn) 畫一個decision tree
第一個中點做根，然後左半的中點做左子，右半中點做右子，遞回
可畫出 balance 的 BST ，樹高最高不超過logn
→ polomoss:第三題可以教一下嗎?
原則上greedy的做，每次選擇delayline最小的，若是遇到相同的，
則選擇penalty較小的，然後把較大的送到stack。
最後再把stack倒出來就是答案。
不過其實會有問題是時間七會是空的，不過剛好8 9沒有collsion，所以不影響時間順序
題目只問schedulle沒問algo，所以我這樣解XD
推 polomoss:好強~這張我會寫的超少..
※ 編輯: taitin          來自: 61.230.239.3         (02/02 22:54)
※ 編輯: taitin          來自: 61.230.239.3         (02/02 23:23)
※ 編輯: taitin          來自: 61.230.239.3         (02/02 23:34)
推 polomoss:原PO有K原文書嗎? 我演算法部分好弱...
→ taitin:你說 i to A嗎？
→ taitin:我資結念原文，演算法introduction to algo原文做輔助
推 RdMax:強者 推一個