[Introduction To Algorithms] 第九堂: Medians and Order Statistics

這一講的是一群元素中，不用排序找出第幾大的問題。


















一開始講的是同時找最大最小，需要花得比較次數，直覺想是 2n-3 次，但其實只要 floor(3n/2)-2 次即可。9.1 利用狀態機 model了 Min-max problem 的lower bound。 p4~p10.

這個問題是選i小的問題，不用用到 nlog(n)的時間。基本上是學 quicksort 的 pivot 比較大小，不過 pivot 要小心的挑 。

9.3 就是講如何小心的挑，
先五個五個做 insertion sort，再找中位數，這是一個經典的演算法。

[Introduction To Algorithms] 第八堂: Sorting in Linear Time

一般 sort 都是以比較為基礎來討論的，首先討論的是 comparison-based 的演算法 worst case 的下限。


基本的觀念是建立一個 decision-tree model 來對應各種排序演算法。接下來再證明在 worst case 下至少要花Ω(nlgn) 的時間。 p3.~p.4






有了 lower bounds，接下來討論一些演算法是否符合需求， merge sort、Heap sort 符合需求 (quicksort worst case 是ο( n²))。 heap sort 因為 heapify 要跟左右子節點比較，所以會比 merge sort 比較的次數多。


那麼 merge sort 的比較次數是不是最佳的呢?  NO
接下來老師就補充，merge sort 和最佳次數的關西。  p.6 ~ p. 9


注意 p.8 用圖示簡單的示範了 5 個元素時的 "merge insertion sort" 演算法，個元素的插入順序很重要。




接下來討論到不是用比較為基礎的排序，老師一開始討論說 Radix 其實太輕忽了，其實實數、字串等也可以用 Radix 比較， Radix sort 的缺點是占空間，但效率很好。目前 C++ Library 的排序演算法是 IntroSort (quicksort 的改良版)。 




Counting Sort 有個重要概念、Stable，要達到 Stable 那麼輔助陣列要累加。


Radix 有分成 LSD & MSD 、LSD 比較實用，但兩個複雜度相同，用 LSD 時也就需要 stable counting sort。 p.15 利用數學歸納法證明了 LSD Radix 的正確性，基本上就 1...i 位數都排序，那麼 在討論 i+1 位數是否有排序。


分析了一下 LSD Radix Sort 有個很重要的觀念是如何切割....

p.17 有說明如何切割最好: r = lgn 時
     當 r 比 lgn 大或小時效能都不會好。


p.18 說明為什麼Radix會比較快，排序所花的時間主要是"看"的次數。 舉個例子: 考慮 16-bit 的整數有 2¹⁶ 個。Radix 只要看4次，而MergeSort要看16次。


這裡也做了一些假設，只排 unsigned integer，若是要比較 signed integer、string、real 也是可以，但要多做一些步驟。


p. 19 ~20 比較 signed integer (最後一部分相加在排)
p. 21 ~22 比較 string (用了 weighted index)

最後談到的是 Bucket Sort 有點 Hash Table 的概念。 這裡做了些機率分布的假設，假設平均分布。那 expected running time 為 θ(n)。

p.26 做了簡單的 Correctness 證明




p.27 做了大略的分析




p.28 ~ p.33 做了詳細的證明

[Distributed Algorithms] 第三堂: Distributed consensus with link failures

這堂課講的是 Coordinated Attack Problem，
下面是 wiki 的網頁
http://en.wikipedia.org/wiki/Two_Generals'_Problem
說明兩個將軍要攻打第三方，只有兩方合作才能打勝仗，所以需要傳令兵來互通訊息，而傳令兵傳送訊息的過程中有可能被殺 = =
所以這問題基本上是無解。

• Deterministic Version

這問題比較學術的說法叫做 reaching consensus，
這問題要符合 Agreement、Validity、Termination，接下來會用 indistinguish 的方式證明矛盾

• Randomized Version

randomized version 的 agreement 是將犯錯的機率控制在一個範圍內。

兩 event 不知道互相發生甚麼事情，這也是分散式系統的本質。 (consistent global snapshot)

information flow 的概念也很重要!!

[Introduction To Algorithms] 第七堂: QuickSort

 QuickSort 雖然很熟了，但重點是在它的分析。


開始講之前，老師講了 merge sort 的變化 (分成三堆)，第二種是分成三堆後用 priority queue 分析的方式排序，第二種感覺比較聰明的做法，但是複雜度反而變差，而這種情況當分成√n 堆時，priority queue 會複雜度會比較低。


Divide and Conquer 若是 master thm 派不上用場，最後都有大絕招，猜，然後建構式歸納。

經過分析，每一次 partition 的複雜度取決於基準邊的選取，如果每次基準邊都選到最大，那複雜度會到θ(n²) 。若是基準邊都挑很平均，那麼複雜度就是 θ(nlgn)。

這是以結果論來看，我們不能夠很武斷的說，就是這樣啊~ 需要證明，用的方法就是把所有的 case 挑出來 (這種分析方式要好好學)。


值得提的是，若是基準邊是以固定比例來分，那複雜度還是θ(nlgn)，跟一開始講的 merge sort 分三段一樣。

分析時先試著用直覺的觀念，考慮好壞交錯的情況，發現好壞交錯和最好的情況複雜度相同。

