Algorithm hw#13

Prob. 25-1
Transitive Closure: 參考 http://acm.nudt.edu.cn/~twcourse/TransitiveClosure.html
簡言之就是走得到的所有連結, 所構成的一張圖

a. 當加進一條邊時,要怎樣更新Transitive Closure的boolean matrix, 在O(V^2)時間內
b. 舉例說明當加入一條邊到一張圖裡時, 不管用什麼演算法, update Transitive Closure的時間下限是V^2
c. 針對更新Transitive Closure給一個有效的演算法, 對一系列的n個insertion來說, 證明時間可以維持在O(V^3)

Prob. 31-1
大部分的電腦實施減法操作來驗證一個二進位整數是奇數或偶數, 且比"算餘數"的方法還快了一倍(時間減半)
此問題牽涉到binary gcd algorithm, 避免了在Euclid’s algorithm裡的餘數計算
a. 證明當a,b都是偶數時, (a,b)的gcd是(a/2,b/2) gcd的兩倍
b. 證明當a是奇數,b是偶數時, (a,b)的gcd是(a,b/2) 的gcd
c. 證明當a,b都是奇數時, (a,b)的gcd是((a-b)/2,b) 的gcd
d. 設計一個有效的binary gcd algorithm, 滿足a>=b, O(lg a)