查看“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
# 鄢振宇 (2班)
|
* 无
|-
| 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:An_Interview_with_Edsger_W._Dijkstra_(CACM_2010).pdf | An_Interview_with_Edsger_W._Dijkstra_(CACM_2010).pdf]]
|-
|}