接下來分析 randomized 的版本，在實務應用中，為了避免 worst case 發生，會用 randomize 的方式打散。














分析 best case 只要分析Ω就好，因為上界已經是θ(nlgn)了。
而此分析講義沒有列出，在習題 ex.7.4-2 當作練習。 (跟 worst case 分析ο類似)

worst case 的分析就很重要，先猜，再證明。

這個證明利用到微積分的拋物線球極值的觀念。






















再來就是分析 running time 了

有兩種分析方式，這個作者用觀察的方式來證明，這樣證明比較簡單，而習題有傳統分析的方式。

首先觀察 Quicksort 的特性
發現時間在於 Partition 中的比對次數。


所以可以假設 running time 等於，所有比對的次數。random variable 就派上用場了。










p.14 ~ p.17 用 indicator variable 估算出比對次數，這種解法要記!!

老師補充了第二種方式的證明。


p.18 ~ p.23


其中 p.20 頁課本直接用歸納證明，但 full-history recurrence 其實有經典的解法(前次項減後次項)

p.24 列出了一般教科書的解法。


















Quicksort 是個很重要的問題，因此有很多種分析方式，熟悉這些事很重要的!!




















接下來就用，

[Introduction To Algorithms] 第六堂: Heapsort

開始上演算法的應用了，講的是 HeapSort，Heapsort有兩個用途

• 排序
• Priority Queues 的實作

前面屬於資料結構的部分，Heap 的定義、性質、如何 maintain heap (heapify)

接下來討論到 Heapify 的 Running time 

書上直覺地導出上下界。 老師也補充了用 recurrence 的算法。  p.7 注意不能用θ表示。

再來才是分析 worst case(演算法分析要精確)

接下來談到 heap 的建立，也分析了 running time  p.11 ~ p.15

再來就是分析 Heapsort algo....

這裡用到一個 lemma 推導出 n 的 nodes 時，heap 的高度，原理很簡單，自己可以推出來。

這裡老師花了蠻多時間講，列出幾個點

1.  O(0) 的意義
2. 用到之前 rule of sum 等 theorem

我下課問了一下老師，為何可以 remove floor and ceiling = =" 這之前才學過 smooth fun 可以去 floor and ceiling !!

這段老師也強調了一下，畫線的那一段書上沒有說明，老師主要補充， lgn+1到 ∞ 那一段不是"master"。

heap build 分析完後，Heapsort 分析就很簡單了。 p.15~p.17

Priority Queue 不管是 max 還是 min 本質上都一樣。
接下來要分析 Priority Queue 運算的時間。
p.18~p.19

注意 Heap-Increase-Key 這個運算，他其實只要θ(i) 就可以了但是對於整體而言，我們只關心 input size 是 n 時，複雜度是多少，因此θ(n)比較符合需求。












掰!!

Apple Developer 帳號申請成功

這個搞了我超久，網路上說台灣申請大概要一兩個禮拜果然沒錯＝＝
在 Apple Store 買了以後，Apple 會叫你再 Fax 身分證資訊給他
真的是麻煩 ＠＠
紀念一下申請成功！！ 哈哈

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
Dear 公子乖,
Thank you for joining the iOS Developer Program. You now have access to a comprehensive set of development tools and resources to assist you in developing innovative applications.
Please feel free to contact us if you have any general questions or require assistance.
Best regards,

Apple Developer Support

C++ 印出目前函式名稱的方法

#include 
#include 
using namespace std;


int foo(int x)
{
 cout << BOOST_CURRENT_FUNCTION << endl;
 return 0;
}

int main()
{
 cout << BOOST_CURRENT_FUNCTION << endl;
 foo(0);
}

[Introduction To Algorithms] 第五堂: Probablistic Analysis and Randomized Algorithms

首先把第四章的 The Master Method 講完，花了一些時間講 Case 3，

其實只要符合規律下降就可以了，但我們一班還是比較習慣看 asympototic notation，接下來有些 lemma 來證明。 p.47~p.48

Master Theorem 無法涵蓋所有的範圍。有些理論可以涵蓋多一些，不過也無法涵蓋全部。這時候就先猜然後用 substitution 證明。










背景知識的學習，就剩下這第五章了。
"Probability Analysis and Randomized Algorithms"

這張比較屬於機率的部分。老師說數學機率的部分他覺得比較難，反而是代數單純些 XD


這裡兩個重點，

• Probabilistic Analysis(Average case analysis) VS. Randomized Algorithm 的差異
• indicator random variable 的概念

randomize 是強迫機率分布假設成立，所以沒有甚麼 worst case、average case 的概念。

Indicator Random Variable 可以用骰子的例子說明，課本上舉了丟三次骰子出現六的機率，先用一班Random Variable 來做，接下來用 indicator random variable 來做。因為"和的期望值等於期望值的和"所以 indicator random variable 指的是事件 (event) 發不發生 (0 or 1) 這樣子可以簡化計算。

回到 The Hiring Problem，注意的用 probability 和 randomize 分析出來的結果措辭不一樣。p.12 ~ 14

Randomized algorithm 還要考慮到 random bits 的概念 (教科書就沒什麼提到)  p.15~20 提供了比較少的 random bit Permuting arrays 並證明。

要開始真正學 algo 了~~