資訊專欄INFORMATION COLUMN
摘要：除特別標注外，文章非原創(chuàng)插圖全部來自課程相關資源。劇透預警內(nèi)容包含大作業(yè)的關鍵問題解法分析。為的返回值此方案下，判斷只需要對應，判斷使用結(jié)果準確，判斷檢測的對應是否為。更新此方法已確定違反的。
Princeton的算法課是目前為止我上過的最酣暢淋漓的一門課，得師如此夫復何求，在自己的記憶徹底模糊前，愿對這其中一些印象深刻的點做一次完整的整理和回顧，以表敬意。
注：
這是一篇更關注個人努力與完成任務項目過程相關的文章，內(nèi)容集中于課程背后值得提到的部分，不會介紹課程基本信息及學習時必讀的設定要求等部分，敬請諒解。
在學習一門課程的時候考慮為什么這么教是個人習慣，我會嘗試給出一些解讀，為什么這門課這么屌(awesome)。
優(yōu)化無止境，越學習才能越深刻地感受自己的無知，即使是作業(yè)內(nèi)已提到的額外內(nèi)容我也并沒有一一探究完整，這里只是謙卑地盡力記錄自己的努力，并無意與誰比較，如有新的進展還會回來更新。
除特別標注外，文章非原創(chuàng)插圖全部來自課程相關資源。
每一小節(jié)的作業(yè)題目鏈接到specification，“√”鏈接到checklist，“〇”鏈接到code下載。
這里提供一個全文完整的資源樹。
劇透預警：
內(nèi)容包含大作業(yè)的關鍵問題解法分析。
作為第一部分開學第一課，作業(yè)Percolation可謂精妙：
既沒有復雜的語法使用（僅數(shù)組操作），又著實比在基礎語言層面上升了一個檔次；
漂亮的visualizer動畫效果激勵著初學者完成任務；
強大的autograder功能初次展現(xiàn)，評價算法的主要管道一目了然，每一微秒每一字節(jié)都很重要；
針對學習迅速的同學還隱含了一個很大的挑戰(zhàn)：在僅使用一個WeightedQuickUnionUF對象的前提下，解決backwash問題。
下面主要聊聊backwash：
問題的核心源自virtual top/bottom，一個強行被導師在課程視頻中提到的優(yōu)化方法，于是天真的同學們（我）就去開心地實現(xiàn)這個看似無辜而又性能楚楚動人的方法，卻毫不了解導師在下一節(jié)中馬上提出的backwash問題是何物，還覺得這種低級錯誤怎么可能會發(fā)生：
java-algs4 PercolationVisualizer percolation/input10.txt
……
（我發(fā)誓這就是我看到的東西……）
把痛碎的心小心拼回，認真思索一番后確定問題根源出在virtual bottom，一個顯而易見的解決方案便浮現(xiàn)在眼前：使用兩個UF，一個使用vb一個不用，判斷percolate用前者，判斷full用后者，解決！
Raw Score 100.00 / 100.00
然而checklist的一句話又引起了我的注意：
However, many students consider this to be the most challenging and creative part of the assignment (especially if you limit yourself to one union-find object).
加上autograder特別溫馨的提醒“bonus failed”，我不得不重新開始審視這個問題。
后來的事實證明，直到課程結(jié)束沒有一個問題再讓我如此頭疼。經(jīng)過了一段可謂長征式的思考，加之在forum的討論中得到了一點靈感(多加利用Find())，最終形成并實現(xiàn)了解決方案，方案核心如下（corner case另行處理）：
將原方案中表示open狀態(tài)的boolean數(shù)組改為byte數(shù)組，設定規(guī)則如下：初始化的默認值0代表blocked site，賦1代表open site，賦2代表與尾行相連的open site；
每open一個site，如果位于尾行則賦2，否則賦1；
分別對每個鄰接site檢測：如任何一方的root site對應byte值為2，將雙方Union后的root site設為2。（root為Find()的返回值）
此方案下，判斷open只需要對應byte>0，判斷full使用UF結(jié)果準確，判斷percolates檢測virtual top的root site對應byte是否為2。
Raw Score 101.25 / 100.00
Test 2 (bonus): Check that total memory <= 11 N^2 + 128 N + 1024 bytes
==> passed
對這個作業(yè)來說，上面這三行的成績凝聚了太多。
II. Resizing Array & Linked Lists與Randomized Queues and Deques √ 〇第二周課程正式展開，但在作業(yè)深度上相對稍有下降，根據(jù)指定的性能和API要求，選擇適當?shù)膶崿F(xiàn)方式（動態(tài)數(shù)組、單、雙向鏈表），實現(xiàn)Randomized Queue和Deque，主要訓練基本的算法分析和編程嚴謹性（完善處理corner-case），但并無特別的難點。有兩個小技巧可以提出：鏈表可使用sentinel node(s)使代碼更簡潔（checklist已提），寫client時可先shuffle再插入(bonus)。
2018更新：最近同學在做這道題時發(fā)現(xiàn)autograder已明確指出不可以使用數(shù)組，這就使得這個bonus變得有趣多了：
仔細想一下，既然API已經(jīng)把我們非常嚴格地限制在只能遍歷一遍輸入的情況下，而我們?nèi)匀幌Ｍ鸕Q不超過k個元素，那么在正常讀入k個元素后面對下一個元素我們只有兩個選擇，dequeue一個舊元素然后enqueue新元素，或直接忽略這個新元素；所以問題的關鍵就變成了一個概率問題，兩個選擇應當如何權衡，才能保證每個元素最終留在RQ中的概率相等呢？
相對應地，autograder也有完整的假設檢驗(t-test)來實際檢測，小伙子你真的做對了嗎？
不必多說，擼起袖子上吧，撿起高中的排列組合知識，仔細分析一下，你算出的忽略當前新元素的概率應該是這樣：
$$mathrm{P}_{discard}=frac{mathrm{C}_{n-1}^k}{mathrm{C}_n^k}=frac{n-k}{n}$$
plug it in and feel the magic! 不得不說這個作業(yè)的設計之精巧，看似非常不起眼的一個小bonus，竟然也幾乎是蘊含著Monte Carlo方法的一些基礎啟發(fā)，真是妙啊。
過程中一并學習了Java的Generics，Iterable，Iterator概念，在大學課程部分已學習掌握得比較熟練，可不談，the result speaks：
Raw Score 100.19 / 100.00
Test 3 (bonus): Check that maximum size of any or Deque or RandomizedQueue object created is <= k
==> passed
結(jié)合兩次作業(yè)特性，可看出一些值得一提的點：
作業(yè)任務要求與說明往往面面俱到細致入微，在給定公有API框架及其對應時間空間復雜度的基礎上，結(jié)合課程視頻知識內(nèi)容，這種“受指導”的編程過程變得十分清晰，尤其是其中API的設計，風格簡潔高效到自成一家，我認可自己的代碼風格已很簡潔，而algs4.jar讓我第一次看到了更高；
給定充足的測試材料，包括各類corner-case或相對有趣的輸入數(shù)據(jù)（如sedgewick60.txt），及合適情況下生動的可視化工具（如PercolationVisualizer.java），都使得學生可以全力，高效，有動力地，將精力集中在核心算法本身上。
III. Sorting與Pattern Recognition - Collinear Points √ 〇本周的課程介紹了兩大經(jīng)典排序：Mergesort和Quicksort，自然作業(yè)也與sorting緊密相關。Collinear Points（找出所有4個或以上共線的點構成的點集）是第一個在運行時見證“好的算法”與“暴力算法”直觀差別的作業(yè)，這樣的對比能給學生帶來深刻的影響：忙了好久，為了什么？
上圖為暴力算法(~N^4)求解100個數(shù)據(jù)點(input100.txt)，下圖為基于排序的算法(~N^2logN)求解1423個數(shù)據(jù)點(rs1423.txt)
測試數(shù)據(jù)還有很多。圖中示例對快速算法給定數(shù)據(jù)量龐大了不止10倍，運行時間卻與不到1/10數(shù)據(jù)量下的暴力算法接近；對上圖數(shù)據(jù)，快速算法基本看不到找線的動畫過程就完成了；對下圖數(shù)據(jù)，暴力算法在可以忍受的時間里基本找不到幾條線。
這樣的運行結(jié)果可以給學生一種非常好的對自己努力的掌控感，正是這樣一個個美妙的瞬間使學生能以最好的狀態(tài)與飽滿的好奇心在算法之路上繼續(xù)走下去。
作業(yè)說明中對核心算法的描述非常清晰，應當特別小心的技術點（浮點誤差、正負零等等）也都在checklist中予以強調(diào)，因而實現(xiàn)難度不算很大，其中使用了Java的Comparable與Comparator，排序過程調(diào)用Arrays.sort()，詳細思考問題理清關系后，實現(xiàn)非常自然，前提是編程基本功必須扎實。
值得提到的點：
checklist鼓勵初學者開始編寫快速算法時先不要擔心5個或以上的點共線的情況，而實際上對基本功扎實的同學，從開始便考慮這個問題更為合適；
checklist提到compare()和FastCollinearPoints類可以完全避免浮點數(shù)用整形運算實現(xiàn)，我想到的唯一符合要求（Point.java注釋中規(guī)定不得依賴toString()）的方法是，對Point類的compareTo()方法返回值增加意義（不單純返回正負1），以獲取兩點的坐標之差（因題目給定坐標取值范圍0-32767，可在返回值低兩位字節(jié)存儲x坐標差， 高兩位字節(jié)存儲y坐標差），再利用坐標差判斷斜率是否相等。雖依然完全符合題目要求，但已有一點奇技淫巧之嫌，并且不一定能夠通過autograder（評分時會替換Point類去測試FastCollinearPoints），不多討論。（更新：此方法已確定違反FastCollinearPoints的API。）
最終實現(xiàn)版本拿到了100分，未發(fā)現(xiàn)關于bonus的討論。
IV. Priority Queue與8 Puzzle √ 〇剛剛講解完使用Binary Heap實現(xiàn)的Priority Queue，便迎來了這周的8 Puzzle——使用PQ實現(xiàn)A*解決NP難問題，所以——重點在優(yōu)化咯。
(Image Source Here)
左邊是目標狀態(tài)，右邊是起始狀態(tài)；對，就是那個——小時候功能手機上的蒙娜麗莎。
隨著學習的深入，這次作業(yè)的復雜度有了一個明顯的上升，但這門課最美妙的地方之一也就在這里：面臨的問題越來越復雜，而導師給出的指導思路依然保持最大程度的簡潔優(yōu)雅，每一步驟的設定都直指問題核心，并在實現(xiàn)功能基礎上提供非常豐富的優(yōu)化選擇，以及每個優(yōu)化會帶來的影響分析。
"It"s a funny feeling being took under the wings of a dragon. It"s warmer than you think." —— Gangs of New York
整個問題相對比較復雜，但經(jīng)過給定API的劃分和給定的限制后，問題變成了實現(xiàn)一個個目標明確的小方法而已，其中最復雜的不過是A*的實現(xiàn)，而周到合理的封裝和PQ的使用也使得這個過程無比自然，在此之前我從未意識到我可以將A*在如此短小清晰的代碼中實現(xiàn)：（源碼如此，僅省略了聲明過程）
while (!pq.min().board.isGoal()) {
cur = pq.delMin();
for (Board nb : cur.board.neighbors()) {
if (cur.prev != null && nb.equals(cur.prev.board)) continue;
pq.insert(new Node(nb, cur.moves+1, cur));
}
}
PQ使用了Manhattan Priority作為Comparator，Node為封裝Board的單鏈表節(jié)點，結(jié)束后獲取最短路徑只需取PQ中最小Node，利用prev指針遍歷。
解決8 Puzzle這一NP難問題的核心代碼便完成了。
當然，在其余部分還是有不少值得提到的點：
用char[]存儲一個Board的狀態(tài)比用int[][]好太多，但使用前需要詳細測試將char做數(shù)字使用與直接用int的區(qū)別；
Board的equals()方法只需比較char[]構成的String即可，早期因圖省事直接比較了toString()的返回值（one-liner），造成了很大的性能損失，最后尋找問題來源也費了不少功夫（教訓：看似再簡單的部分也要在腦袋里多轉(zhuǎn)一轉(zhuǎn)再下手，devil in the details，…，you name it）；
Solvability: 這篇文章描述的解決方案應為checklist所述方案，但需要脆弱地依賴toString()反推Board內(nèi)容，在本期課程的API設定中已被明確禁止，要求使用兩個同步A*的方案解決（最好使用一個PQ），但未來session可能會在兩方案對應API設定間切換，所以我都實現(xiàn)了一遍，上面出現(xiàn)的A*代碼來自文章所述方案；
實現(xiàn)Priority的cache時需要稍多做思考，直覺想到的第一方案是儲存在Node中與A*過程配合，而這將使A*代碼迅速腫脹，且沒有很好地利用更多規(guī)律：如checklist所指出，對相鄰Board每次重新計算Priority其實也有很多重復工作，我的做法是將cache過程作為Board類一個私有構造函數(shù)，構造相鄰Priority只需做對應增量操作即可，以最簡潔的手段達到了目的。
我的最終測試文件及結(jié)果在這里，運行于i5-2450 (8G)，結(jié)尾幾個復雜的4x4開始因內(nèi)存不足報錯，論壇查到大概需要5-6G超出了我的空閑內(nèi)存，即使要測也會用到虛擬內(nèi)存，因而結(jié)果參考意義不大。
對于這個作業(yè)，努力的最終匯報便是，看著終端中puzzle一個個被正確解決沾沾自喜，然后到相關的拓展材料中去體驗無知，發(fā)現(xiàn)更大的世界。
這一周的Balanced Search Trees課程令我印象深刻。在進入作業(yè)討論前，我希望先聊聊這次的課程內(nèi)容：
在前一周的課程中就已引入了二叉樹的概念，一個無比經(jīng)典的數(shù)據(jù)結(jié)構，這我在大學課程中便已了解到，只是認識非常淺薄，并從未，也從未認為我能夠，動手實現(xiàn)過。
可如果說在上一周的學習中彌補了我的這個問題，對二叉樹有了更深刻的理解，那么這一周的課程徹底顛覆了曾經(jīng)心中幼稚的見解，所謂質(zhì)變，我應該是在這里體會到的：
從小學四年級開始在少年宮學習BASIC到初中的PASCAL，以致雖然后來停止學習，但因為接觸時間遠早于同齡人而在此方面經(jīng)歷了各種優(yōu)勢，但從小在我心中“程序”，以及它背后所代表的機械邏輯始終被認為是“就那么回事兒”的。我天真地認為自己早已掌握“程序”界的終極真理，無非就是嚴絲合縫一步不差地執(zhí)行、再執(zhí)行，只要“機械”性地認真下去，便沒有什么解決不了的，以至于從小就在性格中造就了一面“徹頭徹尾的唯物+實用主義者”，不相信任何世間美好。
有這句天真的話在前，接著慢慢成長，讀書，行路，閱人，歷事，自然會學到原來這個世界真的不是那樣，開始理解愛與人性，開始理解這個世界的美妙。加上比較幸運，因而“唯心+浪漫主義者”的一面在我的性格里也發(fā)展得很好。但大學開始繼續(xù)學習計算機，多少，對“程序”這一徹頭徹尾“唯物+實用”精神的產(chǎn)物，還是抱著一些看法的。
結(jié)束這一周的課程學習后，我改變了這個看法。
課程開始先講解了2-3 search trees，一種引入了新規(guī)則樹型結(jié)構。這是一個“理解容易，實現(xiàn)復雜”的Symbol table方案，它可以對任何輸入數(shù)據(jù)保證樹形結(jié)構的平衡以達到保證各項操作logN的復雜度，而規(guī)則卻足夠簡單到可以在課堂中很快描述清楚，可以算是課程中第一個令我驚艷的算法。
這時我想：果然在一步步深入后算法變得高深莫測了起來呢，這個2-3 tree，理解起來容易，要實現(xiàn)起來可真是困難吶。已經(jīng)不是二叉樹那么簡單的東西了，以后是不是只會更難啊，看來我遇到了一個屏障，這是不是我能走到的最遠了啊。（開始有一點點擔心）
直到視頻結(jié)尾出現(xiàn)關于implementation的討論：
Bottom Line: Could do it, but there"s a better way.
緊接著下一節(jié)就是我們的主角：左傾紅黑二叉樹(LLRB)。
它只做到了一件事：將2-3 tree帶回了二叉樹世界，卻僅對樸素的二叉樹做極其微小的改動——每個節(jié)點增加1 bit，用以表示“顏色”，加之無比簡潔的引導，便在現(xiàn)實世界中實現(xiàn)了原先只是構想的2-3 tree幾乎全部的優(yōu)點。
紅黑樹本身就是70年代Sedgewick教授參與提出的，而LLRB是由他一手提出的極其簡潔的紅黑樹實現(xiàn)版本，尤其是它的insertion，在課堂上作為重點講解，僅在原樸素二叉樹實現(xiàn)代碼基礎上，增加了3個小工具函數(shù)（左旋、右旋、翻轉(zhuǎn)）和遞歸插入過程中的4行代碼（如圖），便完成了所有工作。
在徹底理解LLRB后，我想我被征服了。程序不再僅僅是徹頭徹尾“唯物+實用”精神的產(chǎn)物，而是我們理解世界的工具，也見證著我們改變世界過程，它與其他一切事物一樣，可以充滿真正的美。
我想可以這樣評價紅黑樹背后的思想：
它就像人類從蒙昧時代開啟智慧的一道光，將原來松散無序的組織變得優(yōu)雅而高效，并且還尊重了所有舊時代的傳統(tǒng)；
也正是因為尊重傳統(tǒng)，才使得新的秩序得以穩(wěn)定存在；
新的秩序完整了傳統(tǒng)，成為了傳統(tǒng)當中，最為亮麗的部分。
這樣的成果也不是憑空出現(xiàn)的：
勇于跳出傳統(tǒng)的框框，用自由的視角審度；（2-3 tree已不是二叉樹）
回到現(xiàn)實在一點一滴中細膩體驗；（發(fā)現(xiàn)除繁瑣的直接實現(xiàn)外其他實現(xiàn)方式的可能性）
不妄自菲薄出身，用尊重的態(tài)度行動。（選擇回到經(jīng)典二叉樹模式，試圖在舊傳統(tǒng)上建立新秩序）
知行合一，至此可謂正途。
同為插入255個隨機節(jié)點，左圖為樸素二叉樹，右圖為左傾紅黑二叉樹。
作為第一部分的最后一個作業(yè)，kd-tree其實難度沒有它看起來那么大。課程部分已很完整地討論過很多種經(jīng)典的樹形結(jié)構（分析+實現(xiàn)），到這個階段學生應已對樹形結(jié)構非常熟悉了，實現(xiàn)kd-tree已是水到渠成。
同樣的，編程嚴謹性在這個作業(yè)中變得更加重要——情況相比前幾周又要復雜一些，從零編寫一個特定（且不簡單的）規(guī)則下運行的樹形結(jié)構，主要功能是高效地插入與查找；
這次的作業(yè)同樣包含了一個暴力算法的版本（使用默認的紅黑樹結(jié)構），除了在執(zhí)行效率上可以做比較外，還提供了一個重要的軟件工程思路：面臨一個較為復雜，而優(yōu)化空間很大的問題時，先實現(xiàn)一個最簡單的暴力算法版本檢測結(jié)果（往往可以非常簡便地實現(xiàn)），再考慮進階的算法與數(shù)據(jù)結(jié)構實現(xiàn)性能優(yōu)化，并在實現(xiàn)期間，暴力算法可以作為檢驗算法正確性最直接的參考。
實現(xiàn)過程中值得提到的點：
節(jié)點的奇偶性是一個不小的麻煩，編寫需要十分謹慎，我的做法是在Node類中添加了一個boolean用以表示奇偶，相信一定有更好的方法（不存儲RectHV），還會回來探索；
Nearest Neighbor的查找過程需要思考清楚，剪枝的界限十分清晰，尤其是剪裁其中一個子樹的條件：如果本子樹中找到的最近點與給定點距離 已小于 給定點到另一子樹矩形區(qū)域的距離（點到點距離比點到矩形距離還近時），才能跳過另一子樹的遍歷過程。
左圖為Nearest Neighbor，右圖為Range Search。（根據(jù)鼠標狀態(tài)信息）
圖中紅色部分為暴力算法運行結(jié)果，藍色部分為kdtree運行結(jié)果；在增加數(shù)據(jù)量后多帶帶測試，暴力解法效率明顯下降。
在一個學期的辛苦努力后，帶著滿滿的收獲與日益成熟的頭腦，第二部分正式開始了。
“相信經(jīng)過了第一部分的學習同學們都會有很大的提高，短暫休息后也恢復了飽滿的學習熱情，那么我有理由相信你們準備好了接受點真正的考驗?！?
—— 視頻中永遠不會提到的導師內(nèi)心獨白（歷經(jīng)折磨后的腦補）
第二部分在課程與作業(yè)兩個方向的難度都比第一部分提升了一個檔次。好在不巧被導師言中，我的確有非常好的提升感和新一輪的熱情。
所以，放馬過來吧。
第一周便直奔主題，開啟了數(shù)據(jù)結(jié)構領域的又一大領域：圖。
課程中出現(xiàn)了一個很有趣的分類值得提到，是形容問題難度的：
任何程序員都能夠解決。
典型的勤奮的算法課學生能夠解決。
雇傭一個領域?qū)＜摇?/p>
非常難。
沒有人知道難度。
已證明不可能解決。
并舉出了一些符合條件例子來說明這些分類，當然可以料到的，有很多難度2的例子。
這針雞血打得，嘖嘖嘖，不留痕跡。
很好。諸位紅著眼的同學，準備變身吧。
第一周的作業(yè)是WordNet，少了第一部分作業(yè)多圖多動畫的喧鬧，不再為搏人眼球而吵吵嚷嚷，卻在安靜的terminal和腦中的抽象之海中展開了一場貨真價實的戰(zhàn)斗。
因文字方面中西文化背景截然不同，導致WordNet的概念不太方便簡單地描述清楚，但作業(yè)說明中已解釋得比較詳細，這里只放一張示意圖：
整個作業(yè)可以分為三大部分：選擇合適的結(jié)構存儲結(jié)構復雜的詞典及其網(wǎng)絡關系（基本功），實現(xiàn)正確高效的廣度優(yōu)先遍歷計算SAP（難點），和在此基礎上一層一層更細致的優(yōu)化（進階）；
本次也是checklist優(yōu)化部分唯一標注optional的作業(yè)，因為的確實現(xiàn)起來有難度；分布如上所注。
詞典(synsets)為ID與單詞的多對多關系（一詞多號，一號多詞，釋義僅供參考無需讀?。?，上下位關系(hypernyms)是以ID為單位的樹形結(jié)構（圖中的箭頭關系），可以明顯看出hypernyms使用有向圖表示，synsets存儲方式取決于訪問需求，因程序中正反都會使用（以詞求號，以號求詞，求詞存在），我選擇了空間換時間：
