教学大纲

课程简介

计算机科学的每一个领域都需要有高效的算法.但是随着各类问题被解决,算法的概念趋向于"高效",甚至计算模型可以从一个领域变换到另外一个领域。 在算法的第二课里,我们将看到各种广泛用在算法的高效设计上的技术,并且学习他们在应用领域和计算模型上的广泛应用

这门课的目标是广泛而不是深度.我们的计划是能够接触以各个领域.以下是一个我们在上课时可能会覆盖到的主题的列表,我们将根据学生的背景, 兴趣,和进度来适当地选择材料。

数据结构

更多的对基本数据结构问题先进解决方案:斐波那契堆、Van Emde Boas优先队列、图连通性/可达性的的动态数据结构。

位欺骗

世界级并行化、跨学科模型、O(n\log n)整数排序。

串算法

Rabin-Karp指印算法、后缀树。

最大流

增广路径和压入-重标记方法、最小代价流、双向匹配。

线性规划

线性规划的规范化、对偶性、简单性、内部点和椭圆算法。

在线算法

雪撬租约、河流查找问题、分页问题、K-服务器问题、列表排序与前移问题。

近似算法

一种解决NP-难问题的方法，贪心近似算法、动态规划和弱多项式时间算法、线性规划松弛法、随机取整法、顶点覆盖、装配线调度及旅行商问题。

固定参数算法

解决NP-难问题的另一种解决方法.参数化复杂性、核化、顶点覆盖、与近似算法的关系。

并行算法

并行共享存储器模型、指针跳跃与并行前缀、树紧缩、分冶法、随机对称分裂法、最大独立子集。

外存算法

计算从低速缓存访问期间数据的代价，排序、B-树、缓冲树、矩阵乘法和二项查找的缓存遗忘算法。

计算几何

凸包问题、线段交集问题、扫描线问题、维氏图、等级树、塞尔德低维线性规划算法。

流算法

概要算法. Distinct and Frequent Elements.

课程目标

我们希望这门课程能使们学会：

• 熟悉各种高效性算法，当给定一个问题时能够知道规划和查找出算法问题的高效解决方案。
• 提供足够的背景和便利条件能够让你阅读当前算法领域的研究执点。
• 提供一系列工具来分析和设计你碰到的新问题和新算法。

前提条件

我们希望我们的读者在本科时学过算法 (6.046J))，并接触过(6.041 或 6.042J就足够了)。最好能够也学过复杂性理论(6.045J) 。

课本

这门课中我们学习的大部分材料我们都没有教科书。大约20%的的内容是由这门课程的前一个版本的讲座笔记组成，《高级算法》，2001年秋季(6.854J), 由Michel Goemans教授授的课. 至于其它的阅读材料，请看参考读物部分.

学生学分与记录

我们期望学生来帮助记录一个LaTex格式的讲座，并且/或者帮助形成一个问题集。这项工作占了这门课程的5%的学分。

作业

每周会有约占总学分的70%的问题集，并且允许合作。

考试

这门课程没有考试。

项目

你将会阅读到最近研究领域的一个新算法，用下面的一种或多种方法改进它：

• 写出原始处算法的一个更清晰的描述，或者
• 设计一个对问题的改进的解决方案，并写出你的改进算法（加上些对原算法的适当讨论）。
• 为了在实践中学习算法的性能执行一遍算法，考虑算法的选择，设计好的测试实例，解释结果，并在实践中设计与分析改进算法的性能。

理想情况下，你选择的一个算法是一个你需要解决的问题而产生的算法。若这个项目很大，允许采用分组的形式来解决。这个项目约点学分的25%。

合作策略

在这门课的所有方面我们都鼓励合作，除了一些明确禁止的地方,注：

1. 在提交作业时所有的合作都必须明确地指出（谁和做什么）。
2. 家庭作业可以以合作的方式来解决，除了一些明确禁止的地方，但是解答必须独立地写。小组应该足够的小，从而每一个人都能在其中起重要作用。
3. 对于一个项目，每一个合作者都必须参与阅读、执行和写。为了允许这种形式，小组限制不超过3人，除非这个项目特别大。

成绩评定