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

来自问题求解
跳转至： 导航、 搜索
小 （→‎学习周历）
Whf（讨论 | 贡献）
（→‎学习周历： +20180622）
 
（未显示同一用户的45个中间版本）
第6行： 第6行：
 
! Open Topics
 
! Open Topics
 
([[Media:Students-opentopics.pdf|分班表]])
 
([[Media:Students-opentopics.pdf|分班表]])
−
! 扩展材料
+
! 扩展材料 (供感兴趣的同学自学使用)
 
|-
 
|-
 
| style="width: 80px;" | 2018-03-05
 
| style="width: 80px;" | 2018-03-05
第57行： 第57行：
 
2018-03-26
 
2018-03-26
 
|
 
|
−
* 程序设计辅导 [[Media: ‎| ]]
+
* 程序设计辅导 (一)
 
|
 
|
 
* The twelvefold way (1)
 
* The twelvefold way (1)
第118行： 第118行：
 
* Alpha-Beta 剪枝
 
* Alpha-Beta 剪枝
 
# [[Media:OT2-Class1-Alphabeta-张博乔.pptx | 张博乔]]
 
# [[Media:OT2-Class1-Alphabeta-张博乔.pptx | 张博乔]]
−
# 郑奘巍
+
# [[Media:OT1-Class2-AlphaBeta-郑奘巍.zip | 郑奘巍]]
 
# [[Media:OT1-Class3-AlphaBeta-张天昀.pptx | 张天昀]]
 
# [[Media:OT1-Class3-AlphaBeta-张天昀.pptx | 张天昀]]
 
* SAT 求解算法
 
* SAT 求解算法
−
# 袁彦
+
# [[Media:OT2-Class1-SAT-袁彦.zip | 袁彦]]
 
# [[Media:OT2-Class2-SAT-李顶为.pptx | 李顶为]]
 
# [[Media:OT2-Class2-SAT-李顶为.pptx | 李顶为]]
 
# [[Media:OT2-Class3-SAT-杨欣然.pptx | 杨欣然]]
 
# [[Media:OT2-Class3-SAT-杨欣然.pptx | 杨欣然]]
 
|
 
|
−
* [http://The%20international%20SAT%20Competitions%20web%20page The international SAT Competitions]
+
* [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-Class2-Quicksort-陈昱名.pdf | 陈昱名]]
 +
# [[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:OT1-Class2-StackQueue-陶绍诚.pdf | 陶绍诚]] (二班)
 +
* Stack 实现的正确性
 +
** [[Media:OT2-Class2-Proof-姜勇刚.pptx | 姜勇刚]] (二班)
 +
|
 +
