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

2016年2月22日

1. 本学期课程导引

2016年2月29日

1. 讨论1-1：问题空间与穷举法
2. 讨论1-2：贪心算法与动态规划
3. 作业2-1反馈

2016年3月7日

1. 讨论2-1：MergeSort正确性证明
2. 讨论2-2：循环不变量与递归不变量有何区别
3. 作业2-2反馈

2016年3月14日

1. 讨论3-1：What we talk about when we talk about BIG O?
2. 讨论3-2：在有序序列中查找指定元素问题的复杂度
3. 作业2-3反馈

2016年3月21日

1. 讨论4-1：elegant approach for counting exercise 1.3-4、5?
2. 讨论4-2：逆序数统计
3. 作业2-4反馈

2016年3月28日

1. 讨论5.1 Proof of the Master Theory
2. 讨论5.2 How to calculate the product of two complex numbers?
3. 作业反馈2-5

2016年4月11日

1. 讨论6.1 Proof and applications of Principle of Inclusion and Exclusion��
2. 讨论6.2 Tree diagram for an independent trials process.
3. 作业反馈2-6/2-7

2016年4月18日

1. 讨论7.1 如何扩展证明引理5.4
2. 讨论7.2 Generating UnBiased-Random with Biased Random sub-routine.
3. 作业反馈2-8

2016年4月25日

1. 讨论8.1 证明Randomized-Select期望运⾏时间是 Θ(n)
2. 讨论8.2 排序算法的稳定性.
3. 讨论8.3 严格证明快速排序算法的正确性（部分正确性+完全正确性）
4. 作业反馈2-9

2016年5月9日

1. 讨论9.1 写出堆的ADT及其形式规约
2. 讨论9.2 用二叉树->堆->优先队列的方式给出优先队列的实现
3. 讨论9.3 堆排序是stable的吗？
4. 作业反馈2-10
5. 作业反馈2-11

2016年5月16日

1. 讨论Hashing

2016年5月23日

1. Primes in Hashing
2. 乘法散列法
3. 作业反馈2-12

2016年5月30日

1. BST的中序遍历与排序
2. BST抽象数据类型及其应用
3. 作业反馈2-13(1)