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

2014年2月20日

1. 讨论上学期期末笔试题
   • Square Field 问题与动态规划
   • 形式化方法解题
   • BNF范式
   • 证明幂集的大小
   • 排练的判断
   • 不等势的证明

2014年2月27日

1. 问题讨论
   • 贪心解题为什么会失败？从搜索的角度解释。
   • 动态规划为什么可以求解？
   • 动态规划的本质也是穷尽搜索，为什么效率可以保证？

2014年3月6日

[课件下载]

1. • DH第四章作业讨论

2014年3月13日

[课件下载]

1. • DH第五章作业讨论
   • 算法正确性证明的基本步骤
   • 使用循环不变式证明算法正确与使用数学归纳法证明定理正确的异同

2014年3月20日

[课件下载]

1. • DH第六章作业讨论
   • TC第二章问题讨论

2014年3月27日

[课件下载]

1. • 根据度序列构建平凡图的Hakimi算法
   • Hakimi算法的复杂度分析
   • 根据度序列构建平凡图问题的算法复杂度下界问题讨论

2014年4月3日

[课件下载]

1. • 从n元集合中取k元多级的计数问题
   • 用集合的观点来看待加法原理、乘法原理和商原理
   • 根据CS习题证明从n元集合中取k元多级的计数公式
   • 讨论题：如何使用递归树来猜测递归式的界

2014年4月10日

[课件下载]

1. • Master 定理的基本原理
   • 结合习题使用Master定理（习题讨论）
   • 使用O(n)时间复杂度的算法解最大连续子串问题
   • 讨论题：使用例子说明为什么分治法可以比穷举法更加有效？

2014年4月17日

[课件下载]

1. • 结合习题讨论证明2-ear-Lemma的归纳法
   • 用递归方法来求解Collatz猜想
   • 讨论题：举适合用递归方法来求解的例子

2014年4月24日

[课件下载]

1. • 样本空间，事件，概率分布等基本概念
   • 概率基本概念习题讨论
   • 讨论题：概率树的作用，独立实验的概率树自同构性质

2014年5月1日

节日：D

2014年5月8日

[课件下载]

1. • 概率计算的容斥原理
   • 计数的容斥原理
   • 习题讨论
   • 讨论题：随机算法中产生均匀分布的方法。

2014年5月15日

[课件下载]

1. • 条件概率、Bayes公式、独立试验过程、概率树图
   • Bernoulli试验、期望、Indicator 随机变量、几何分布
   • 相关习题讨论
   • 讨论题：(1)快速排序过程中的Partition子过程的正确性(2)桶排序的基本原理及其性能分析。