* [https://en.wikipedia.org/wiki/Probability_interpretations Probability interpretations (wiki)]
 +
    (阅读建议: 了解对于概率的多种解释方式。)
 +
* [[Media: Concrete_Mathematics_-_R._Graham,_D._Knuth,_O._Patashnik.pdf | Concrete Mathematics: A Foundation for Computer Science]] Sections 8.3 and 8.4
 +
    (阅读建议: Coin pattern 问题解析。)
 +
|-
 +
|
 +
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-Class-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
 +
# [[Media:OT1-Class3-Universal_Hashing-周涛.pdf | 周涛]]
 +
* Hashing 故事
 +
# [[Media:OT2-Class2-Hashing-Story-陈巍.pdf | 陈巍]]
 +
|
 +
* [[Media:Adversary_Arguments_(Jeff_2013).pdf | Adversary Arguments (Jeff 讲义)]]
 +
    (阅读建议: 理解 adversary arguments。理解讲义中的证明。)
 +
* [[Media:SB_-_Computer_Algorithms_-_Introduction_to_Design_and_Analysis_(3rd).pdf | Computer Algorithms - Introduction to Design and Analysis]]
 +
    (阅读建议: 第五章关于对手论证的内容。)
 +
* [[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 开始"。)
 +
|-
 +
|
 +
2018-06-07
 +
|
 +
* 程序设计辅导 (四)
 +
|
 +
* Splay tree
 +
** [[Media:OT1-Class1-Splay-杜星亮.pdf | 杜星亮]] (一班)
 +
** 孙旭东 (一班)
 +
* 中序遍历的正确性
 +
** 银加 (二班)
 +
** [[Media:OT2-Class2-Inorder-鄢振宇.zip | 鄢振宇]] (一班)
 +
|
 +
* 无
 +
|-
 +
|
 +
2018-06-20
 +
|
 +
* [[Media:2-11-heapsort.pdf|2-11-heapsort.pdf]]
 +
* [[Media:2-11-heapsort-handout.pdf|2-11-heapsort-handout.pdf]]
 +
* [[Media:Obama.zip | Obama.zip]]
 +
|
 +
* B 树插入算法对高度的影响
 +
** 黄秉焜 (二班)
 +
** 殷兆恒 (三班)
 +
* 介绍 B* 树
 +
** 邱凯 (二班) （临时取消）
 +
** 谢乃容 (三班)
 +
|
 +
* [[Media:The_Analysis_of_Heapsort_(Sedgewick_1992).pdf | The Analysis of Heapsort (Sedgewick 1992).pdf]]
 +
* [[Media:On_the_Best_Case_of_Heapsort_(1994).pdf | On the Best Case of Heapsort (1994).pdf]]
 +
    (阅读建议：了解 Heapsort average-case 和 best-case 的分析方法。)
 +
|-
 +
|
 +
2018-06-22
 +
|
 +
* 无 [Hash table, BST, RB-tree, and B tree] (临时补课)
 +
|
 +
* 无
 +
|
 +
* 无
 
|}
 
|}

2018年6月28日 (四) 20:42的最新版本

学习周历

日期 论题 Open Topics

(分班表)

扩展材料 (供感兴趣的同学自学使用)
2018-03-05

( 1-exam-handout.pdf)

  • 无
 
 (阅读目的: 学习 Cantor-Bernstein Theorem 的证明。)

2018-03-12

  • Insertion Sort
  1. 刘恩萌
  2. 姜勇刚
  3. 张天昀
  • Cyclic Hanoi
  1. 李凯旭
  2. 郑奘巍
  3. 董杨静
 
 (阅读目的: 了解 Hoare Logic。)

2018-03-19

  • Algorithmic Gap
  1. 王腾
  2. 李顶为
  3. 肖江
  • Asymptotic Notations
  1. 马常风
  2. 黄秉焜
  3. 吕云哲
 
 (阅读建议: 不必一次性读完 (这也不太现实); 
  先阅读第一章，从宏观角度理解循环不变式。
  再对照目录，在适当时候阅读相应算法。)

2018-03-26

  • 程序设计辅导 (一)
  • The twelvefold way (1)
  1. 高天朗
  2. 谢逸
  3. 何伟
  • The twelvefold way (2)
  1. 张廷昊
  2. 匡舒磊
  3. 殷天润
 
 (阅读建议: 每位同学(不仅是做 Open Topics 的同学)都读一读。) 

 (阅读建议: 阅读第 390 页。理解什么叫做 "indistinguishable"。)

2018-04-02

  • 证明 The Master Theorem
  1. 兰兆炜
  2. 吕云哲
  • 介绍 Akra–Bazzi Method
  1. 李博文
  2. 刘寒
 
 (阅读建议: 了解该方法。在本科阶段，不太用得着。大家以后做复杂的算法分析时（比如分析平均情况时间复杂度），可能会用得到。) 

 (阅读建议: 第三章。了解如何处理取整函数。要认识到：如果需要更精确的复杂度分析，我们是有相应的数学工具的。)

 (Paper for the "Treasure Hunt" section.)

2018-04-11

  • Josephus Problem
  1. 裴一凡
  2. 戴若石
  3. 毕秋宇
  • Generating Function
  1. 张灵毓
  2. 何润雨
  3. 丁保荣
 
 (阅读建议: 第七章 (7.2-7.5)。Generating Function。)

2018-04-16

  • 程序设计辅导 (二)
  • Alpha-Beta 剪枝
  1. 张博乔
  2. 郑奘巍
  3. 张天昀
  • SAT 求解算法
  1. 袁彦
  2. 李顶为
  3. 杨欣然

2018-04-18

  • 无 (临时习题课)
 
   (阅读建议: 了解 VLSI Layout 相关的更多有意思的结论与算法。(算法问题无处不在。))

   (阅读建议: Column 8 关于 Maximal-sum Subarray 问题的讨论。)

   (Paper and video for the "Treasure Hunt" section on mergesort.)

2018-04-23

  • 无 (两节习题讲解课)
 
   (阅读建议: 学习 Chapters 2, 3, 4; 了解各种类型的 Linear Recurrences 的解法。)

   (阅读建议: Chapter 39: How to Guard a Museum。)

2018-04-28

  • 程序设计辅导 (三)
  • Monty Hall Problem
  1. 李博文
  2. 毛一鸣
  3. 毕秋宇
  • TC Problem 5.2: Searching an unsorted array
  1. 许致明 ((f) 有误)
  2. 何润雨
  3. 殷兆恒
  • 无

2018-05-07

  • TC Problem 7.4: Stack depth for quicksort
  1. 徐臣
  2. 陈昱名
  3. 谢乃容
  • Random-Selection 算法的期望时间复杂度
  1. 鄢振宇
  2. 张扬播
  3. 韩博
 
   (阅读建议: 明确各种版本背后所基于的假设。)

   (阅读建议: 理解为什么"获取信息"的方式会影响最终的结果。)

2018-05-16 

   (阅读建议: 了解对于概率的多种解释方式。)

   (阅读建议: Coin pattern 问题解析。)

2018-05-21

  • 程序设计辅导 (四)
  • Heapsort vs. Quicksort 性能
  1. 张灵毓
  2. 凌晨宇
  3. 廖玺然
  • Binary tree => Heap => Priority queue
  1. 马常风
  2. 邱凯
  3. 肖江 肖江 handout ‎
 
   (阅读建议: 通过分析 Quicksort 感受算法分析的威力。)

2018-05-28

  • Universal Hashing
  1. 周涛
  • Hashing 故事
  1. 陈巍
 
   (阅读建议: 理解 adversary arguments。理解讲义中的证明。)

   (阅读建议: 第五章关于对手论证的内容。)

   (阅读建议: 了解该问题的不同变体，并尝试理解解题过程。)

2018-05-30

  • 无 (临时调课)
 
   (阅读建议: 学习 Dijkstra 如何说理。了解 "下标为何从 0 开始"。)

2018-06-07

  • 程序设计辅导 (四)
  • Splay tree
  • 中序遍历的正确性
  • 无

2018-06-20

  • B 树插入算法对高度的影响
    • 黄秉焜 (二班)
    • 殷兆恒 (三班)
  • 介绍 B* 树
    • 邱凯 (二班) （临时取消）
    • 谢乃容 (三班)
 
   (阅读建议：了解 Heapsort average-case 和 best-case 的分析方法。)

2018-06-22

  • 无 [Hash table, BST, RB-tree, and B tree] (临时补课)
  • 无
  • 无
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2017级--小班讨论_(第二学期)&oldid=2671”