1、已知，(1<=i<=n-1) 其中c1和c2为正常数，请证明
。
2、【凸包问题】给定平面上n个点，从中找出一个最小点集，使该点集所组成的凸多边形包围所有的n个点。用分治法编写一个求解凸包问题的算法。
3、设计一个动态规划算法，找到字符串T[1..n]中前向和后项相同的最长连续子串。前向子串和后项子串不能重叠。例如：
1）输入“ALGORITHM”，算法返回空串；
2）输入“RCURSION”，算法返回“R”；
3）输入“REDIVIDE”，算法返回“EDI”。
4、假定J={1,2,3,…,n}是n个等待在同一台机器上加工的作业集合，每个作业所需要的加工时间都为1个时间单位，且每个作业i都有一个最迟完成时间di。如果一个作业i能够在di之前完成，就可获得收益pi>0；反之，则不获得收益。请设计一个贪心的算法求该问题的一个最佳安排方案使得收益最大，并证明你所设计的贪心策略的最优性。
5、【集合覆盖问题】给定一个集合X={x1,x2,…xn}以及X的一个子集簇F={f1,f2,…fn}，其中，fi ÍX。求F的一个最小子集CÍF，使得C中的集合能够覆盖集合X，即。
1）已知图的顶点覆盖问题是NPC，证明集合覆盖问题是NP难的；
2）利用回溯法或分支界限法设计求解集合覆盖问题的算法。