[理工] [資演] 103-台大電機-丙 討論

[ken52011219 (呱)]

大家好，因為看板上 103 台大電機丙 - 資演 好像沒甚麼人在討論
因此想來跟大家討論一下各題想法。

1.(20%)

http://imgur.com/a/0RmQ3


        依題目所提示可以得出以下重點：

                1.該 Data Structrue 共兩種 function
                   (1) : insert()
                   (2) : median() // 不用刪除

                2.目前總共有 n 個 element in the data structure

                3.對於 n 為奇數而言， median() = (n+1) / 2
                         為偶數而言， median() =   n   / 2

                4.( n/2 + 1 ) th 是 最小元素

問題【1】，請敘述該 Data Structure

        對於該Data Structure而言，分成兩部分討論

        1. Insertion()中會包含著判定是否為最小值，若是則會被 insert (n/2+1)th
           反之則會 將原本的值將插入 n+1 th、，原本minmum swap to (n/2 + 1)th

        2. median() 則為上述 重點3 的判別式


問題【2】， n calls insertion(x) + 亂數calls O(n)次 median() 的時間複雜度

        Insertion time complexity 共 n calls 為 O(1*n + x*n)

             x  if 為 unsort array structure , search 為 O(n)
                if 為 unsort link list       . search 為 O(1)
                if 為 binary search                   為 O(log n)

                if code 有 動態紀錄該式 n 的位子 為 O(1)

        median time complexity 為 O(1) 共 n call , 為 O( 1 * n )

        Ans O( 1*n + x*n +  1*n ) = O( xn )


推 FRAXIS: 第一題應該是用 augmented balanbed BST
2. (25%)

http://imgur.com/a/Fe9lV

 (5%)問題【1】

        題目要將Double hashing 呈現像 linear hashing

        h(k) = (h_1(k) + ih_2(k)) % m
        =>   = (h_1(k) + i * 1 )  % m

        令 h_2(k) = 1 即可

 (5%)問題【2】

        No, uniform 的意義為 每個probe sequence 機率都是一樣的，若純談論
        double hashing , 則為 yes ，但上題已經將 double hashing 改為 linear
        hashing 的效能了。

(15%)問題【3】



        Pr{X ≧ i } = n/m * (n-1)/(m-1) * ... * (n-i+2) / (m-i+2)

                    ≦ (n/m)^(i-1)

                    = α^(i-1)
               ∞                m                ∞
        E[X] = Σ Pr {X ≧ i} = Σ Pr {X ≧ i} +  Σ Pr {X ≧ i}
              i =1              i=1               i>m
                ∞
             ≦ Σ α^(i-1) + 0
                i=1
               ∞
             = Σ α^(i)   =  1/ (1-α)


        本題小弟已放棄解讀，其證明為 楓葉本 11.4 274-275

        un-succeful look up = 1/ (1-α)
           succeful look up = (1/α)ln(1/ (1-α))


3.(20%)

http://imgur.com/a/uLycl

推 FRAXIS: 第三題利用 power diagram 可以做到 O(n lg n)
→ FRAXIS: https://en.wikipedia.org/wiki/Power_diagram

4.(35%)

http://imgur.com/a/kyxuN

 (5%)問題【a】

        原文書-312 題目

         最高比例為 2 ( root 為 1 Black , interal Red node 為 2 )
         最低比例為 0

 (5%)問題【b】

        楓葉本-333

        AVL tree of height h has at least F_h node         O
          0 1 2 3 4 5  6                                 ╱  ╲
        F 1 1 2 3 5 8 13                                O       O
                                                      ╱ ╲   ╱ ╲
        AVL 高度最多為 5                            O      O O     O
                                                  ╱ ╲  ╱         ╲
                                                 O     OO             O
                                               ╱
                                              O
(5%)問題【c】

        楓葉本-333

        AVL-Insert run on an n-node AVL take O(lgn) times and O(1)次 rotation

(10%)問題【d】

        楓葉本-343
        14 單元 - Augmenting data structure

        O(log n)

(10%)問題【e】

        目前我想到的是以binary search  AVL ，可是看起來應該沒有那麼簡單

→ FRAXIS: 4 (e) 是 augmented AVL tree 的應用
        O(log n)


