[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 了~~