摘要：除特别标注外，文章非原创插图全部来自课程相关资源。剧透预警内容包含大作业的关键问题解法分析。为的返回值此方案下，判断只需要对应，判断使用结果准确，判断检测的对应是否为。更新此方法已确定违反的。
Princeton的算法课是目前为止我上过的最酣畅淋漓的一门课，得师如此夫复何求，在自己的记忆彻底模糊前，愿对这其中一些印象深刻的点做一次完整的整理和回顾，以表敬意。
注：
这是一篇更关注个人努力与完成任务项目过程相关的文章，内容集中于课程背后值得提到的部分，不会介绍课程基本信息及学习时必读的设定要求等部分，敬请谅解。
在学习一门课程的时候考虑为什么这么教是个人习惯，我会尝试给出一些解读，为什么这门课这么屌(awesome)。
优化无止境，越学习才能越深刻地感受自己的无知，即使是作业内已提到的额外内容我也并没有一一探究完整，这里只是谦卑地尽力记录自己的努力，并无意与谁比较，如有新的进展还会回来更新。
除特别标注外，文章非原创插图全部来自课程相关资源。
每一小节的作业题目链接到specification，“√”链接到checklist，“〇”链接到code下载。
这里提供一个全文完整的资源树。
剧透预警：
内容包含大作业的关键问题解法分析。
作为第一部分开学第一课，作业Percolation可谓精妙：
既没有复杂的语法使用（仅数组操作），又着实比在基础语言层面上升了一个档次；
漂亮的visualizer动画效果激励着初学者完成任务；
强大的autograder功能初次展现，评价算法的主要管道一目了然，每一微秒每一字节都很重要；
针对学习迅速的同学还隐含了一个很大的挑战：在仅使用一个WeightedQuickUnionUF对象的前提下，解决backwash问题。
下面主要聊聊backwash：
问题的核心源自virtual top/bottom，一个强行被导师在课程视频中提到的优化方法，于是天真的同学们（我）就去开心地实现这个看似无辜而又性能楚楚动人的方法，却毫不了解导师在下一节中马上提出的backwash问题是何物，还觉得这种低级错误怎么可能会发生：
java-algs4 PercolationVisualizer percolation/input10.txt
……
（我发誓这就是我看到的东西……）
把痛碎的心小心拼回，认真思索一番后确定问题根源出在virtual bottom，一个显而易见的解决方案便浮现在眼前：使用两个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”，我不得不重新开始审视这个问题。
后来的事实证明，直到课程结束没有一个问题再让我如此头疼。经过了一段可谓长征式的思考，加之在forum的讨论中得到了一点灵感(多加利用Find())，最终形成并实现了解决方案，方案核心如下（corner case另行处理）：
将原方案中表示open状态的boolean数组改为byte数组，设定规则如下：初始化的默认值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结果准确，判断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
对这个作业来说，上面这三行的成绩凝聚了太多。
II. Resizing Array & Linked Lists与Randomized Queues and Deques √ 〇第二周课程正式展开，但在作业深度上相对稍有下降，根据指定的性能和API要求，选择适当的实现方式（动态数组、单、双向链表），实现Randomized Queue和Deque，主要训练基本的算法分析和编程严谨性（完善处理corner-case），但并无特别的难点。有两个小技巧可以提出：链表可使用sentinel node(s)使代码更简洁（checklist已提），写client时可先shuffle再插入(bonus)。
2018更新：最近同学在做这道题时发现autograder已明确指出不可以使用数组，这就使得这个bonus变得有趣多了：
仔细想一下，既然API已经把我们非常严格地限制在只能遍历一遍输入的情况下，而我们仍然希望RQ不超过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! 不得不说这个作业的设计之精巧，看似非常不起眼的一个小bonus，竟然也几乎是蕴含着Monte Carlo方法的一些基础启发，真是妙啊。
过程中一并学习了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
结合两次作业特性，可看出一些值得一提的点：
作业任务要求与说明往往面面俱到细致入微，在给定公有API框架及其对应时间空间复杂度的基础上，结合课程视频知识内容，这种“受指导”的编程过程变得十分清晰，尤其是其中API的设计，风格简洁高效到自成一家，我认可自己的代码风格已很简洁，而algs4.jar让我第一次看到了更高；
给定充足的测试材料，包括各类corner-case或相对有趣的输入数据（如sedgewick60.txt），及合适情况下生动的可视化工具（如PercolationVisualizer.java），都使得学生可以全力，高效，有动力地，将精力集中在核心算法本身上。
III. Sorting与Pattern Recognition - Collinear Points √ 〇本周的课程介绍了两大经典排序：Mergesort和Quicksort，自然作业也与sorting紧密相关。Collinear Points（找出所有4个或以上共线的点构成的点集）是第一个在运行时见证“好的算法”与“暴力算法”直观差别的作业，这样的对比能给学生带来深刻的影响：忙了好久，为了什么？
上图为暴力算法(~N^4)求解100个数据点(input100.txt)，下图为基于排序的算法(~N^2logN)求解1423个数据点(rs1423.txt)
测试数据还有很多。图中示例对快速算法给定数据量庞大了不止10倍，运行时间却与不到1/10数据量下的暴力算法接近；对上图数据，快速算法基本看不到找线的动画过程就完成了；对下图数据，暴力算法在可以忍受的时间里基本找不到几条线。
这样的运行结果可以给学生一种非常好的对自己努力的掌控感，正是这样一个个美妙的瞬间使学生能以最好的状态与饱满的好奇心在算法之路上继续走下去。
作业说明中对核心算法的描述非常清晰，应当特别小心的技术点（浮点误差、正负零等等）也都在checklist中予以强调，因而实现难度不算很大，其中使用了Java的Comparable与Comparator，排序过程调用Arrays.sort()，详细思考问题理清关系后，实现非常自然，前提是编程基本功必须扎实。
值得提到的点：
checklist鼓励初学者开始编写快速算法时先不要担心5个或以上的点共线的情况，而实际上对基本功扎实的同学，从开始便考虑这个问题更为合适；
checklist提到compare()和FastCollinearPoints类可以完全避免浮点数用整形运算实现，我想到的唯一符合要求（Point.java注释中规定不得依赖toString()）的方法是，对Point类的compareTo()方法返回值增加意义（不单纯返回正负1），以获取两点的坐标之差（因题目给定坐标取值范围0-32767，可在返回值低两位字节存储x坐标差， 高两位字节存储y坐标差），再利用坐标差判断斜率是否相等。虽依然完全符合题目要求，但已有一点奇技淫巧之嫌，并且不一定能够通过autograder（评分时会替换Point类去测试FastCollinearPoints），不多讨论。（更新：此方法已确定违反FastCollinearPoints的API。）
最终实现版本拿到了100分，未发现关于bonus的讨论。
IV. Priority Queue与8 Puzzle √ 〇刚刚讲解完使用Binary Heap实现的Priority Queue，便迎来了这周的8 Puzzle——使用PQ实现A*解决NP难问题，所以——重点在优化咯。
(Image Source Here)
左边是目标状态，右边是起始状态；对，就是那个——小时候功能手机上的蒙娜丽莎。
随着学习的深入，这次作业的复杂度有了一个明显的上升，但这门课最美妙的地方之一也就在这里：面临的问题越来越复杂，而导师给出的指导思路依然保持最大程度的简洁优雅，每一步骤的设定都直指问题核心，并在实现功能基础上提供非常丰富的优化选择，以及每个优化会带来的影响分析。
"It"s a funny feeling being took under the wings of a dragon. It"s warmer than you think." —— Gangs of New York
整个问题相对比较复杂，但经过给定API的划分和给定的限制后，问题变成了实现一个个目标明确的小方法而已，其中最复杂的不过是A*的实现，而周到合理的封装和PQ的使用也使得这个过程无比自然，在此之前我从未意识到我可以将A*在如此短小清晰的代码中实现：（源码如此，仅省略了声明过程）
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的单链表节点，结束后获取最短路径只需取PQ中最小Node，利用prev指针遍历。
解决8 Puzzle这一NP难问题的核心代码便完成了。
当然，在其余部分还是有不少值得提到的点：
用char[]存储一个Board的状态比用int[][]好太多，但使用前需要详细测试将char做数字使用与直接用int的区别；
Board的equals()方法只需比较char[]构成的String即可，早期因图省事直接比较了toString()的返回值（one-liner），造成了很大的性能损失，最后寻找问题来源也费了不少功夫（教训：看似再简单的部分也要在脑袋里多转一转再下手，devil in the details，…，you name it）；
Solvability: 这篇文章描述的解决方案应为checklist所述方案，但需要脆弱地依赖toString()反推Board内容，在本期课程的API设定中已被明确禁止，要求使用两个同步A*的方案解决（最好使用一个PQ），但未来session可能会在两方案对应API设定间切换，所以我都实现了一遍，上面出现的A*代码来自文章所述方案；
实现Priority的cache时需要稍多做思考，直觉想到的第一方案是储存在Node中与A*过程配合，而这将使A*代码迅速肿胀，且没有很好地利用更多规律：如checklist所指出，对相邻Board每次重新计算Priority其实也有很多重复工作，我的做法是将cache过程作为Board类一个私有构造函数，构造相邻Priority只需做对应增量操作即可，以最简洁的手段达到了目的。
我的最终测试文件及结果在这里，运行于i5-2450 (8G)，结尾几个复杂的4x4开始因内存不足报错，论坛查到大概需要5-6G超出了我的空闲内存，即使要测也会用到虚拟内存，因而结果参考意义不大。
对于这个作业，努力的最终汇报便是，看着终端中puzzle一个个被正确解决沾沾自喜，然后到相关的拓展材料中去体验无知，发现更大的世界。
这一周的Balanced Search Trees课程令我印象深刻。在进入作业讨论前，我希望先聊聊这次的课程内容：
在前一周的课程中就已引入了二叉树的概念，一个无比经典的数据结构，这我在大学课程中便已了解到，只是认识非常浅薄，并从未，也从未认为我能够，动手实现过。
可如果说在上一周的学习中弥补了我的这个问题，对二叉树有了更深刻的理解，那么这一周的课程彻底颠覆了曾经心中幼稚的见解，所谓质变，我应该是在这里体会到的：
从小学四年级开始在少年宫学习BASIC到初中的PASCAL，以致虽然后来停止学习，但因为接触时间远早于同龄人而在此方面经历了各种优势，但从小在我心中“程序”，以及它背后所代表的机械逻辑始终被认为是“就那么回事儿”的。我天真地认为自己早已掌握“程序”界的终极真理，无非就是严丝合缝一步不差地执行、再执行，只要“机械”性地认真下去，便没有什么解决不了的，以至于从小就在性格中造就了一面“彻头彻尾的唯物+实用主义者”，不相信任何世间美好。
有这句天真的话在前，接着慢慢成长，读书，行路，阅人，历事，自然会学到原来这个世界真的不是那样，开始理解爱与人性，开始理解这个世界的美妙。加上比较幸运，因而“唯心+浪漫主义者”的一面在我的性格里也发展得很好。但大学开始继续学习计算机，多少，对“程序”这一彻头彻尾“唯物+实用”精神的产物，还是抱着一些看法的。
结束这一周的课程学习后，我改变了这个看法。
课程开始先讲解了2-3 search trees，一种引入了新规则树型结构。这是一个“理解容易，实现复杂”的Symbol table方案，它可以对任何输入数据保证树形结构的平衡以达到保证各项操作logN的复杂度，而规则却足够简单到可以在课堂中很快描述清楚，可以算是课程中第一个令我惊艳的算法。
这时我想：果然在一步步深入后算法变得高深莫测了起来呢，这个2-3 tree，理解起来容易，要实现起来可真是困难呐。已经不是二叉树那么简单的东西了，以后是不是只会更难啊，看来我遇到了一个屏障，这是不是我能走到的最远了啊。（开始有一点点担心）
直到视频结尾出现关于implementation的讨论：
Bottom Line: Could do it, but there"s a better way.
紧接着下一节就是我们的主角：左倾红黑二叉树(LLRB)。
它只做到了一件事：将2-3 tree带回了二叉树世界，却仅对朴素的二叉树做极其微小的改动——每个节点增加1 bit，用以表示“颜色”，加之无比简洁的引导，便在现实世界中实现了原先只是构想的2-3 tree几乎全部的优点。
红黑树本身就是70年代Sedgewick教授参与提出的，而LLRB是由他一手提出的极其简洁的红黑树实现版本，尤其是它的insertion，在课堂上作为重点讲解，仅在原朴素二叉树实现代码基础上，增加了3个小工具函数（左旋、右旋、翻转）和递归插入过程中的4行代码（如图），便完成了所有工作。
在彻底理解LLRB后，我想我被征服了。程序不再仅仅是彻头彻尾“唯物+实用”精神的产物，而是我们理解世界的工具，也见证着我们改变世界过程，它与其他一切事物一样，可以充满真正的美。
我想可以这样评价红黑树背后的思想：
它就像人类从蒙昧时代开启智慧的一道光，将原来松散无序的组织变得优雅而高效，并且还尊重了所有旧时代的传统；
也正是因为尊重传统，才使得新的秩序得以稳定存在；
新的秩序完整了传统，成为了传统当中，最为亮丽的部分。
这样的成果也不是凭空出现的：
勇于跳出传统的框框，用自由的视角审度；（2-3 tree已不是二叉树）
回到现实在一点一滴中细腻体验；（发现除繁琐的直接实现外其他实现方式的可能性）
不妄自菲薄出身，用尊重的态度行动。（选择回到经典二叉树模式，试图在旧传统上建立新秩序）
知行合一，至此可谓正途。
同为插入255个随机节点，左图为朴素二叉树，右图为左倾红黑二叉树。
作为第一部分的最后一个作业，kd-tree其实难度没有它看起来那么大。课程部分已很完整地讨论过很多种经典的树形结构（分析+实现），到这个阶段学生应已对树形结构非常熟悉了，实现kd-tree已是水到渠成。
同样的，编程严谨性在这个作业中变得更加重要——情况相比前几周又要复杂一些，从零编写一个特定（且不简单的）规则下运行的树形结构，主要功能是高效地插入与查找；
这次的作业同样包含了一个暴力算法的版本（使用默认的红黑树结构），除了在执行效率上可以做比较外，还提供了一个重要的软件工程思路：面临一个较为复杂，而优化空间很大的问题时，先实现一个最简单的暴力算法版本检测结果（往往可以非常简便地实现），再考虑进阶的算法与数据结构实现性能优化，并在实现期间，暴力算法可以作为检验算法正确性最直接的参考。
实现过程中值得提到的点：
节点的奇偶性是一个不小的麻烦，编写需要十分谨慎，我的做法是在Node类中添加了一个boolean用以表示奇偶，相信一定有更好的方法（不存储RectHV），还会回来探索；
Nearest Neighbor的查找过程需要思考清楚，剪枝的界限十分清晰，尤其是剪裁其中一个子树的条件：如果本子树中找到的最近点与给定点距离 已小于 给定点到另一子树矩形区域的距离（点到点距离比点到矩形距离还近时），才能跳过另一子树的遍历过程。
左图为Nearest Neighbor，右图为Range Search。（根据鼠标状态信息）
图中红色部分为暴力算法运行结果，蓝色部分为kdtree运行结果；在增加数据量后多带带测试，暴力解法效率明显下降。
在一个学期的辛苦努力后，带着满满的收获与日益成熟的头脑，第二部分正式开始了。
“相信经过了第一部分的学习同学们都会有很大的提高，短暂休息后也恢复了饱满的学习热情，那么我有理由相信你们准备好了接受点真正的考验。”
—— 视频中永远不会提到的导师内心独白（历经折磨后的脑补）
第二部分在课程与作业两个方向的难度都比第一部分提升了一个档次。好在不巧被导师言中，我的确有非常好的提升感和新一轮的热情。
所以，放马过来吧。
第一周便直奔主题，开启了数据结构领域的又一大领域：图。
课程中出现了一个很有趣的分类值得提到，是形容问题难度的：
任何程序员都能够解决。
典型的勤奋的算法课学生能够解决。
雇佣一个领域专家。
非常难。
没有人知道难度。
已证明不可能解决。
并举出了一些符合条件例子来说明这些分类，当然可以料到的，有很多难度2的例子。
这针鸡血打得，啧啧啧，不留痕迹。
很好。诸位红着眼的同学，准备变身吧。
第一周的作业是WordNet，少了第一部分作业多图多动画的喧闹，不再为搏人眼球而吵吵嚷嚷，却在安静的terminal和脑中的抽象之海中展开了一场货真价实的战斗。
因文字方面中西文化背景截然不同，导致WordNet的概念不太方便简单地描述清楚，但作业说明中已解释得比较详细，这里只放一张示意图：
整个作业可以分为三大部分：选择合适的结构存储结构复杂的词典及其网络关系（基本功），实现正确高效的广度优先遍历计算SAP（难点），和在此基础上一层一层更细致的优化（进阶）；
本次也是checklist优化部分唯一标注optional的作业，因为的确实现起来有难度；分布如上所注。
词典(synsets)为ID与单词的多对多关系（一词多号，一号多词，释义仅供参考无需读取），上下位关系(hypernyms)是以ID为单位的树形结构（图中的箭头关系），可以明显看出hypernyms使用有向图表示，synsets存储方式取决于访问需求，因程序中正反都会使用（以词求号，以号求词，求词存在），我选择了空间换时间：