--
　　有一個香錦囊，是從一個神話般的守軍的血屍頂上剝下的。那一次我們部隊遭受從未
有過的頑強抵抗，我們犧牲了三個艦隊，一個裝甲師和無以數計小組推進的敢死排，才摧
毀了那處隘口的碉堡。但是竟然發現，使我們遭受如此慘烈傷亡的守軍，總數只有一人。
　　士兵們起鬨地在他胸前發現這枚香袋，大家都相信這是一枚具有神奇力量的護身符。
我們把他的頭顱砍斷，取下香袋，剝開，
　　裡面一張被血浸紅的宣紙竟用漢字娟娟秀秀四個整齊的楷書寫著－「盼君早歸。」

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.131.84.210
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484291998.A.088.html
→ ken52011219: 4(C) 看有沒有人有正確畫法，雖然答案不唯一
→ ken52011219: 但根據楓葉本 F_h = node 數 , 這樣 root 視為h= 0
→ ken52011219: 而我當初畫的 (右圖) 將root 視為1
→ ken52011219: 咦 F_1 = 1 好像也可以 這樣我答案就沒問題了
※ 編輯: ken52011219 (140.131.84.210), 01/13/2017 15:36:18
推 Transfat: 2(2)我有點想問為什麼Double hashing會是最接近uniform
→ Transfat: 的方法啊
        楓葉本-275
        The performance of double hashing appears to be very close to the
          performance of the "ideal" scheme of uniform hashing

→ Transfat: 第三題我想到一方法，就是把每個點的中心點投影到x軸和y
→ Transfat: 軸上，我們先看左邊那四個circle,右邊重疊那五個先不要
→ Transfat: 看，因為我們知道circle的center和radius,所以我們先投
→ Transfat: 到x軸上，接下來就拿radius去比，如果有重疊到，我們就
→ Transfat: 先記錄著，例如從左到右circle是c1,c2,c3,c4,看了一下發
※ 編輯: ken52011219 (140.131.84.210), 01/13/2017 16:26:28
→ Transfat: 現c1,c2,c3在x軸上回重疊到，接下來就去比y（把center投
→ Transfat: 影到y軸，然後各circle畫radius,發現在c1,c2,c3這三個
→ Transfat: 之中，只有c2,c3重疊到，這就可以肯定c2,c3一定是一個
→ Transfat: closed region,且c1被排除在外，也就是說c1也是一個clos
→ Transfat: d region,c4因為都沒有和別人重疊，他也是一個closed re
→ Transfat: gion. 我這邊先舉例四個circle,右邊那五個考慮進來也可
→ Transfat: 以用同樣方式去看
推 Transfat: http://imgur.com/a/P0XlJ
推 Transfat: 我上面那圖好像沒畫得很標準，c3要比c1更高
→ Transfat: http://imgur.com/a/RXRLw
→ Transfat: 所以c3和c1投影到y軸上的時候才不會重疊
→ Transfat: 畫得好醜，不知道看不看得懂
        幫排版:

        第三題我想到一方法，就是把每個點的中心點投影到x軸和y軸上

        我們先看左邊那四個circle,右邊重疊那五個先不要看，因為我們知道circle
        的center和radius,所以我們先投影到x軸上。

        接下來就拿radius去比，如果有重疊到，我們就先記錄著。
        例如從左到右circle是c1,c2,c3,c4,看了一下發現c1,c2,c3在x軸上回重疊到

        接下來就去比y（把center投影到y軸)，然後各circle畫radius發現在c1,c2,c3
        這三個之中，只有c2,c3重疊到，這就可以肯定c2,c3一定是一個closed region

        且1被排除在外，也就是說c1也是一個closgion.

        我這邊先舉例四個circle,右邊那五個考慮進來也可以用同樣方式去看

→ ken52011219: XDD.. 我個人幾何之前都放推 最近才會加減補起來
→ ken52011219: 所以看有沒有人有研究的來幫忙討論一下Q_Q
推 Transfat: 我靈感來源是closet pair,這種東西真的只能看老天有沒
→ Transfat: 有突然靈光乍現了QQ
推 Transfat: http://imgur.com/a/6OBYJ 好像沒貼到
※ 編輯: ken52011219 (140.131.84.210), 01/13/2017 17:01:14
推 yupog2003: 我第三題的想法是有九個circle，兩兩測試有沒有重疊
→ yupog2003: 測試的方法是(x1-x2)^2+(y1-y2)^2 < (r1+r2)^2是否成立
→ yupog2003: 如果有重疊就把他們union起來，沒重疊就當disjoint set
→ yupog2003: 最後看看有幾個disjoint set
→ yupog2003: 這樣可以變成O(n^2)，也沒用到根號或除，應該可以
推 FRAXIS: 第一題應該是用 augmented balanbed BST
       先感謝F大回答<(_ _)> 想問一下這題使用的 Data structure 有一定的限制嗎@@?
       怕我上考場一時失神就忘記了

→ FRAXIS: 或是兩個 heap 可以達到 插入 和 median 都是 O(lg n)
→ FRAXIS: 4 (e) 是 augmented AVL tree 的應用
        我再研究看看

推 FRAXIS: 第三題利用 power diagram 可以做到 O(n lg n)
→ FRAXIS: https://en.wikipedia.org/wiki/Power_diagram
        這應該是正解了 感謝!
※ 編輯: ken52011219 (36.224.23.104), 01/14/2017 16:42:35