2013年3月1日

计算问题与算法。
- 计算问题：input + output + their relationship。
- 算法：well-defined computational procedure for achieving an input-output relationship。
好算法。
- 要素：正确性、高效性、易实现性。
- 设计流程：思路-->过程-->正确性-->效率。
算法的正确性分析。
- partially correct：基于checkpoint和invariant。
- totally correct：partially correct + termination。
算法的效率分析。
- RAM的要素：数据类型、数据存储方式；指令类型、指令执行方式。
- running time的计算：cost*times；best/worst/average case。
算法效率的渐进表示法。
- Theta, O和Omega的含义：基于集合；基于极限。
- Theta vs. O：用O避免分情况讨论。
- O vs. o：基于集合；基于极限。
- 渐进表示法的比喻：大小关系；相似的性质，但无trichotomy。

2013年3月8日

induction, recursion, recurrences。
- induction、recursion和recurrences的两两关系。
- well-ordering principle和induction的关系：反证法+well-ordering principle=induction。
- top-down比bottom-up的优势：思路更直接；不用证明构建的完备性；base case更直接。
first-order constant coefficient linear recurrence。
- 结论的来源：通过递推展开来猜测。
- 结论的证明：数学归纳法。
the master theorem的证明：基于递归树的时间复杂度分析。

probability。
- 从集合的角度理解sample space, element, event。
- 区分probability weight和probability，并基于probability weight理解probability distribution function的三个条件。
- uniform probability distribution的意义：probability-->counting。
the principle of inclusion and exclusion：基于Venn图解释公式。
conditional probability。
- 基于Venn图解释conditional probability和独立性。
- independent trials process和tree diagram。
random variable：理解random variable, expected value, additivity of expectation。

indicator random variable：原理与应用。
随机化。
- expected running time vs. average-case running time：随机算法 vs. 一般算法的所有输入。
- 随机数生成方法：计算方法；物理方法。
- 数组随机排序方法：permute-by-sorting；randomize-in-place。
计算expected running time的方法：定义；indicator random variable；线性性质；条件期望。
probability distributions and variance。
- distribution function vs. cumulative distribution function：点和区间。
- variance及其来源。

快速排序。
- 正确性证明：loop invariant；递归程序正确性的归纳证明。
- 运行时间：worst-case；best-case；average-case。
- 随机化的快速排序：随机化的意义；期望运行时间。
线性时间排序算法。
- 基于比较的排序：运行时间的下界。
- counting sort：stable；从左往右扫描的改法；对输入的要求及缺点。
- radix sort：从高位开始排序的改法；分解的灵活性；对输入的要求。
- bucket sort：最优运行时间。
选择问题：找最大、最小元；随机化的选择算法；确定性的选择算法。