2012级--讨论记录 (第二学期)

2013年3月1日

[课件下载]

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

2013年3月8日

[课件下载]

1. 加法和乘法原理的应用：识别元素；识别不相交的集合。
2. 列表、置换和子集。
   • 列表：本质是函数。
   • 置换：本质是双射函数。
   • k-元素置换：本质是列表。
   • k-元素子集：也可以看作函数。
3. 双射在counting中的作用：元素个数不变，但更容易计算。
4. 等价关系在counting中的作用：等价类大小相同时，可以做除法。

2013年3月15日

[课件下载]

1. maximum-subarray problem。
   • divide、conquer和combine在这个算法中分别如何体现。
   • 找max-crossing-subarray的方式与brute-force不同，从而节约操作。
   • 运行时间的递归表示。
   • 利用recursion tree来猜测运行时间的渐进表示法。
   • 利用substitution或master theorem来证明。
2. substitution证明的一些细节。
   • 为低阶项保留余量。
   • 恰当运用替换。
3. recursion tree。
   • 作用：猜测运行时间；直接证明运行时间。
   • 构建的步骤：中间节点；叶子节点；每层的和；层数；总合。

2013年3月22日

[课件下载]

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

2013年3月29日

[课件下载]

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

2013年4月7日

[课件下载]

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