Select k-th element in linear time

上週日提起 linear time 的 selection algorithm, 發現 wiki 寫得很詳細
原理很簡單, 只是原本 partial quick sort 選 pivot 的那部份改進

假設 PICK(A, k) = k-th element in A[]
原本是 random 選一個 pivot, 現在則是把 array A 分成 |A|/5 組
每組找出 5 個數中的 median, 叫作 B[0], B[1], .. B[|A|/5-1]

然後 call PICK(B, |B|/2) recursive 找出 B[] 真正的 median 作為 pivot
由於每個 B[i] 都至少大於/等於 3 個 element, 而 pivot 又大於/等於 |A|/10 個 B[] 中的數
所以 pivot 至少大於/等於(& 小於/等於) A 中 3/10 的 element, 即是 partition 後的 size 最大為原本的 7/10
然後便像原本 partial quick sort 做下去

得 T(N) = T(N/5) + T(7N/10) + O(N)
⇒ T(N) = c * N * (1 + 9/10 + 81/100 + ...) ≤ 10 * c * N = O(N)

一開始覺得 '5' 很神奇, 發現其實不一定要是 5
假設不是分為 |A|/5 組而是 |A|/k 組 (k = odd integer)
便會變成

T(N) = T(N/k) + T(N * (1 - (k+1)/4k)) + O(N)

T(N) 是 linear 的條件是 1/k + (1 - (k+1)/4k) < 1 即 k > 3
估計由於 5 是最小的 odd integer solution 所以是 5 吧 [利申: 我估的]

Sem 4 4/13: FORTRAN & COBOL

原來沒有功課的四個星期過得真快
318 Asg 1 是要模擬一 object 在某房間內的 movement, 而且有一堆會 board



做法只是每次找最接近的 board, 計算 segment intersection
比較莫明奇妙的是 output
spec 要求把 path 上每一點都 truncate 至整數點, 再把整個 bitmap print 出來



很明顯 precision 會很有影響, 尤其是條 path pass through 交點時
雖然可以處理, 但是這份功課的重點已經開始偏離 programming languages 本身

FORTRAN

特別限制: 只能使用 if, goto, 不能使用 loop 等
據說是為了體驗 'the old times', 不過用 if goto 也很輕鬆
本身不支援 recursion, 所以整個 FORTRAN 感覺是線性的

比較麻煩的是 1)沒有 struct 2) procedure 不能 access global variable
1) 加上 FORTRAN 是一行一句使得 code 很難看
2) 由於要把所有相關的 variable pass 入去, 又是把 function 寫得很長

總括來說還是寫得很順手



COBOL

B stands for business, 好像是很古老的商業用 language
很明顯用來寫 geom 已經很莫明奇妙, 如果想體驗的話應該寫該種 language 應該寫的 program
COBOL 除了不適合用來計數外, 本身己經有一大堆缺憾

1) Define variable 竟然要一行一個




2) 接近英文的語法
眾多缺點中最差的一個, 例子:
ADD X TO Y GIVING Z
MOVE 1 TO X
據說設計的原意是 "讓不懂電腦的人也可看懂程序", 真是莫明奇妙
不懂電腦的人根本沒必要看懂, 懂電腦的看得很辛苦
幸好後來發現有 COMPUTE, 可以正常地打 arithmetic expression..

3) 莫明奇妙的限制
例如有 PERFORM N TIMES.. END-PERFORM (幸好有 loop 用)
但是卻不能在 N TIMES 中打 expression, 例如 PERFORM N-1 TIMES 是不行的

種種問題令段 program 寫得冗長又難看
雖然古老的 language 有很多不足很正常, 但是最莫明奇妙是要用來寫 geom 和搞 output format, precision 等, 令我對 318 的印象--

VC 與 AOC

前幾天看到 matrix67 的 blog, 覺得很有趣, 便一直在想除了還有沒有其它做法
由於沒有打 SC (StarCraft), 不過應該和 AOC 差不多 (其實這些即時戰略遊戲應該都不大差別)
即是說, 給出一個 AOC 的局況, 判斷某一方是否能勝出

文中用的 NPC 問題是 PLANAR GRAPHS HAMILITON PATH, 把判斷 "圖 G 是否存在 HAMILITON PATH" 轉化成判斷 "此 SC 局況某方是否能勝出", 從而得出 SC 是 NP-HARD 的結論
類似的, 現在要選一個 NPC 問題, 把它轉化成 AOC 中的局況

想到的是 PLANAR GRAPHS VERTEX COVER
這個問題即使限制 degree 不大於 3 仍是 NPC 的 (見 Wikipedia)
即是說, 給出圖 G, 是否能選取不多於 k 個頂點覆蓋所有的邊

