查看“2017级--小班讨论 (第二学期)”的源代码
←
2017级--小班讨论 (第二学期)
跳转至:
导航
、
搜索
因为以下原因,您没有权限编辑本页:
您所请求的操作仅限于该用户组的用户使用:
用户
您可以查看与复制此页面的源代码。
== 学习周历 == {| border=1 ! 日期 ! 论题 ! Open Topics ([[Media:Students-opentopics.pdf|分班表]]) ! 扩展材料 (供感兴趣的同学自学使用) |- | style="width: 80px;" | 2018-03-05 | * [[Media:1-exam.pdf | 1-exam.pdf]] ([[Media:1-exam-handout.pdf | 1-exam-handout.pdf]]) | * 无 | * [https://en.wikipedia.org/wiki/Schr%C3%B6der%E2%80%93Bernstein_theorem Cantor-Bernstein Theorem@wiki] (阅读目的: 学习 Cantor-Bernstein Theorem 的证明。) |- | 2018-03-12 | * [[Media:2-1-correctness.pdf | 2-1: 算法的正确性]] | * Insertion Sort # [[Media:OT1-Class1-刘恩萌-InsertionSort.pptx | 刘恩萌]] # [[Media:OT1-Class2-姜勇刚-插入排序的正确性证明.pptx | 姜勇刚]] # [[Media:OT1-Class3-张天昀-插入排序正确性证明.pdf | 张天昀]] * Cyclic Hanoi # [[Media:OT2-Class1-李凯旭-CyclicHanoi.pptx | 李凯旭]] # [[Media:OT2-Class2-郑奘巍-CyclicHanoi.pdf | 郑奘巍]] # [[Media:OT2-Class3-董杨静-CyclicHanoi.pdf | 董杨静]] | * [https://en.wikipedia.org/wiki/Hoare_logic Hoare Logic@wiki]: [[Media:An_Axiomatic_Basis_for_Computer_Programming_(Hoare_CACM69).pdf | An Axiomatic Basis for Computer Programming (Hoare CACM69).pdf]] (阅读目的: 了解 Hoare Logic。) |- | 2018-03-19 | * [[Media:2-1-算法的正确性(2).pdf | 2-1: 算法的正确性 (2)]] | * Algorithmic Gap # [[Media:OT1-Class1-王腾-AlgorithmicGap.pptx|王腾]] # [[Media:OT1-Class2-李顶为-AlgorithmicGap.pptx|李顶为]] # [[Media:OT1-Class3-肖江-AlgorithmicGap.zip|肖江]] * Asymptotic Notations # [[Media:OT2-Class1-马常风-AsymptoticNotations.pptx|马常风]] # [[Media:OT2-Class2-黄秉焜-AsymptoticNotations.pptx|黄秉焜]] # [[Media:OT2-Class3-吕云哲-AsymptoticNotations.pptx|吕云哲]] | * [[Media:ArXiv12_1211.4470_(CSUR12)_Loop_Invariants_Analysis_Classification_and_Examples.pdf | Paper: Loop Invariants: Analysis, Classification, and Examples.pdf]] (阅读建议: 不必一次性读完 (这也不太现实); 先阅读第一章,从宏观角度理解循环不变式。 再对照目录,在适当时候阅读相应算法。) |- | 2018-03-26 | * 程序设计辅导 (一) | * The twelvefold way (1) # [[Media:OT2-Class1-高天朗-12way-part1.pptx | 高天朗]] # [[Media:OT1-Class2-谢逸-12way-part1.pptx | 谢逸]] # [[Media:OT1-Class3-何伟-12way-part1.pptx | 何伟]] * The twelvefold way (2) # [[Media:OT2-Class1-张廷昊-12way-part2.pptx | 张廷昊]] # [[Media:OT2-Class2-匡舒磊-part2.pptx | 匡舒磊]] # [[Media:OT2-Class3-殷天润-12way-part2.pptx | 殷天润]] | * [https://en.wikipedia.org/wiki/Twelvefold_way Twelvefold Way (wiki)] [http://tcs.nju.edu.cn/wiki/index.php/%E7%BB%84%E5%90%88%E6%95%B0%E5%AD%A6_(Spring_2015)/Basic_enumeration Basic Enumeration (尹一通老师 “组合数学” 课程讲义)] (阅读建议: 每位同学(不仅是做 Open Topics 的同学)都读一读。) * [[Media:The_Art_of_Computer_Programmin_Volume4A_Combinatorial_Algorithms.pdf | The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1]] (阅读建议: 阅读第 390 页。理解什么叫做 "indistinguishable"。) |- | 2018-04-02 | * [[Media:2-2-efficiency.pdf | 2-2-efficiency.pdf]] * [[Media:2-2-efficiency-handout.pdf | 2-2-efficiency-handout.pdf]] | * 证明 The Master Theorem # [[Media:OT1-Class1-兰兆炜-Master-Theorem.pptx | 兰兆炜]] # [[Media:OT1-Class3-吕云哲-Master-Theorem.pptx | 吕云哲]] * 介绍 Akra–Bazzi Method # [[Media:OT2-Class1-李博文-Akra-Bazzi-Method.pptx | 李博文]] # [[Media:OT2-Class3-刘寒-Akra-Bazzi-Method.pptx | 刘寒]] | * [[Media:On_the_Solution_of_Linear_Recurrence_Equations_(Akra_and_Bazzi_1998).pdf | Paper: On the Solution of Linear Recurrence Equations (Akra and Bazzi, 1998)]] (阅读建议: 了解该方法。在本科阶段,不太用得着。大家以后做复杂的算法分析时(比如分析平均情况时间复杂度),可能会用得到。) * [[Media: Concrete_Mathematics_-_R._Graham,_D._Knuth,_O._Patashnik.pdf | Concrete Mathematics. R. Graham, D. Knuth, O. Patashnik.pdf]] (阅读建议: 第三章。了解如何处理取整函数。要认识到:如果需要更精确的复杂度分析,我们是有相应的数学工具的。) * [[Media: Finding_Repeated_Elements_(Misra_1982).pdf | Paper: Finding Repeated Elements (Misra, 1982).pdf]] (Paper for the "Treasure Hunt" section.) |- | 2018-04-11 | * [[Media:2-3-counting.pdf | 2-3-counting.pdf]] * [[Media:2-3-counting-handout.pdf | 2-3-counting-handout.pdf]] | * Josephus Problem # [[Media:OT1-Class1-Josephus-裴一凡.pptx | 裴一凡]] # [[Media:OT1-Class2-Josephus-戴若石.pptx | 戴若石]] # [[Media:OT1-Class3-Josephus-毕秋宇.pptx | 毕秋宇]] * Generating Function # [[Media:OT2-Class1-generating function-张灵毓.pptx | 张灵毓]] # [[Media:OT2-Class2-GeneratingFunction-何润雨.pptx | 何润雨]] # [[Media:OT2-Class3-GeneratingFunction-丁保荣.pdf | 丁保荣]] | * [[Media: Concrete_Mathematics_-_R._Graham,_D._Knuth,_O._Patashnik.pdf | Concrete Mathematics. R. Graham, D. Knuth, O. Patashnik.pdf]] (阅读建议: 第七章 (7.2-7.5)。Generating Function。) |- | 2018-04-16 | * 程序设计辅导 (二) | * Alpha-Beta 剪枝 # [[Media:OT2-Class1-Alphabeta-张博乔.pptx | 张博乔]] # [[Media:OT1-Class2-AlphaBeta-郑奘巍.zip | 郑奘巍]] # [[Media:OT1-Class3-AlphaBeta-张天昀.pptx | 张天昀]] * SAT 求解算法 # [[Media:OT2-Class1-SAT-袁彦.zip | 袁彦]] # [[Media:OT2-Class2-SAT-李顶为.pptx | 李顶为]] # [[Media:OT2-Class3-SAT-杨欣然.pptx | 杨欣然]] | * [http://www.satcompetition.org/ The international SAT Competitions] |- | 2018-04-18 | * [[Media:2-4-recurrences.pdf | 2-4-recurrences]] * [[Media:2-4-recurrences-handout.pdf | 2-4-recurrences-handout]] | * 无 (临时习题课) | * [[Media:TR89_(MIT_Charles_Leiserson)_VLSI_Theory_and_Parallel_Supercomputing.pdf | Paper: TR89 (MIT Charles Leiserson) VLSI Theory and Parallel Supercomputing.pdf]] (阅读建议: 了解 VLSI Layout 相关的更多有意思的结论与算法。(算法问题无处不在。)) * [[Media:Programming_Pearls_(Second_Edition_Jon_Bentley).pdf | Book: Programming Pearls (Second Edition Jon Bentley).pdf]] (阅读建议: Column 8 关于 Maximal-sum Subarray 问题的讨论。) * [[Media:Mellin_Transforms_and_Asymptotics_The_Mergesort_Recurrence_(Flajolet_1994).pdf | Mellin Transforms and Asymptotics: The Mergesort Recurrence (Flajolet 1994).pdf]] * [[Media:2-4_Mergesort.mp4.zip | Mergesort (Video)]] (Paper and video for the "Treasure Hunt" section on mergesort.) |- | 2018-04-23 | * [[Media:2-5-recursion.pdf | 2-5-recursion]] * [[Media:2-5-recursion-handout.pdf | 2-5-recursion-handout]] | * 无 (两节习题讲解课) | * [[Media:An_Introduction_to_the_Analysis_of_Algorithms_(2nd_Edition_Robert_Sedgewick,_Philippe_Flajolet).pdf | Book: An Introduction to the Analysis of Algorithms (2nd Edition Robert Sedgewick, Philippe Flajolet).pdf]] (阅读建议: 学习 Chapters 2, 3, 4; 了解各种类型的 Linear Recurrences 的解法。) * [[Media:Proofs_from_THE_BOOK_(Fifth_Edition_2014).pdf | Book: Proofs from THE BOOK (Fifth Edition 2014).pdf]] (阅读建议: Chapter 39: How to Guard a Museum。) |- | 2018-04-28 | * 程序设计辅导 (三) | * Monty Hall Problem # [[Media:OT1-Class1-MontyHall-李博文.pptx | 李博文]] # [[Media:OT1-Class2-MontyHall-毛一鸣.zip | 毛一鸣]] # [[Media:OT1-Class3-Monty Hall-毕秋宇.pptx | 毕秋宇]] * TC Problem 5.2: Searching an unsorted array # [[Media:OT2-Class1-Search-许致明.pptx | 许致明]] ((f) 有误) # [[Media:OT2-Class2-Search-何润雨.pptx | 何润雨]] # [[Media:OT2-Class3-Search-殷兆恒.pptx | 殷兆恒]] | * 无 |- | 2018-05-07 | * [[Media:2-7-discrete-probability.pdf | 2-7-discrete-probability]] * [[Media:2-7-discrete-probability-handout.pdf | 2-7-discrete-probability-handout]] | * TC Problem 7.4: Stack depth for quicksort # [[Media:OT1-Class1-Quicksort-徐臣.pptx | 徐臣]] # 陈昱名 # [[Media:OT1-Class3-Quicksort-谢乃容.pptx | 谢乃容]] * Random-Selection 算法的期望时间复杂度 # [[Media:OT2-Class1-Selection-鄢振宇.zip | 鄢振宇]] # [[Media:OT2-Class2-Selection-张扬播.pdf | 张扬播]] # [[Media:OT2-Class3-Selection-韩博.pdf | 韩博]] | * [https://en.wikipedia.org/wiki/Monty_Hall_problem Monty Hall problem (wiki)] (阅读建议: 明确各种版本背后所基于的假设。) * [https://en.wikipedia.org/wiki/Boy_or_Girl_paradox Boy or Girl paradox (wiki)] (阅读建议: 理解为什么"获取信息"的方式会影响最终的结果。) |- | 2018-05-16 | * [[Media:2-8-probabilistic-analysis.pdf | 2-8-probabilistic-analysis]] * [[Media:2-8-probabilistic-analysis-handout.pdf | 2-8-probabilistic-analysis-handout]] | * A Stack, Two Queues ** [[Media: | 陶绍诚]] (二班) * Stack 实现的正确性 ** [[Media:OT2-Class2-Proof-姜勇刚.pptx | 姜勇刚]] (二班) | * [https://en.wikipedia.org/wiki/Probability_interpretations Probability interpretations (wiki)] (阅读建议: 了解对于概率的多种解释方式。) |- | 2018-05-21 | * 程序设计辅导 (四) | * Heapsort vs. Quicksort 性能 # [[Media:OT1-Class1-Quicksort-Heapsort-张灵毓.pptx | 张灵毓]] # [[Media:OT1-Class2-Quicksort-Heapsort-凌晨宇.zip | 凌晨宇]] # [[Media:OT1-Class3-Quicksort-Heapsort-廖玺然.pdf | 廖玺然]] * Binary tree => Heap => Priority queue # [[Media:OT2-Class1-Priority-Queue-马常风.pptx | 马常风]] # 邱凯 # [[Media:OT2-Class3-Priority-Queue-肖江.pdf | 肖江]] [[Media:OT2-Class3-Priority-Queue-handout-肖江.pdf | 肖江 handout]] | * [[Media:The_Analysis_of_Quicksort_Programs_(Sedgewick).pdf | The Analysis of Quicksort Programs (Sedgewick)]] (阅读建议: 通过分析 Quicksort 感受算法分析的威力。) |- | 2018-05-28 | * [[Media:2-9-sorting-selection.pdf|2-9-sorting-selection.pdf]] * [[Media:2-9-sorting-selection-handout.pdf|2-9-sorting-selection-handout.pdf]] | * Universal Hashing # 周涛 * Hashing 故事 # 陈巍 | * [[Media:Adversary_Arguments_(Jeff_2013).pdf | Adversary Arguments (Jeff 讲义)]] (阅读建议: 理解 adversary arguments。理解讲义中的证明。) * [[Media:The Coupon Collectors Problem (MAT2, 2015).pdf | The Coupon Collector's Problem (MAT2, 2015)]] (阅读建议: 了解该问题的不同变体,并尝试理解解题过程。) |- | 2018-05-30 | * [[Media:2-10-data-structures.pdf|2-10-data-structure.pdf]] * [[Media:2-10-data-structures-handout.pdf|2-10-data-structures-handout.pdf]] | * 无 (临时调课) | * [[Media:EWD831_Why_Numbering_Should_Start_at_Zero.PDF | Why Numbering Should Start at Zero (EWD831)]] (阅读建议: 学习 Dijkstra 如何说理。了解 "下标为何从 0 开始"。) |}
返回至
2017级--小班讨论 (第二学期)
。
导航菜单
个人工具
登录
命名空间
页面
讨论
变种
视图
阅读
查看源代码
查看历史
更多
搜索
导航
首页
最近更改
随机页面
帮助
工具
链入页面
相关更改
特殊页面
页面信息