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

来自问题求解
跳转至： 导航、 搜索
（→‎学习周历）
Whf（讨论 | 贡献）
（→‎学习周历）
 
（未显示同一用户的50个中间版本）
第20行： 第20行：
 
# 分治法 kd-tree: [[Media:7-鄢振宇.zip | 鄢振宇]]
 
# 分治法 kd-tree: [[Media:7-鄢振宇.zip | 鄢振宇]]
 
|
 
|
−
*  
+
* 无
 
|-
 
|-
 
| 2018-09-17
 
| 2018-09-17
 
|
 
|
 
* [[Media:3-1-dp.pdf ‎| 3-1-dp (Part I: Examples)]]
 
* [[Media:3-1-dp.pdf ‎| 3-1-dp (Part I: Examples)]]
 +
* [[Media:3-1-dp-part1-handout.pdf ‎| 3-1-dp-handout (Part I: Examples)]]
 
|
 
|
 
* 通信系统
 
* 通信系统
第30行： 第31行：
 
# [[Media:1-Comm-谢逸.pptx | 谢逸]]
 
# [[Media:1-Comm-谢逸.pptx | 谢逸]]
 
* Bitonic euclidean traveling-salesman problem
 
* Bitonic euclidean traveling-salesman problem
−
# 肖江
+
# [[Media:2-Bitonic-肖江.pdf | 肖江]]
 
# [[Media:2-Bitonic-姜勇刚.pptx | 姜勇刚]]
 
# [[Media:2-Bitonic-姜勇刚.pptx | 姜勇刚]]
 
|
 
|
第37行： 第38行：
 
   学习如何深入浅出地讲解算法。
 
   学习如何深入浅出地讲解算法。
 
|-
 
|-
 +
| 2018-09-27
 +
|
 +
* [[Media:3-1-dp-part2.pdf ‎| 3-1-dp (Part II: "Theory")]]
 +
* [[Media:3-1-dp-part2-handout.pdf ‎| 3-1-dp-handout (Part II: "Theory")]]
 +
|
 +
* Huffman Codes
 +
# [[Media:3-2-Huffman-张灵毓.pptx | 张灵毓]]
 +
* Tiling Path
 +
#
 +
# 鄢振宇
 +
|
 +
* 无
 +
|-
 +
| 2018-09-29
 +
|
 +
* [[Media:3-2-greedy.pdf ‎| 3-2-greedy]]
 +
* [[Media:3-2-greedy-handout.pdf ‎| 3-2-greedy-handout]]
 +
|
 +
* 图中顶点Merge 算法
 +
# [[Media:3-3-Merge-凌晨宇.zip|凌晨宇]]
 +
|
 +
* Chapter 4, Book "Algorithm Design" by Jon Kleinberg and Eva Tardos
 +
  更多有些难度的贪心算法。学习如何分析并证明贪心算法的正确性。
 +
|-
 +
| 2018-10-08
 +
|
 +
* [[Media:3-2-amortized-analysis.pdf ‎| 3-2-amortized-analysis]]
 +
* [[Media:3-2-amortized-analysis.pdf ‎| 3-2-amortized-analysis-handout]]
 +
|
 +
* 无
 +
|
 +
* [[Media:Amortized_Analysis_Explained_(Fiebrink).pdf ‎| Amortized Analysis Explained, Princeton, COS423]]
 +
  进一步熟悉平摊分析的概念与应用。
 +
* [[Media:Amortized_Computational_Complexity_(Robert_Tarjan,_1985).pdf ‎| Paper: Amortized Computational Complexity (Robert Tarjan, 1985)]]
 +
  Robert Tarjan 关于 Amortized Analysis 的论文。
 +
|-
 +
| 2018-10-15
 +
|
 +
* [[Media:3-2-amortized-analysis-part-II.pdf ‎| 3-2-amortized-analysis-part-II]]
 +
* [[Media:3-2-amortized-analysis-part-II-handout.pdf ‎| 3-2-amortized-analysis-part-II-handout]]
 +
|
 +
* LCA
 +
# [[Media:3-4-LCA-杜星亮.pdf | 杜星亮]]
 +
# [[Media:3-4-LCA-彭翔宇.pptx | 彭翔宇]]
 +
* Partition Refinement
 +
# [[Media:3-4-PartitionRefinement-袁彦.pptx | 袁彦]]
 +
