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

• 问题求解第二学期期末试卷讲解

1. 排序: 李顶为
2. 凸多边形直径: 毛一鸣
3. 随机算法: 黄秉焜
4. 计数: 张天昀
5. 哈希: 姜勇刚
6. 扩展二叉搜索树: 徐臣
7. 分治法 kd-tree: 鄢振宇

• 无

• 3-1-dp (Part I: Examples)
• 3-1-dp-handout (Part I: Examples)

• 通信系统

1. 吕云哲
2. 谢逸

• Bitonic euclidean traveling-salesman problem

1. 肖江
2. 姜勇刚

• Solution to the Bitonic Tour Problem
• Solving LIS in O(n log n) time

 学习如何深入浅出地讲解算法。

• 3-1-dp (Part II: "Theory")
• 3-1-dp-handout (Part II: "Theory")

• Huffman Codes

1. 张灵毓

• Tiling Path

1. 鄢振宇 (2班)

• 无

• 3-2-greedy
• 3-2-greedy-handout

• 图中顶点Merge 算法

1. 凌晨宇

• Chapter 4, Book "Algorithm Design" by Jon Kleinberg and Eva Tardos

 更多有些难度的贪心算法。学习如何分析并证明贪心算法的正确性。

• 3-2-amortized-analysis
• 3-2-amortized-analysis-handout

• 无

• Amortized Analysis Explained, Princeton, COS423

 进一步熟悉平摊分析的概念与应用。

• Paper: Amortized Computational Complexity (Robert Tarjan, 1985)

 Robert Tarjan 关于 Amortized Analysis 的论文。

• 3-2-amortized-analysis-part-II
• 3-2-amortized-analysis-part-II-handout

• LCA

1. 杜星亮
2. 彭翔宇

• Partition Refinement

1. 袁彦
2. 马常风

• Paper: Self-­Adjusting Binary Search Trees

 Robert Tarjan、Daniel Sleator 关于 Splay Tree 的论文。学习 Splay Tree 数据结构。学习平摊分析技术。

• MIT OCW on Self-organizing Lists

 强烈推荐。

• 3-5-mst
• 3-5-mst-handout

• Kruskal 算法和 Prim 算法的实现及其效率

1. 谢乃容
2. 刘恩萌

• 使用矩阵表示实现最小生成树算法

1. 何润雨
2. 殷兆恒

• CLRS Chapter 23: Minimum Spanning Trees
• [MIT 6.046J Design and Analysis of Algorithms, Spring 2015 (By Erik Demaine)](https://youtu.be/tKwnms5iRBU)

 体会不同的讲法。学习MST相关定理的证明技巧。