2017级--小班讨论 (第四学期)

学习周历

日期	论题	Open Topics (分班表)	扩展材料 (供感兴趣的同学自学使用)
2019-02-25	2017-3-final-exam.pdf 4-0-exam-scan	无	Robbins' Theorem on SCC Orientation Linear-time algorithm to find an odd-length cycle in a directed graph 不仅仅是判断有无，而是要找出一个（如果存在）有向奇圈。
2019-03-04	4-1-lp-1-scan	Pivot 操作 殷兆恒 黄秉焜 饲养成本问题 周涛 孙旭东	Chapter 7 of "Algorithms"（算法概论）By Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani 更深刻地理解 Simplex Method 与 Duality 理论 Chapter 8 of "Introduction to Linear Algebra (4th Edition)" By Gilbert Strang 初读不易理解；再读也不易理解; 一旦理解，受益匪浅。
2019-03-11	4-1-lp-2-scan	“移动”群之一 肖江 李顶为 “移动”群之二 谢乃容 郑奘巍	Section 8.7 of "Combinatorial Optimization" by Christos H. Papadimitriou, Kenneth Steiglitz Linear-inequality Feasibility 问题
2019-03-18	4-2-cyclic-group-scan	二阶魔方 姜勇刚 张灵毓 置换与逆序 刘寒 吕云哲	无
2019-03-25	4-3-dihedral-group-scan	群第二同构定理 凌晨宇 马常风 问题10中的结论 李博文 鄢振宇	Dihedra Group (by Keith Conrad) 关于 Dihedra Group 的更多内容
2019-04-01	4-4-direct-product 4-4-direct-product-handout 4-4-direct-product-scan	KMP 正确性 丁保荣 张天昀 字典树 彭翔宇 杜星亮
2019-04-08	4-5-polyhedral-group-I 4-5-polyhedral-group-I-handout 4-5-polyhedral-group-I-scan 4-5-polyhedral-group-II 4-5-polyhedral-group-II-handout	无	Subgroups of S4 S4 的所有子群以及它们之间错综复杂的关系
2019-04-15	4-grouptheory-isomorphism 4-grouptheory-isomorphism-handout 4-grouptheory-isomorphism-scan	Peano 公理 何润雨 殷天润 乘法算法 裴一凡 戴若石	On Cancellation in Groups 什么时候消去律成立?
2019-04-22	4-6-basic-number-theory-scan	加密、解密算法 袁彦 张廷昊 中国剩余定理 徐臣 张梓悦	Strong Duality for a Special Class of Integer Programs (Meyer 1977) 从“对偶”的角度看待 GCD
2019-04-29	4-7-number-theoretic-algorithms-scan	各种“花式”距离 裴明亮 谢逸 编码率 何伟 杨欣然	无
2019-05-06	4-8-rsa 4-8-rsa-handout	无	New Directions in Cryptography (1976) 提出密钥交换协议与公开密钥加密系统的革新性的论文 RSA: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems RSA 关于 RSA 的论文。 Attacks on RSA Cryptosystem (math.boisestate.edu) RSA 使用不当，容易遭致攻击。
2019-05-13	4-9-coding 4-9-coding-handout	Turing Machine 李凯旭 兰兆炜 SAT 陶绍诚 匡舒磊	A Mathematical Theory of Communication (Shannon 1948)
2019-05-20	4-11-p-np-I 4-11-p-np-I-handout	NP 定义 董杨静 桑百惠 TSP is in NPC 刘恩萌 毛一鸣	Reducibility Among Combinatorial Problems (Karp 1972） 经典论文。21 个 NPC 问题。
2019-05-27	4-11-p-np-II 4-11-p-np-II-handout	Δ-TSP 高天朗 王腾 SCP 毕秋宇 梁宇方	The History and Status of the P versus NP Question (STOC92, Michael Sipser) Godel's Letter
2019-06-03	4-12-approximation-algorithms 4-12-approximation-algorithms-handout	无	Classic Nintendo Games are Computationally Hard 超级玛丽是 NP-hard 的. (这事, 玛丽知道吗?) Super Mario Bros. Is Harder Easier than We Thought (Erik Demaine, FUN, 2016) 超级玛丽是 PSPACE-complete 的. (玛丽如果知道的话, 他还会去救公主吗?) A Survey on the Structure of Approximation Classes (CS Review 2010) 与近似算法相关的复杂度类; 不可近似结果
2019-06-10	4-13-randomized-algorithms 4-13-randomized-algorithms-handout	介绍 Example 5.2.2.5 中的协议 张扬播 邱凯 介绍 Algorithm 5.3.2.4 赵新榆 廖玺然 习题 5.2.2.7 顾宬 张昱东 习题 5.2.2.8 陈昱名 韩博	An Introduction to Randomized Algorithms (Richard Karp; Discrete Applied Mathematics, 1991) 经典的随机算法
2019-06-10	"多余的话" 4-overview 4-overview-handout	无	两年的课程结束了。感谢大家。祝大家学业有成。