# [[Media:3-4-PartitionRefinement-马常风.pptx | 马常风]]
 +
|
 +
* [[Media:Self-­Adjusting_Binary_Search_Trees_(Rober_Tarjan,_JACM85).pdf ‎| Paper: Self-­Adjusting Binary Search Trees]]
 +
  Robert Tarjan、Daniel Sleator 关于 Splay Tree 的论文。学习 Splay Tree 数据结构。学习平摊分析技术。
 +
* [https://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/lecture-14-competitive-analysis-self-organizing-lists/ MIT OCW on Self-organizing Lists]
 +
  强烈推荐。
 +
|-
 +
| 2018-10-22
 +
|
 +
* [[Media:3-5-mst.pdf ‎| 3-5-mst]]
 +
* [[Media:3-5-mst-handout.pdf ‎| 3-5-mst-handout]]
 +
|
 +
* Kruskal 算法和 Prim 算法的实现及其效率
 +
# [[Media:3-5-MST-Complexity-谢乃容.zip | 谢乃容]]
 +
# [[Media:3-5-MST-Complexity-刘恩萌.pdf | 刘恩萌]]
 +
* 使用矩阵表示实现最小生成树算法
 +
# [[Media:3-5-MST-MATRIX-何润雨.pptx | 何润雨]]
 +
# [[Media:3-5-MST-Matrix-殷兆恒.pptx | 殷兆恒]]
 +
|
 +
* CLRS Chapter 23: Minimum Spanning Trees
 +
* [https://youtu.be/tKwnms5iRBU MIT 6.046J Design and Analysis of Algorithms, Spring 2015 (By Erik Demaine)]
 +
  体会不同的讲法。学习MST相关定理的证明技巧。
 +
|-
 +
| 2018-10-29
 +
|
 +
* [[Media:3-6-graph-decomposition.pdf ‎| 3-6-graph-decomposition]]
 +
* [[Media:3-6-graph-decomposition-handout.pdf ‎| 3-6-graph-decomposition-handout]]
 +
|
 +
* DFS算法及其正确性
 +
# [[Media:3-6-DFS-桑百惠.pptx | 桑百惠]]
 +
# [[Media:3-6-DFS-梁宇方.zip | 梁宇方]]
 +
* SCC算法正确性
 +
# [[Media:3-6-SCC-王腾.pptx | 王腾]]
 +
# [[Media:3-6-SCC-郑奘巍.pdf | 郑奘巍]]
 +
|
 +
* [[Media:Depth-First_Search_and_Linear_Graph_Algorithms_(Tarjan_SIAM_1972).pdf | Paper: Depth-First Search and Linear Graph Algorithms (Tarjan SIAM 1972)]]
 +
  Robert Tarjan 关于 DFS 在图算法中的应用的经典论文
 +
|-
 +
| 2018-11-05
 +
|
 +
* [[Media:3-6-graph-decomposition-part-II.pdf ‎| 3-6-graph-decomposition-part-II]]
 +
* [[Media:3-6-graph-decomposition-part-II-handout.pdf ‎| 3-6-graph-decomposition-part-II-handout]]
 +
|
 +
* Bellman-Ford 算法输出负权环
 +
# [[Media:3-7-BellmanForm-张天昀.pdf | 张天昀]]
 +
# [[Media:3-7-BellmanFord-丁保荣.pdf | 丁保荣]]
 +
* 使用 Fibonacci Heap 的 Dijkstra 算法的复杂度分析
 +
# [[Media:3-7-DijkstraFibHeap-毛一鸣.zip | 毛一鸣]]
 +
# [[Media:3-7-DijkstraFibHeap-李顶为.pptx | 李顶为]]
 +
|
 +
* [[Media:Depth-First_Search_and_Linear_Graph_Algorithms_(Tarjan_SIAM_1972).pdf | Paper: Depth-First Search and Linear Graph Algorithms (Tarjan SIAM 1972)]]
 +
  Robert Tarjan's Bicomponent Algorithm
 +
|-
 +
| 2018-11-12
 +
|
 +
* [[Media:3-7-sssp.pdf ‎| 3-7-sssp]]
 +
* [[Media:3-7-sssp-handout.pdf ‎| 3-7-sssp-handout]]
 +
|
 +
* Floyd-Warshall 算法输出最短路径
 +
# [[Media:3-8-FloydWarshall-周海波.pptx | 周海波]]
 +
# [[Media:3-8-FloydWarshall-李凯旭.pptx | 李凯旭]]
 +
* 炼钢厂选址
 +
# [[Media:3-8-Location-徐臣.pptx | 徐臣]]
 +
# [[Media:3-8-Location-匡舒磊.pptx | 匡舒磊]]
 +
|
 +
* [[Media:An_Interview_with_Edsger_W._Dijkstra_(CACM_2010).pdf | An Interview with Edsger W. Dijkstra (CACM 2010).pdf]]
 +
|-
 +
| 2018-11-19
 +
|
 +
* [[Media:3-8-apsp.pdf ‎| 3-8-apsp]]
 +
* [[Media:3-8-apsp-handout.pdf ‎| 3-8-apsp-handout]]
 +
|
 +
* Block 算法
 +
#
 +
# [[Media:3-9-Block-毕秋宇.zip | 毕秋宇]]
 +
* 证明 Harary 图是r-连通的。
 +
# [[Media:3-9-HararyGraph-黄秉焜.pdf| 黄秉焜]]
 +
#
 +
|
 +
* [[Media:Cubic_Hardness_and_All-Pair_Shortest_Paths_(Algorithmic_Lower_Bounds,_Lecture_Note,_2014).pdf | Cubic Hardness and All-Pair Shortest Paths (Algorithmic Lower Bounds, Lecture Note, 2014).pdf]]
 +
  所有点对之间的最短路径问题的下界
 +
|-
 +
| 2018-11-26
 +
|
 +
* [[Media:3-9-connectivity-part-I.pdf ‎| 3-9-connectivity-part-I]]
 +
* [[Media:3-9-connectivity-part-I-handout.pdf ‎| 3-9-connectivity-part-I-handout]]
 +
|
 +
* 竞赛图
 +
# [[Media: 3-10-Hamilton-何伟.pptx | 何伟]]
 +
# [[Media:3-10-Hamilton-殷天润.pptx | 殷天润]]
 +
* 循环赛排名方法
 +
# [[Media: 3-10-Rank-孙旭东.pptx | 孙旭东]]
 +
# [[Media:3-10-Rank-李博文.pptx | 李博文]]
 +
|
 +
* [[Media:Connectivity_Algorithms_(cse.msu.edu).pdf | Connectivity Algorithms (cse.msu.edu).pdf]]
 +
  关于连通度的算法。
 +
|-
 +
| 2018-12-03
 +
|
 +
* [[Media:3-9-connectivity-part-II.pdf ‎| 3-9-connectivity-part-II: Menger Theorem]]
 +
* [[Media:3-9-connectivity-part-II-handout.pdf ‎| 3-9-connectivity-part-II-handout: Menger Theorem]]
 +
 +
* [[Media:3-10-traversability-part-I.pdf ‎| 3-10-traversability-part-I: Eulerian Graphs]]
 +
* [[Media:3-10-traversability-part-I-handout.pdf ‎| 3-10-traversability-part-I-handout: Eulerian Graphs]]
 +
|
 +
* 点独立与点覆盖
 +
# [[Media: 3-11-Cover-刘寒.pptx | 刘寒]]
 +
# [[Media:3-11-Cover-韩博.pptx | 韩博]]
 +
* 点独立与点覆盖
 +
# [[Media: 3-11-Konig-杨欣然.pptx | 杨欣然]]
 +
|
 +
* 无
 +
|-
 +
| 2018-12-10
 +
|
 +
* [[Media:3-10-traversability-part-II.pdf ‎| 3-10-traversability-part-II: Hamiltonian Graphs]]
 +
* [[Media:3-10-traversability-part-II-handout.pdf ‎| 3-10-traversability-part-II-handout: Hamiltonian Graphs]]
 +
* [[Media:3-11-matchings-factors-part-I.pdf ‎| 3-11-matchings-factors-part-I: Matchings and Covers]]
 +
* [[Media:3-11-matchings-factors-part-I-handout.pdf ‎| 3-11-matchings-factors-part-I-handout: Matchings and Covers]]
 +
|
 +
* Ford-Fulkerson's Labeling Algorithm
 +
# [[Media:3-12-FordFulkerson-张梓悦.pptx | 张梓悦]]
 +
# [[Media:3-12-FordFulkerson-周涛.pdf | 周涛]]
 +
* 利用最大流算法证明 Hall 定理
 +
# [[Media:3-12-NetworkFlowHall-裴一凡.pdf | 裴一凡]]
 +
# [[Media:3-12-NetworkFlowHall-董杨静.pdf | 董杨静]]
 +
|
 +
* [https://en.wikipedia.org/wiki/Stable_marriage_problem Stable marriage problem (wiki)]
 +
* [https://www.youtube.com/watch?v=Qcv1IqHWAzg Stable Marriage Problem@Numberphile@YouTube]
 +
  有意思的 Stable Matching Problem
 +
|-
 +
| 2018-12-17
 +
|
 +
* [[Media:3-12-network-flow.pptx | 3-12-network-flow.pptx]]
 +
|
 +
* Brooks 定理
 +
# [[Media:3-13-Brooks-张廷昊.pptx | 张廷昊]]、[[Media:3-13-Brooks-裴明亮.pdf | 裴明亮]]
 +
# [[Media: 3-13-Brooks-高天朗-邱凯.pptx | 高天朗、邱凯]]
 +
* Martin Gardner
 +
# [[Media:3-13-MartinGardner-赵新榆.pptx | 赵新榆]]
 +
# [[Media:3-13-MartinGardner-兰兆炜.pdf | 兰兆炜]]
 +
|
 +
* 无
 +
|-
 +
| 2018-12-24
 +
|
 +
* [[Media:3-11-matchings-factors-part-II.pdf ‎| 3-11-matchings-factors-part-II: Perfect Matchings]]
 +
* [[Media:3-11-matchings-factors-part-II-handout.pdf ‎| 3-11-matchings-factors-part-II-handout: Perfect Matchings]]
 +
|
 +
* LUP 分解算法的正确性
 +
# [[Media:3-14-LUP-Correctness-廖玺然.pptx | 廖玺然]]
 +
# [[Media:3-14-LUP-Correctness-陶绍诚.pptx | 陶绍诚]]
 +
* LUP 分解求矩阵的行列式
 +
# [[Media:3-14-LUP-Det-张扬播.pdf | 张扬播]]
 +
# [[Media:3-14-LUP-Det-顾宬.zip | 顾宬]]
 +
|
 +
* [[Media:Matching_Euler_Tours_and_the_Chinese_Postman_(Jack_Edmonds-Johnson,_1973).pdf | Matching Euler Tours and the Chinese Postman (Jack Edmonds-Johnson, 1973).pdf]]
 +
Page 92、Page 93: 利用 Perfect Matching 解决 Chinese Postman Problem。
 +
* [[Media:Shortest_Path_Algorithms_(math.sfu.ca,_Math_408,_Luis_Goddyn).pdf | Shortest Path Algorithms (math.sfu.ca, Math 408, Luis Goddyn).pdf]]
 +
利用 Perfect Matching 求无向图(允许有负权边，但不允许有负圈)中的最短简单路径。
 +
WARNING: 内有少量笔误，把它们找出来吧; 里面还有大量未加证明的论述，把它们证明了吧。然后，你就算真得懂了。
 +
|-
 +
| 2018-12-29
 +
|
 +
* 平面图与点着色
 +
|
 +
* CZ 9.8、CZ 10.5
 +
# [[Media:3-15-HW-戴若石.pdf | 戴若石]]
 +
* CZ Theorem 10.10
 +
# [[Media:3-15-Coloring-陈昱名.zip | 陈昱名]]
 +
* Dilworth Theorem
 +
# [[Media:3-15-DilworthTheorem-殷兆恒.zip | 殷兆恒]]
 +
# 张博乔 （取消）
 +
|
 +
* [[Media:Equivalence_of_Seven_Major_Theorems_in_Combinatorics_(Robert_Borgersen,_2004).pdf | Equivalence of Seven Major Theorems in Combinatorics (Robert Borgersen, 2004).pdf]]
 
|}
 
|}

2019年1月2日 (三) 10:31的最新版本

学习周历

日期 论题 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
  2. 鄢振宇
  • 无
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 算法
  2. 毕秋宇
  • 证明 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. 张博乔 （取消）
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2017级--小班讨论_(第三学期)&oldid=3043”