現假設有玩家 A 和 B
玩家 A 有 |E| 隻劍兵, 對應著 |E| 條邊, 而且是被困著的 (例如地圖是海, 劍兵在孤島)
玩家 B 則沒有村民和軍隊, 但有 |V| 座弓箭場 (在 |V| 個島上) 和剛好夠資源生產 k 隻茅兵

對於邊 (u, v), 要做到在島 u 生產的茅兵能射到這條邊的劍兵但又不能走到島 v
具體方法是



即是說, 在某個島生產茅兵能殺掉相鄰邊上的玩家 A 劍兵
玩家 B 能勝出的唯一方法是殺掉所有劍兵, 顯然的, 這對應著圖 G 有 size k 的 vertex cover
即是說, 如果懂得判定 AOC 的勝負問題, 則懂得判定 planar 的 VC 問題
得出 AOC 是 NP-HARD 的

ps0. 更多的遊戲
ps1. AOC 今年會更新! :D

ITCSC-INC Winter School 2012: Keywords

Network Coding
- Randomized coefficient matrix G: (i, j) : e[j] = G[i][j] * e[i]
- High Probability Det != 0
- Theorem: Cut(s, t) = Maximum information sent from s to t = #Linearly Independent vectors

Directed Graph connectivity
- F = H + GF, F = H * inv(I - G)
- High Probability: Min Cut = Matrix Rank
- Compute inv(I - G), Matrix for Cut(s, t) = extract submatrix from it

Single Source
- Topological sort, O(Δd²)
- Use Superconcentrators → O(Δd)

Expanders
- Sparse and highly connected
- Example: Bipartite Graph (n, 0.75n), left regular with constant number of edges
- High Probability: if |S| ≤ n/2 → |N(S)| ≥ |S|

Superconcentrators
- G(I, O): I, O = disjoint vertex sets
- For every k, choose k vertex from I, O and there exists k edge-disjoint path
- Construct: edge from I_i to O_i
- |I'| = 0.75|I|, |O'| = 0.75|O|, Expanders: (I, I'), (O', O)
- Recursively Superconcentrators G(I', O')

Matrix Rank
- Find linearly independent columns vectors for A_{m × n}
- Regular Bipartite Graph (n, 10m): left degree = 2, right degree = n/5m
- B[i] = Random Linear Combination of n/5m column vectors from A
- Done in O(#Non-zero entries in A)
- High Probability: Rank(B_{m × 10m}) = Rank(A_{m × n})
- Trace: at most n/5 vectors in A are candidate: reduce problem to A'_{m × n/5}

Sem 4 1/13: Begin

不知不覺間來到第 4 個 sem, 感覺還是一事無成
出了 GPA, 以數值來看總算可以很自然地告訴別人
該 A 的科都 A 了, A 不了的也沒有很失望

下年會不會去 exchange 還是未知數
今個 sem 還是讀書 + ACM (其實我都唔知仲可以有甚麼..)
繼續全部讀 major

CSC 310 - Software Engineering
十半堂當然不上, 也沒有一定要上的理由
為了吸引人答問題派 coupon ← dislike

CSC 318 - Principles of Programming Languages
感覺: 未讀過就唔叫讀過CS, 不過興趣不大

CSC 325 - Computers and Society
還在 waitlist, 計 attendance 的 tutorial 撞了 day-off, 極有可能 drop
不得不提這個 course = 浪費時間, 還要做 project, 莫明奇妙

CSC 342 - Computer Architecture
又是李健康, 又有 4 個 quiz + resubmit..
不過 project 用 C 做! 希望唔好咁痛苦..

CSC 443 - Data Communication and Computer Networks
mole神的 course! 由於 workload 很大所以沒有 take
不過如果不是很忙的話打算去 S 班食花生, 上 mole神堂學到很多野呢

CSC 506 - Topics in the theory of computing
被 chin 慫恿去上了一堂 Andrej 的 course, 感覺: 正
內容是 coding theory + boolean functions + expander
應該會繼續 sit 下去

CSC 516 - Spectrum Algorithms
這個 sem 最刺激的 course, 內容大部份都未聽過
據超超講 + 自己經驗: 每個星期要花數小時複習
目前感覺是 linear algebra 和 graph 的關係
未來幾個月應該要和 matrix 做朋友了

最後當然是 WF
不過感覺離 WF 還有很多時間, 又很久沒有 5hr 的 training, 完全未有應有的緊張感
目前還沒有一個很明確的 rank 目標, 所以還是專心做題目吧