“2017级--小班讨论 (第二学期)”的版本间的差异

• 1-exam.pdf

( 1-exam-handout.pdf)

• 无

• Cantor-Bernstein Theorem@wiki

 (阅读目的: 学习 Cantor-Bernstein Theorem 的证明。)

2018-03-12

• 2-1: 算法的正确性

• Insertion Sort

1. 刘恩萌
2. 姜勇刚
3. 张天昀

• Cyclic Hanoi

1. 李凯旭
2. 郑奘巍
3. 董杨静

• Hoare Logic@wiki: An Axiomatic Basis for Computer Programming (Hoare CACM69).pdf

 (阅读目的: 了解 Hoare Logic。)

2018-03-19

• 2-1: 算法的正确性 (2)

• Algorithmic Gap

1. 王腾
2. 李顶为
3. 肖江

• Asymptotic Notations

1. 马常风
2. 黄秉焜
3. 吕云哲

• Paper: Loop Invariants: Analysis, Classification, and Examples.pdf

 (阅读建议: 不必一次性读完 (这也不太现实); 
  先阅读第一章，从宏观角度理解循环不变式。
  再对照目录，在适当时候阅读相应算法。)

2018-03-26

• 程序设计辅导 (一)

• The twelvefold way (1)

1. 高天朗
2. 谢逸
3. 何伟

• The twelvefold way (2)

1. 张廷昊
2. 匡舒磊
3. 殷天润

• Twelvefold Way (wiki) Basic Enumeration (尹一通老师 “组合数学” 课程讲义)

 (阅读建议: 每位同学(不仅是做 Open Topics 的同学)都读一读。) 

• The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1

 (阅读建议: 阅读第 390 页。理解什么叫做 "indistinguishable"。)

2018-04-02

• 2-2-efficiency.pdf
• 2-2-efficiency-handout.pdf

• 证明 The Master Theorem

1. 兰兆炜
2. 吕云哲

• 介绍 Akra–Bazzi Method

1. 李博文
2. 刘寒

• Paper: On the Solution of Linear Recurrence Equations (Akra and Bazzi, 1998)

 (阅读建议: 了解该方法。在本科阶段，不太用得着。大家以后做复杂的算法分析时（比如分析平均情况时间复杂度），可能会用得到。) 

• Concrete Mathematics. R. Graham, D. Knuth, O. Patashnik.pdf

 (阅读建议: 第三章。了解如何处理取整函数。要认识到：如果需要更精确的复杂度分析，我们是有相应的数学工具的。)

• Paper: Finding Repeated Elements (Misra, 1982).pdf

 (Paper for the "Treasure Hunt" section.)

2018-04-11

• 2-3-counting.pdf
• 2-3-counting-handout.pdf

• Josephus Problem

1. 裴一凡
2. 戴若石
3. 毕秋宇

• Generating Function

1. 张灵毓
2. 何润雨
3. 丁保荣

• Concrete Mathematics. R. Graham, D. Knuth, O. Patashnik.pdf

 (阅读建议: 第七章 (7.2-7.5)。Generating Function。)

2018-04-16

• 程序设计辅导 (二)

• Alpha-Beta 剪枝

1. 张博乔
2. 郑奘巍
3. 张天昀

• SAT 求解算法

1. 袁彦
2. 李顶为
3. 杨欣然

• The international SAT Competitions

2018-04-18

• 2-4-recurrences
• 2-4-recurrences-handout

• 无 (临时习题课)

• Paper: TR89 (MIT Charles Leiserson) VLSI Theory and Parallel Supercomputing.pdf

   (阅读建议: 了解 VLSI Layout 相关的更多有意思的结论与算法。(算法问题无处不在。))

• Book: Programming Pearls (Second Edition Jon Bentley).pdf

   (阅读建议: Column 8 关于 Maximal-sum Subarray 问题的讨论。)

• Mellin Transforms and Asymptotics: The Mergesort Recurrence (Flajolet 1994).pdf

   (Paper for the "Treasure Hunt" section.)