查看“2017级--小班讨论 (第三学期)”的源代码
←
2017级--小班讨论 (第三学期)
跳转至：
导航
、
搜索
因为以下原因，您没有权限编辑本页：
您所请求的操作仅限于该用户组的用户使用：
用户
您可以查看与复制此页面的源代码。
== 学习周历 == {| border=1 ! 日期 ! 论题 ! Open Topics ([[Media:Ot-classes.pdf|分班表]]) ! 扩展材料 (供感兴趣的同学自学使用) |- | style="width: 80px;" | 2018-09-03 | * 问题求解第二学期期末试卷讲解 | # 排序: [[Media:1-李顶为.pptx | 李顶为]] # 凸多边形直径: [[Media:2-毛一鸣.zip | 毛一鸣]] # 随机算法: [[Media:3-黄秉焜.zip | 黄秉焜]] # 计数: [[Media:4-张天昀.pdf | 张天昀]] # 哈希: [[Media:5-Hashing.pdf | 姜勇刚]] # 扩展二叉搜索树: [[Media:6-徐臣.pptx | 徐臣]] # 分治法 kd-tree: [[Media:7-鄢振宇.zip | 鄢振宇]] | * 无 |- | 2018-09-17 | * [[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)]] | * 通信系统 # [[Media:1-Comm-吕云哲.pptx | 吕云哲]] # [[Media:1-Comm-谢逸.pptx | 谢逸]] * Bitonic euclidean traveling-salesman problem # [[Media:2-Bitonic-肖江.pdf | 肖江]] # [[Media:2-Bitonic-姜勇刚.pptx | 姜勇刚]] | * [[Media:Bitonic_Tour_CLRS_Solution.pdf | Solution to the Bitonic Tour Problem]] * [http://qr.ae/TUNEQk Solving LIS in O(n log n) time] 学习如何深入浅出地讲解算法。 |- | 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]] |}
返回至
2017级--小班讨论 (第三学期)
。
导航菜单
个人工具
登录
命名空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
首页
最近更改
随机页面
帮助
工具
链入页面
相关更改
特殊页面
页面信息
