2018q1 Homework3 (list)
======================
###### tags: `shaimejump520`
contributed by <`shaimejump520`>

作業說明連結 [D05: list
](https://hackmd.io/P7Bxz6AZQFasijJlYVwHQA?view)

## 預期目標

* 嘗試研讀大型軟體專案
* 學習 Linux 核心原始程式碼的資料結構
* 資料封裝和 C 語言程式設計技巧
* 複習機率統計，及早脫離鄉民口中的「文組^TM^」
* 兼顧理論和實務

## 作業要求

* 回答上述「生日悖論」、「Linux 風格的 linked list」，和「針對 linked list 的排序演算法」裡頭「自我檢查清單」的所有問題，需要附上對應的參考資料和必要的程式碼
* 在 GitHub 上 fork [linux-list](https://github.com/sysprog21/linux-list)，參考 `examples/insert-sort.c` 和 `examples/quick-sort.c` 的實作方式，實作 merge sort，並且在 `tests/` 目錄提供新的 unit test
* 研讀「你所不知道的 C 語言」的 [函式呼叫篇](https://hackmd.io/s/SJ6hRj-zg) 和 [技巧篇](https://hackmd.io/s/HyIdoLnjl) 探討 [linux-list](https://github.com/sysprog21/linux-list) 的 `include/list.h` 的實作考量 (在上述檢查清單已提及部分)
* 承上，實作測試程式，批次建立包含若干大小的 linked list，隨機放入數值為介於 1 到 366 之間 (包含) 的節點 (代表 [day number](https://www.epochconverter.com/daynumbers)) ，至少應該涵蓋 10^1^, 10^2^, 10^3^, ... 10^6^ 等數量，透過前述的 insert, quick, merge sort 進行排序，分析執行時間並解讀其行為
* 需要有檢驗的程式碼
* 承上，設計 deduplication 程式，將上述輸入中的數值挑出重複的節點並與刪除，透過統計分析，解讀執行時間分佈，以及探討 [data deduplication](https://en.wikipedia.org/wiki/Data_deduplication) 的效益
* 比照生日悖論，提出統計模型和數學分析
* 參照 [Remove duplicates from a sorted linked list](https://www.geeksforgeeks.org/remove-duplicates-from-a-sorted-linked-list/)
* 延續 [A Comparative Study Of Linked List Sorting Algorithms](https://www.researchgate.net/publication/2434273_A_Comparative_Study_Of_Linked_List_Sorting_Algorithms) 的方式，量化分析上述步驟，並且提出效能改善機制
* 將你的觀察、上述要求的解說、應用場合探討，以及各式效能改善過程，善用 gnuplot 製圖，紀錄於「[作業區](https://hackmd.io/s/S1iCyyziG)」

## 生日悖論

### 如何透過近似的運算式，估算上述機率計算呢？附上有效的 LaTeX 算式
* 要解決這個問題，首先要先學會 [LaTeX](https://zh.wikipedia.org/zh-tw/LaTeX) 語法，我第一次作業偷懶沒有先學抱歉QQ，終於碰到了阿...，先看個 [LaTeX 語法與示範](https://hackmd.io/s/B1RwlM85Z)壓壓驚 :satisfied:
* 在排版時覺得原本使用的`\dfrac`和`\frac`放在指數時看起來十分不理想，基於強迫症就去查到了`\tfrac`這種格式，可以讓分數放在指數時大小適中又美觀XD

$by\ Taylor\ series\ :\
e^x\ =\ 1\ +\ x\ +\ \dfrac{x^2}{2!}\ +\ ...\\
with\ small\ x\ ,\
we\ can\ assume\ that\ x<<1\ ,\ thus\ :\
e^x\ \approx\ 1\ +\ x\\
and\ we\ get\ :\
e^{-\tfrac{1}{365}}\ \approx\ 1\ -\ \dfrac{1}{365}\\
P(n)\ = \ 1\ -\ \bar{P}(n)\\
\begin{split}
\bar{P}(n)\ &=\ \dfrac{364}{365}\ \times\ \dfrac{363}{365}\ \times\ ...\ \times\ \dfrac{365-(n-1)}{365}\\
&=\ (1-\dfrac{1}{365})\ \times\ (1-\dfrac{2}{365})\ \times\ ...\ \times\ (1-\dfrac{n-1}{365})\\
&\approx\ e^{-\tfrac{1}{365}}\ \times\ e^{-\tfrac{2}{365}}\ \times\ ...\ \times\ e^{-\tfrac{n-1}{365}}\\
&=\ e^{-\tfrac{1+2+...+(n-1)}{365}}\\
&=\ e^{-\tfrac{n(n-1)/2}{365}}\\
&=\ e^{-\tfrac{n(n-1)}{730}}\\
\end{split}\\
P(n)\ =\ 1\ -\ \bar{P}(n)\
\approx\ 1\ -\ e^{-\tfrac{n(n-1)}{730}}\
\approx\ 1\ -\ e^{-\tfrac{n^2}{730}}$

### [Birthday problem](https://en.wikipedia.org/wiki/Birthday_problem) 對資訊安全的影響在哪些層面？
* 先研讀 [bitrhday attack](https://en.wikipedia.org/wiki/Birthday_attack)，得知這是一種基於 birthday problem 理論產生的 brute-force attack，由於對於資料做加密傳輸的方式，多數是使用 hash function 產生加密過後的資料做傳輸，而 birthday problem 的特性，只要嘗試 $2^{n/2}$ 組輸入，便有很高的機率能早到與原明文相同的 hash value，從而能夠接收者不知情的其況下竄改訊息、達到攻擊的目的
>參考 [LinYunWen的共筆](https://hackmd.io/s/S1aszm0sM) 中提供的 [reference:雜湊](http://www.tsnien.idv.tw/Security_WebBook/%E7%AC%AC%E5%9B%9B%E7%AB%A0%20%E9%9B%9C%E6%B9%8A%E8%88%87%E4%BA%82%E6%95%B8%E6%BC%94%E7%AE%97%E6%B3%95.html) 蠻易懂的
>但我的疑問是，為何一個路人攔截訊息，能夠確定你加密的 hash function 是哪一個而能夠以此完成攻擊呢？
* 另一種問題 -- [合約詐欺](http://www.tsnien.idv.tw/Security_WebBook/%E7%AC%AC%E5%9B%9B%E7%AB%A0%20%E9%9B%9C%E6%B9%8A%E8%88%87%E4%BA%82%E6%95%B8%E6%BC%94%E7%AE%97%E6%B3%95.html)，這是在知道 hash function 的情況下，可以找到與一份100萬合約具有相同 hash value 的1000萬合約，誘騙對方簽署

* 所以常見的解決方法是加長 hash value 的 bits 數，如此一來增加了找到相同 hash value 訊息的難度，從而化解 birthday attack 然而相對的，加長資料長度後必定會帶來運算更加複雜、效率也因此更差

### 像是 [Random Number Generator](http://stattrek.com/statistics/random-number-generator.aspx) 這樣的產生器，是否能產生「夠亂」的亂數呢？
*

## 參考資料
* [LaTeX 語法與示範](https://hackmd.io/s/B1RwlM85Z)