主题:
动态规划及优化

题目:
There is a tower of n floors, and an egg dropper with m ideal eggs. The physical properties of the ideal egg is such that it will shatter if it is dropped from floor n* or above, and will have no damage whatsoever if it is dropped from floor n* - 1 or below. The problem is to find a strategy such that the egg dropper can determine the floor n* in as few egg drops as possible.

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
从 O(n^2m) 的 DP 可以优化到 O(sqrt(n))，换一种思路又可以优化到 O(lgn)。
有点复杂但很有趣。

题解:
Egg Dropping _ Brilliant Math & Science Wiki
优化，再优化！——从《鹰蛋》一题浅析对动态规划算法的优化（IOI2004 国家集训队论文 朱晨光）

参考资料:
https://en.wikipedia.org/wiki/Dynamic_programming#Egg_dropping_puzzle

主题:
数论/抽象代数

题目:
对于一个群G, 若有

且
都为质数
则必存在元素a≠e
|a|=k

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
书上有k=3时的特殊情况。虽然特殊情况有一个非常漂亮的证明，但是对一般情况我们可以有更好的结论

题解:
选择G中的一个元素e,
如果任意p_i都不整除|e|, 那么k仍然整除得到的商群的阶(order)
考虑G模e得到的商群(记作G')，它的阶更小，且仍然满足题设条件
如果存在p_i整除|e|， 那么必有e的c次方，使得|e^c|=p_i
那么考虑G模e^c得到的商群(记作G')，它的阶更小，且k'=k/p_i也更小
因此，在有限步操作之后，我们可以规约到k'=|G'|=1的情况
则之前模掉的所有因子的乘积的阶必为k

参考资料:

其它:

现为以下题目征集答案:

• 5-10: Palindrome Pal1(S)
• 5-12: Palindrome Pal2(S)
• Euclid 递归算法的正确性 (未完成, 待补充)

• 哈希表均匀采样 (TC 11.2-6) [10]
  • 采样算法
  • 复杂度分析
  • 正确性证明

主题:
正则表达式、CNF（上下文无关文法）、CSF（上下文相关/敏感文法）

题目:
简单描述人类语言（自然语言）、正则表达式、CNF、CSF之间的共同点和不同点
简单示范三种文法如何生成语言内的语句
并阐述清
“正则表达式无法计数。CNF可以计数，但仅能对单个元素计数。CSF可以对多个元素计数”
并结合“正则表达式与自动机”，阐述为何大多情况下使用正则表达式
习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
为《编译原理》课程打下一定基础
增强对不同文法的理解，以及正则表达式这一时间和表达能力互相妥协的产物
题解:

参考资料:

其它:

主题:
Coq
数学归纳法

题目:
Coq的induct的归纳对应什么样的数学归纳法？
在Coq中，如果我们定义了
Inductive arith : Set :=
| Const (n : nat)
| Variable (x : string)
| Plus (e1 e2 : arith)
| Minus (e1 e2 : arith)
| Times (e1 e2 : arith).

那么，如果我们在证明forall a : arith, P(a)
的时候，如果我们使用intros. induct a.
我们会得到5个sbugoals.
其中，在证明Plus时，我们要证明的东西类似于
IHa1 : P(a1)
IHa2 : P(a2)
subgoal : P(Plus a1 a2)
问题来了，我们在证明Plus的时候，并没有证明过归纳法对于Minus和Times成立呀？如果a1和a2是Minus或者Times怎么办呢？
更进一步，如果因为Coq的这个“疏忽”，我们在证Plus时用到了Minus的性质，在证Minus时用到了Plus的性质，不就变成循环论证了吗？这该怎么办呢？

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
Coq的induct中提到的rank概念在很多计算机领域中有所涉及，很多时候我们用一些比较模糊的rank函数对一类东西进行排序，可以得到很好的结果
题解:
Coq对于递归类型是非常严格的。Coq中可以定义的递归类型的每一个成员，都是可以通过有限个constructor构成的。
那么，这意味着什么呢？
意味着我们可以给每个成员赋一个值，不妨记作rank（秩）
所有不通过递归得到的成员，rank设为1.（如例子中的Const和Variable）
所有通过递归得到的表达式a，必然可以写作Constructor(subterm1 subterm2 ... subtermN)
我们定义rank(a) = max(rank(subterm1), rank(subterm2), ... rank(subtermN)) + 1
然后再回到这题。我们其实是在对表达式的秩（它的构造函数的最大深度）做递归！我们在证明Plus的时候，可以尽情使用Minus, Times的性质，因为我们真正在证明的，是如果所有秩为k的表达式如果都有P性质，那么所有秩为k+1的表达式也都有P性质！
这样一来，就不会出现交叉论证啦！

参考资料:

其它:
可延展内容（附简答）：
在考虑秩的定义时，如果涉及多个递归类型，能不能只考虑自己？
比如有两个递归类型Recur1, Recur2
Recur1有一个constructor是
Combine Recur1 Recur1 Recur2
如果我们定义a = Combine r1 r2 r3的秩为max(rank(r1), rank(r2)) + 1

• 这种定义和定义max(rank(r1), rank(r2), rank(r3) ) + 1有没有区别呢？（显然是有区别的）
• 这样定义秩会不会有问题呢？（在Coq语法内不会）
• 会不会影响我们在草稿纸上的证明过程呢？（不会）
• {简单介绍}这样定义秩其实和我们把rank(nat)认为是1一样是一种无伤大雅的简化。

有什么样的递归类型，会让我们无法使用秩来做归纳呢？（我还没想到，但应该是存在的）
如果存在这样的递归类型，有没有办法证明Coq语法中，永远无法定义这样的类型呢？

说明:

• [0.5] 表示该题可用来顶替一半需要订正的题目
• [1] 表示该题可用来顶替所有需要订正的题目
• 如果超额高质量完成，[0.5] 可提升为 [1]
• 在下面留言领取题目
• 本替代方案截止日期可适当放宽（但需有基本的进度保证）
• 累计领取题目数/人数统计：6/6

要求:

• 中英文都可以
• 逻辑清晰。鼓励自主思考、鼓励自行扩展题目。
• 参考: 2-1-correctness.pdf

2-2 (算法的效率)

• 凸多边形直径问题 [0.5]
  • 算法 + 正确性证明
  • 参考: 习题课课件
• 平面上最近点对问题 [1]
  • 算法 + 正确性证明
  • 参考: CLRS 33.4
  • By 殷兆恒

2-3 (计数)

• 计算 \binom{n}{k} (CS 1.5-14) [0.5]
  • 算法 + 复杂度分析
  • 参考: 习题课课件
  • By 周涛

2-4 (分治法与递归)

• 最大和/积子数组问题 (TC 4.1-5) [1]
  • 分析不同效率的多种算法 (原理介绍 + 伪代码)
  • 最大积子数组问题作为扩展，只需要给出线性的算法
  • 参考: 习题课课件; 《编程珠玑》Column 8
  • By 韩博
• 电路布线问题 [0.5]
  • 算法 + 复杂度分析
  • 参考: 习题课课件

2-5 (递归)

• The Art Gallery Problem [1]
  • 问题描述、定理证明、下界证明
  • 参考: 习题课课件; 《Proofs from THE Book》"How to Guard a Museum?"
• 递归式求解方法总结 [1]
  • first order linear recurrences
  • linear recurrences with constant coefficients
  • first order linear non-homogeneous recurrences
  • More
  • 参考: 习题课课件; 《An Introduction to the Analysis of Algorithms》 Chapters 2 and 3

2-7 (离散概率)

• The Monty-Hall Problem [1]
  • 分析多种版本
  • 参考: 习题课课件; wiki 词条 "Monty Hall problem"
• The Boy/Girl Puzzle (CS 5.3-12) [0.5]
  • 两种方式解读 “one of the children is a girl”
  • 参考: 习题课课件; wiki 词条 "Boy or Girl paradox"

2-8 (概率分析)

• Coin Pattern Problem [1]
  • 两种计算方法
  • 如果能将找到这两种方法的联系则更好
  • 参考: 习题课课件; 《Concrete Mathematics》Sections 8.3 and 8.4

2-9 (排序与选择)

• “01” Pattern Problem [0.5]
  • 奇数情况下的算法设计与正确性证明
  • 偶数情况下的对手论证与证明
  • 参考: 习题课课件; Jeff 讲义 (见课程网站)

2-10 (基本数据结构)

• Stack <-> Queue [1]
  • 两个 stacks 实现一个 queue
    • 参考: 习题课课件
  • 两个 queues 实现一个 stack
    • 参考: here and here
• By 杜星亮

2-11 (堆排序)

• Heapsort worst-case Omega(n log n) (TC 6.4-4) [0.5]
  • 如何构造最坏的例子
  • 参考: 习题课课件
• Heapsort best-case Omega(n log n) (TC 6.4-5) [1]
  • 证明
  • 参考: 习题课课件; TAOCP Vol. 3 Solution to Ex 32 of Section 5.2.3
• Counting # of heaps of size n [0.5]
  • 参考: 习题课课件; Paper "The Analysis of Heapsort", 见课程网站

2-12 (哈希表)

• 哈希表均匀采样 (TC 11.2-6) [1]
  • 采样算法
  • 复杂度分析
  • 正确性证明
  • By 肖江

2-14 (B 树)

• B树节点个数 (TC 18.2-4) [1]
  • 问题分析与解答
  • By 董杨静

其它

• 本学期所学内容（包括阅读材料、课堂教学、习题课、Open Topics、OJ 题目）中你所感兴趣的某个话题

主题:
正则表达式，自动机
题目:
（一下自动机均假设有限）
正则表达式和自动机的关系
如何将正则表达式转换为非确定自动机、确定自动机
非确定自动机和确定自动机的互相转化
习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
增加同学们对正则表达式、自动机的理解。
为后续课程《编译原理》部分内容打基础
题解:

参考资料:
《编译原理》（龙书）
其它:

主题:
分治（CLRS Chapter 4）

题目:
最大子数组问题（在数组中找到一个连续的子数组，使该子数组的和最大）的线性分治解法。

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
算法本身挺简单的。
说明分治不意味着复杂度高。
同时了解一下线段树。

题解:
https://fancypei.github.io/MaxSubarrayProblem/

参考资料:
https://en.wikipedia.org/wiki/Maximum_subarray_problem
https://vijos.org/p/1083

本 Issue 现征集习题、Open Topics:

• 为什么需要征集习题、Open Topics?

  • 我们需要高质量的题目
  • 你一定见识过很多高质量的题目
  • 你一定曾有过“好题共欣赏”的冲动
  • 你一定曾有过“没人搭理我”的失落

• 什么样的题目可以入选?

  • 有趣的
  • 有深度的
  • 有代表性的
  • 任意你想分享的题目

• 如何提交题目?

  • 提交 Issue (选择使用 problem-collecting 模板)
  • 注意: 一个 Issue 里只包含一道题目

• 如果题目得以采用,有何奖励?

  • 署名权
  • 待定 (你说呢?)

说明:

• 任选一道题目即可
• 在下面留言领取题目（多人可选同一题目）
• 截止日期: 2019年01月20日 晚上 20:00
  (依成绩统计进度，截止日期可能会有延后; 但这不是你犯拖延症的理由。)
• 提交方式: 与作业订正提交方式相同。此外，也可同时向该 Git 项目提交 pull request。

1. 平摊分析

• 问题: "自组织列表"平摊分析
• 参考资料: MIT OCW on Self-organizing Lists
• 要求: 观看教学视频，作笔记。描述问题、给出严格的证明过程

2. 最小生成树

2.1 Updating MST

• 问题: 已知图 G 的最小生成树 T。当出现如下情况时，如何高效地得到 G 的新的最小生成树。
  • T 中某条边权值增加
  • T 中某条边权值减少
  • G 中某条边 (不在 T 中) 权值增加
  • G 中某条边 (不在 T 中) 权值减少
• 要求: 给出严格的证明。
• 提醒: 对某一两个小题, 给出严格的证明可能并非想象中那么简单。

2.2 Critical Edges

• 问题: An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. Show how to find all critical edges in a graph in time proportional to E log E.
• 参考资料: Find all critical edges for minimum spanning tree @ cs-stackexchange
• 要求: 自行给出算法并给出严格证明; 或者检查参考资料中的算法与证明是否成立。
  (两种方案均需提交报告。)

3. 带负权边的无向图上的最短路径问题

• 问题: 利用 Perfect Matching 求无向图(允许有负权边，但不允许有负圈)中的最短简单路径
• 参考资料: Shortest Path Algorithms (math.sfu.ca, Math 408, Luis Goddyn).pdf
• 要求: 给出严格而详细的证明。
• 提醒: 参考材料中有少量笔误和大量未加证明的陈述。

4. 匹配

• 问题: 稳定婚姻问题
• 参考资料: Youtube 视频: Stable Marriage Problem, Part 1、Stable Marriage Problem: Part 2
• 要求: 观看视频，作笔记。描述问题、算法以及证明。（可选: 问题的历史与发展）

5. 网络流

• 问题: 七个等价定理
• 参考资料: Equivalence of Seven Major Theorems in Combinatorics (Robert Borgersen, 2004).pdf
• 要求: 任选其中三个定理，证明它们的相互等价性，要给出严格而详细的证明过程。

主题:
递归

题目:

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
刚刚了解到，这个问题的状态转移图竟然与分形有关系。
参见 知乎文章: 汉诺塔：闪烁在数学和心理学交汇之地奇妙问题

题解:
题解包括递归解法与迭代解法。

参考资料:

• Chapter 1 of "Concrete Mathematics"

其它:

• TODO: 使用 TLA+ 创建状态转移图

主题:
自动机

题目:
写一个DFA，使得其能识别二进制数字中3的倍数
（假定输入顺序是高位到低位）
（这个假定会让问题比较简单，但是低位到高位也能解决）

习题 还是 OT (在[]中填入x表示勾选):

• 习题
• OT

推荐理由:
将自动机中的“状态”与某些可以解释的东西联系在一起，增加对状态机的理解

题解:
状态机有3个状态，记作012.
状态i表示目前为止读到的数字串对应的二进制数字模3的余数。
那么状态转移就一目了然了
状态i接受输入j后，会转移到(2i+j)模3

参考资料:
UCB程序设计语言及编译器（CS164)课程作业1

其它: