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

[Distributed Algorithms] 第二堂: Mutual exclusion (3)

一開始先證明 Burnme 演算法，"存在"這個觀念就很重要了 = =
不過剛開始超想睡覺，一度有昏睡過去，就沒有聽清楚老師在講什麼。


接下來講的是 Bakery Algorithm

以前 OS 課本有，好像有點印象 = =
觀念就是拿號碼牌，但因為 muti-process 可能有兩個拿到同樣號碼的號碼牌，所以需要用 choosing 擋住。
老師舉了一個例子，把 choosing 拿掉時，兩個 process 進入 CS 的例子。


這個 algorithm 假設，號碼牌是 unbounded，有人好像花很多時間用改善到 bounded 但....
















再來介紹，Lower bound on the number of register
說明為什麼 n 個 process 要有 n 個 shared variable 才能夠保證同步。(有用到鴿籠原理)
這證明用到很多 lemma ，indistinguishable、idle 的定義。

若是硬體有支援， compare and swap 這樣的 test-and-set 指令的話，那同步演算法就很好設計了，
Read modify write shared variable (但是硬體昂貴) 證明 Bounded by pass 

• 只要 1 個 register 就好 (跟 shared memory model不同)
• 但是 number of bits 要夠用 

嘆!!

RMI in C++

之前設計 Client/Server 程式時，都是用 message 來當作 protocol。
例如:


#define msg_open  1
#define msg_close 2
...


Client 將 message 透過 socket 傳給 Server，Server 再對此 message 做解譯動作。
這種設計方式簡單，但常常要處理很 routine 的工作，自己要處理封包代表的意義。(也就是要解釋 buffer size 的大小問題)


比較好的處理方式是用 remote procedure call 的方式，將複雜的底層處理過程包裝起來，client 需要 server 服務時，只要利用類似 function call 的方式就可以達成目的。
通常這種做法像是 COBRA 通常都要用 IDL 的方式，寫一個語言無關的介面，然後再利用程式碼產生器產生出目的語言 (C++、Java...etc)


下面這篇文章，就不用額外的程式碼產生器，而是利用 C++ preprocessor 來產生 C++ code，也就是只需要 C++ compiler 就搞定啦。
http://www.codeproject.com/KB/threads/Rcf_Ipc_For_Cpp.aspx

不過要注意的是:
1. 需要 C++ boost library  (用到 Asio)
2. 我用 VS2010 編譯時，發生  error C3861: '_cpp_max': identifier not found 
     解法再此 link 
     https://connect.microsoft.com/VisualStudio/feedback/details/553420/std-cpp-max-and-std-cpp-min-not-available-in-visual-c-2010
      
3.  附上作者寫的 User Guide http://deltavsoft.com/w/RcfUserGuide/1.3/

    有興趣可以玩玩看!! Have Fun!!