2017级--小班讨论 (第三学期)

学习周历

日期	论题	Open Topics (分班表)	扩展材料 (供感兴趣的同学自学使用)
2018-09-03	问题求解第二学期期末试卷讲解	排序: 李顶为 凸多边形直径: 毛一鸣 随机算法: 黄秉焜 计数: 张天昀 哈希: 姜勇刚 扩展二叉搜索树: 徐臣 分治法 kd-tree: 鄢振宇	无
2018-09-17	3-1-dp (Part I: Examples) 3-1-dp-handout (Part I: Examples)	通信系统 吕云哲 谢逸 Bitonic euclidean traveling-salesman problem 肖江 姜勇刚	Solution to the Bitonic Tour Problem Solving LIS in O(n log n) time 学习如何深入浅出地讲解算法。
2018-09-27	3-1-dp (Part II: "Theory") 3-1-dp-handout (Part II: "Theory")	Huffman Codes 张灵毓 Tiling Path 鄢振宇	无
2018-09-29	3-2-greedy 3-2-greedy-handout	图中顶点Merge 算法 凌晨宇	Chapter 4, Book "Algorithm Design" by Jon Kleinberg and Eva Tardos 更多有些难度的贪心算法。学习如何分析并证明贪心算法的正确性。
2018-10-08	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 的论文。
2018-10-15	3-2-amortized-analysis-part-II 3-2-amortized-analysis-part-II-handout	LCA 杜星亮 彭翔宇 Partition Refinement 袁彦 马常风	Paper: Self-­Adjusting Binary Search Trees Robert Tarjan、Daniel Sleator 关于 Splay Tree 的论文。学习 Splay Tree 数据结构。学习平摊分析技术。 MIT OCW on Self-organizing Lists 强烈推荐。
2018-10-22	3-5-mst 3-5-mst-handout	Kruskal 算法和 Prim 算法的实现及其效率 谢乃容 刘恩萌 使用矩阵表示实现最小生成树算法 何润雨 殷兆恒	CLRS Chapter 23: Minimum Spanning Trees MIT 6.046J Design and Analysis of Algorithms, Spring 2015 (By Erik Demaine) 体会不同的讲法。学习MST相关定理的证明技巧。
2018-10-29	3-6-graph-decomposition 3-6-graph-decomposition-handout	DFS算法及其正确性 桑百惠 梁宇方 SCC算法正确性 王腾 郑奘巍	Paper: Depth-First Search and Linear Graph Algorithms (Tarjan SIAM 1972) Robert Tarjan 关于 DFS 在图算法中的应用的经典论文
2018-11-05	3-6-graph-decomposition-part-II 3-6-graph-decomposition-part-II-handout	Bellman-Ford 算法输出负权环 张天昀 丁保荣 使用 Fibonacci Heap 的 Dijkstra 算法的复杂度分析 毛一鸣 李顶为	Paper: Depth-First Search and Linear Graph Algorithms (Tarjan SIAM 1972) Robert Tarjan's Bicomponent Algorithm
2018-11-12	3-7-sssp 3-7-sssp-handout	Floyd-Warshall 算法输出最短路径 周海波 李凯旭 炼钢厂选址 徐臣 匡舒磊	An Interview with Edsger W. Dijkstra (CACM 2010).pdf
2018-11-19	3-8-apsp 3-8-apsp-handout	Block 算法 毕秋宇 证明 Harary 图是r-连通的。 黄秉焜	Cubic Hardness and All-Pair Shortest Paths (Algorithmic Lower Bounds, Lecture Note, 2014).pdf 所有点对之间的最短路径问题的下界
2018-11-26	3-9-connectivity-part-I 3-9-connectivity-part-I-handout	竞赛图 何伟 殷天润 循环赛排名方法 孙旭东 李博文	Connectivity Algorithms (cse.msu.edu).pdf 关于连通度的算法。
2018-12-03	3-9-connectivity-part-II: Menger Theorem 3-9-connectivity-part-II-handout: Menger Theorem 3-10-traversability-part-I: Eulerian Graphs 3-10-traversability-part-I-handout: Eulerian Graphs	点独立与点覆盖 刘寒 韩博 点独立与点覆盖 杨欣然	无
2018-12-10	3-10-traversability-part-II: Hamiltonian Graphs 3-10-traversability-part-II-handout: Hamiltonian Graphs 3-11-matchings-factors-part-I: Matchings and Covers 3-11-matchings-factors-part-I-handout: Matchings and Covers	Ford-Fulkerson's Labeling Algorithm 张梓悦 周涛 利用最大流算法证明 Hall 定理 裴一凡 董杨静	Stable marriage problem (wiki) Stable Marriage Problem@Numberphile@YouTube 有意思的 Stable Matching Problem
2018-12-17	3-12-network-flow.pptx	Brooks 定理 张廷昊、 裴明亮 高天朗、邱凯 Martin Gardner 赵新榆 兰兆炜	无
2018-12-24	3-11-matchings-factors-part-II: Perfect Matchings 3-11-matchings-factors-part-II-handout: Perfect Matchings	LUP 分解算法的正确性 廖玺然 陶绍诚 LUP 分解求矩阵的行列式 张扬播 顾宬	Matching Euler Tours and the Chinese Postman (Jack Edmonds-Johnson, 1973).pdf Page 92、Page 93: 利用 Perfect Matching 解决 Chinese Postman Problem。 Shortest Path Algorithms (math.sfu.ca, Math 408, Luis Goddyn).pdf 利用 Perfect Matching 求无向图(允许有负权边，但不允许有负圈)中的最短简单路径。 WARNING: 内有少量笔误，把它们找出来吧; 里面还有大量未加证明的论述，把它们证明了吧。然后，你就算真得懂了。
2018-12-29	平面图与点着色	CZ 9.8、CZ 10.5 戴若石 CZ Theorem 10.10 陈昱名 Dilworth Theorem 殷兆恒 张博乔 （取消）	Equivalence of Seven Major Theorems in Combinatorics (Robert Borgersen, 2004).pdf