2018q1 Homework3 (list)
======
contributed by < `chasingfar` >

自我檢查事項
------

### 生日悖論
#### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
$1 - \dfrac{1}{e^\frac{n^2}{2N}}$
#### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？
N 位長度的 hash table 可能發生碰撞測試次數不是$2^N$次而是只有$2^\frac{N}{2}$次
#### 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？
此網站並未提供亂數產生器算法，所以很難從數學角度解釋。
簡單的統計一下前1000個0~9的出現次數(seed=0)
可看出極不均勻，不知是不是樣本過少的關係，但它上限就是1000個。

在實務中需要真亂數時可以考慮[random.org](https://random.org)提供的服務，
若有可控的偽亂數需求可以考慮 c++11 提供的 `<random>` 函數庫，或者 intel 提供的 MKL 函數庫。

### Linux 風格的 linked list
#### 為何 Linux 採用 macro 來實作 linked list？一般的 function call 有何成本？
function call 需要對 stack `push` 及 `pop` 最少也需要 `jmp` 與 `ret` ，會對 stack 造成負擔以及產生多餘的指令。
用 macro 來實作的話就不會有多餘的指令及額外的 stack 消耗，但會有編譯後程式體積增加及難以維護的缺點
#### Linux 應用 linked list 在哪些場合？舉三個案例並附上對應程式碼，需要解說，以及揣摩對應的考量
#### GNU extension 的 [typeof](https://gcc.gnu.org/onlinedocs/gcc/Typeof.html) 有何作用？在程式碼中扮演什麼角色？
#### 解釋以下巨集的原理

#define container_of(ptr, type, member)                            \
    __extension__({                                                \
        const __typeof__(((type *) 0)->member) *__pmember = (ptr); \
        (type *) ((char *) __pmember - offsetof(type, member));    \
    })

#### 除了你熟悉的 add 和 delete 操作，list.h 還定義一系列操作，為什麼呢？這些有什麼益處？
#### LIST_POISONING 這樣的設計有何意義？
#### linked list 採用環狀是基於哪些考量？
#### `list_for_each_safe` 和 `list_for_each` 的差異在哪？“safe” 在執行時期的影響為何？
#### for_each 風格的開發方式對程式開發者的影響為何？
#### 程式註解裡頭大量存在 `@` 符號，這有何意義？你能否應用在後續的程式開發呢？
#### `tests/` 目錄底下的 unit test 的作用為何？就軟體工程來說的精神為何？
#### `tests/` 目錄的 unit test 可如何持續精進和改善呢？

### 針對 linked list 的排序演算法
#### 對 linked list 進行排序的應用場合為何？
#### 考慮到 linked list 在某些場合幾乎都是幾乎排序完成，這樣貿然套用 quick sort 會有什麼問題？如何確保在平均和最差的時間複雜度呢？
#### 能否找出 Linux 核心原始程式碼裡頭，對 linked list 排序的案例？
#### 透過 [skiplist](https://en.wikipedia.org/wiki/Skip_list) 這樣的變形，能否加速排序？
#### 研讀 [How to find the kth largest element in an unsorted array of length n in O(n)?](https://stackoverflow.com/questions/251781/how-to-find-the-kth-largest-element-in-an-unsorted-array-of-length-n-in-on)，比照上方連結，是否能設計出針對 linked list 有效找出第 k 大 (或小) 元素的演算法？
#### [linux-list](https://github.com/sysprog21/linux-list) 裡頭 `examples` 裡頭有兩種排序實作 （insertion 和 quick sort)，請簡述其原理

實作 merge sort
------