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

来自问题求解
跳转至: 导航搜索

学习周历

日期 论题 Open Topics

(分班表)

扩展材料 (供感兴趣的同学自学使用)
2018-09-03
  • 问题求解第二学期期末试卷讲解
  1. 排序: 李顶为
  2. 凸多边形直径: 毛一鸣
  3. 随机算法: 黄秉焜
  4. 计数: 张天昀
  5. 哈希: 姜勇刚
  6. 扩展二叉搜索树: 徐臣
  7. 分治法 kd-tree: 鄢振宇
2018-09-17
  • 通信系统
  1. 吕云哲
  2. 谢逸
  • Bitonic euclidean traveling-salesman problem
  1. 肖江
  2. 姜勇刚
 学习如何深入浅出地讲解算法。
2018-09-27
  • Huffman Codes
  1. 张灵毓
  • Tiling Path
  1. 鄢振宇
2018-09-29
  • 图中顶点Merge 算法
  1. 凌晨宇
  • Chapter 4, Book "Algorithm Design" by Jon Kleinberg and Eva Tardos
 更多有些难度的贪心算法。学习如何分析并证明贪心算法的正确性。
2018-10-08
 进一步熟悉平摊分析的概念与应用。
 Robert Tarjan 关于 Amortized Analysis 的论文。
2018-10-15
  • LCA
  1. 杜星亮
  2. 彭翔宇
  • Partition Refinement
  1. 袁彦
  2. 马常风
 Robert Tarjan、Daniel Sleator 关于 Splay Tree 的论文。学习 Splay Tree 数据结构。学习平摊分析技术。
 强烈推荐。
2018-10-22
  • Kruskal 算法和 Prim 算法的实现及其效率
  1. 谢乃容
  2. 刘恩萌
  • 使用矩阵表示实现最小生成树算法
  1. 何润雨
  2. 殷兆恒
 体会不同的讲法。学习MST相关定理的证明技巧。
2018-10-29
  • DFS算法及其正确性
  1. 桑百惠
  2. 梁宇方
  • SCC算法正确性
  1. 王腾
  2. 郑奘巍
 Robert Tarjan 关于 DFS 在图算法中的应用的经典论文
2018-11-05
  • Bellman-Ford 算法输出负权环
  1. 张天昀
  2. 丁保荣
  • 使用 Fibonacci Heap 的 Dijkstra 算法的复杂度分析
  1. 毛一鸣
  2. 李顶为
 Robert Tarjan's Bicomponent Algorithm
2018-11-12
  • Floyd-Warshall 算法输出最短路径
  1. 周海波
  2. 李凯旭
  • 炼钢厂选址
  1. 徐臣
  2. 匡舒磊
2018-11-19
  • Block 算法
  1. 毕秋宇
  • 证明 Harary 图是r-连通的。
  1. 黄秉焜
 所有点对之间的最短路径问题的下界
2018-11-26
  • 竞赛图
  1. 何伟
  2. 殷天润
  • 循环赛排名方法
  1. 孙旭东
  2. 李博文
 关于连通度的算法。
2018-12-03
  • 点独立与点覆盖
  1. 刘寒
  2. 韩博
  • 点独立与点覆盖
  1. 杨欣然
2018-12-10
  • Ford-Fulkerson's Labeling Algorithm
  1. 张梓悦
  2. 周涛
  • 利用最大流算法证明 Hall 定理
  1. 裴一凡
  2. 董杨静
 有意思的 Stable Matching Problem
2018-12-17
  • Brooks 定理
  1. 张廷昊 裴明亮
  2. 高天朗、邱凯
  • Martin Gardner
  1. 赵新榆
  2. 兰兆炜
2018-12-24
  • LUP 分解算法的正确性
  1. 廖玺然
  2. 陶绍诚
  • LUP 分解求矩阵的行列式
  1. 张扬播
  2. 顾宬
Page 92、Page 93: 利用 Perfect Matching 解决 Chinese Postman Problem。
利用 Perfect Matching 求无向图(允许有负权边,但不允许有负圈)中的最短简单路径。
WARNING: 内有少量笔误,把它们找出来吧; 里面还有大量未加证明的论述,把它们证明了吧。然后,你就算真得懂了。
2018-12-29
  • 平面图与点着色
  • CZ 9.8、CZ 10.5
  1. 戴若石
  • CZ Theorem 10.10
  1. 陈昱名
  • Dilworth Theorem
  1. 殷兆恒
  2. 张博乔 (取消)