共计七道题，今年不考NP问题和对偶。请各位同学根据教学实际，酌情参考。
卷子是纯英文的，在考场上遇到题目看不懂的情况可以举手示意助教解答。
只要不是大面积空白助教都会尽量捞，真的想不出来就写个时间复杂度分析吧。
祝各位考试顺利~
1. Divide and Conquer
给定一个长度为k的数组，在这个数组中，有一个数字出现了比$\lfloor{\frac{2}{k}} \rfloor$次还多，请找出这个数字。
2. Dynamic Programming
给定两个数组，求问最少操作多少次remove元素后，两个数组可以变得一致。
例如：[A,B,C,D]和[A,E,D]需要操作3次，去除第一个数组里的B和C，以及第二个数组里的E。
剑指Offer II 095
3. Greedy
Leetcode NO.1546
4. Linear Programming
搬家问题。你有a1,a2,a3…an，共n件东西，它们的大小分别是b1,b2,b3…，bn；
你现在有一辆卡车，这辆卡车的容量为V；
你有c1,c2,c3…cm，共m个箱子，它们的容量分别是d1,d2,d3…,dn，所有的物品必须放在箱子里才能上车；
设计一个ILP，要求用最少的趟数可以运完所有的东西。
注意：每个箱子至多使用一次。（问了助教给的答复）
5. Network Flow
（两段式题干，看懂题目就成功了90%；前面一大段都在解释什么是二分图）
二分图是是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。给定一个二分图G，在G的一个子图M中，M的边集中的任意两条边都不依附于同一个顶点，则称M是一个匹配。选择这样的边数最大的子集称为图的最大匹配问题（maximal matching problem)。
现在我们有一个算法可以解决网络流中的最大流问题，我们把这个算法称之为MFP算法。请你利用MFP算法，构造一个算法，使它可以解决MMP问题。
提示：在二分图中添加可能需要的额外顶点，边，或权值。
6. Bonus 1
课堂上有n名学生，他们对于一门考试的成绩分别是a1,a2,… an，现在要把他们划分为若干小组，记一个小组内最高成绩和最低成绩之差为K
(1) 设计一个算法，把学生分为m组，使所有组当中最大的K尽可能小。
(2) 能否将学生分为X组，每组至少Y人，且K均小于L？如果可以，给出算法，如果不能，给出理由。
我们这里假设M,X,Y,L均小于n
7. Bonus 2
题干比较复杂的问题，根据群友的说法，这道题的意思是形式语言与自动机中，证明 P 语言关于 * 操作封闭。（我没学过所以不清楚）
大致回忆如下（不一定准确！）：
我们定义 word = {0,1}
若干word可以组成一个sentence，sentence的长度不定，可以是无限长。
非无限长的sentence可以组成一个language
一个identifier可以用于检查一个sentence是否属于这个language（输出bool true或false）
我们定义一个语言A，和另一个语言B，其中B语言的sentence由A语言的sentence拼接得到。（比如A语言有00，01两个sentence，那么，0001，0100，01000001都属于B语言）
现在，给你一个identifier L，它可以在多项式时间内确定一个输入是否属于A language，请利用这个identifier L，构造一个同样多项式时间复杂度的identifier L’， 使得它可以检查输入是否属于B language。
考场上我的答案思路