BST

Basic Binary Search Tree 大致上已經建構完成(basic的原因，不具備balanced的功能XD)，花了很長的時間在寫ctor, dtor, copy ctor, operator=，不過整個class的效率不佳(基本上都以recursion建成，以後可以思考拆掉)，程式碼目前只有330行，算很小，就算在insert node的這個功能上加入balanced，我相信也不會大到那裡去~

---
AVL Tree建完回頭建link list..XD

沒時間

第一次覺得沒時間可以用，利用自身的筆電優勢，大概把BinarySearchTree寫完了，327行，尚未整理，一整個很有dirty work的感覺，晚上要當工院盃場務，回到宿舍已無體力繼續，印出來之後，完成一個AVL Tree or RB Tree指日可待

事實上沒時間最可惜的是，要寫"資料結構與演算法02" 一直找不到時間XD

---
沒時間(Sun yanzi, Start自選輯)

最近

發現要念書時間不夠用，對於利用電腦整理重點更有心得，但是總覺得有一種被制約的感覺。有人問我"一把鍵盤改變全世界"(msn狀態)是什麼意思，我很高興的說的，因為資工人就利用鍵盤所輸入的文字在改變世界，但是轉眼一想，我們不就受限於簡單的鍵盤上嘍，但是相較而言，用簡單的鍵盤創造無限可能，這或許就跟用鋼琴，就幾十個黑鍵白鍵，譜出全世界最美麗的樂章，有一樣的感覺

---
但是我想要成為資工人，而不能成為鋼琴家XD

資料結構與演算法(下)01 by 隨機客

非正題
當初一時高興之下決定每個禮拜前往台大旁聽的決定，現在已經是第三個禮拜，想想也是覺得複雜了些(早上七點起來+來回60km機車)，但是現在想想，上這堂課是蠻值得的，一直都很想為這堂課寫一些blog note，但是，呃，苦無時間，原因很多，所以且戰且走吧:)，這還是我蠻常說的一句話。

---

2007/02/26 資料結構與演算法(下) 呂學一 投影片

這堂課主要講述的是隨機演算法(yen3註：跟隨機客有異曲同工之妙XD)，主要著重於兩個重點

• Randomized quick sort

sorting 乃萬古常青的演算法問題，quick sort更是在1960年代時被提出，在投影片的一開始複習quick sort的特性(標準的divide and conquer)與algorithm的運作方式(yen3補註：這中間有非常的漂亮動畫說明，考據指出，只用了powerpoint的內建功能)。

quick sort的時間最佳為O(n logn)，最糟為O(n^2)，這中間的效率在於pivot的選取，重點來了，怎麼選？當然，一般化的想法，選中位數，中位數的選取幾乎可以獨立成為一個演算法的課題(在簡報中提到許多paper都在選中位數，而這篇關鍵性的paper author幾乎都得了Turing Award XD)，證明出選中位數是linear time，於是隨機客在這邊丟出一個問題，是否在做quick sort的選取pivot時，一定要用到如此複雜的選中位數呢？

當然有其他解法，Randomized 選取pivot是一個解，隨機演算法本身的撰寫無難度可言，難的是，如何得知效率(time and space complexity)？亂數是否真的夠亂(yen3註：C library 下的rand() 是個眾所皆知的假隨機亂數)，經過證明，經過隨機選取的亂數當pivot，有一半的機率會達到最佳效率，也可以證明出O(n logn) 是成立的(隨機客將中間證明省略)


• Randomized maximum cut

掃黑的藝術(yen3註：XD)
給一個圖G，找出從A node 至B node能夠將最多edge切掉，但是也有一個問題，each node no more than 3 neighbors. 問題規定如題，求出最大切割的time complexity 也是O(c^n) c為constant ，n 為節點數...如果n 非常大，此題接近無解

Approximation Algorithms(近似演算法)現身啦，噹噹噹(近似演算法的哲學：放下對完全的堅持，往往就可以找到新的出路。知所進退，則近道矣。)在此問題上，使用隨機演算法選取node進行切割，則有機率是最佳解的一半(但是時間就是生出亂數的時間XD)，隨機近似演算法就變成一個很好的解法(yen3註：後面看不太懂，要再念書。)

對隨機演算法不要有一個誤解，無論input data為何，都不影響其效率，也就是說，對於best case和wroest case，隨機演算法皆保有同一個效率，並不因input改變，因此，沒有必要對所有可能的input 算出每一個時間複雜度，若是這樣子，此隨機演算法不成立。當然，隨機演算法也有其罩門，這世界上是否真的有亂數產生器？(Pseudo-random generator exists if and only if one-way function exists.)到目前為止沒有人知道有沒有，因為事實上證明出現有的亂數產生器都是有跡可循的，若是用C library 上的rand() ，照著一定公式所產生的亂數，也有演算法可以很大的機率猜出下一個會出現的數字是什麼(以bit的觀點)。在這也提到了P vs NP problem (列入Hilbert's 23 open questions)。

亂數沒有那麼好產生，也早就有人證明出依照現在所存的方法，所產生的亂數都是假隨機亂數(也就是有跡可循的亂數)，要能夠產生真正夠亂的亂數依舊是一個難題，世界上沒有一個公平的硬幣，所以就有了一個題外話的數學小證明，號稱20世紀最聰明的人von Neumann，提出了丟硬幣的方法(見投影片p.38)。用了簡單的機率，即得證。

---

有錯誤請盡量指正，謝謝:)

---
寫的好長好亂，下次我是不是該改成wiki..XD