前言
如果我们预挑出计算机科学中那些影响长久的贡献，算法（algorithm）一定位列其中。自从人类发明了可以执行基本数学运算的机器，什么是可以计算的以及如何计算就成为人们一直研究的课题。伴随此项研究，人们发现了大量的重要算法以及设计方法。算法成为计算机科学领域中的一项重要组成部分。本书的目的就是对有关算法的内容精心地组织，从而使得使用本书的同学以及实践者可以设计和分析全新的算法。
一本包含所有已发明的算法的书将会异常冗长。传统的算法书通常只对很少的几个问题领域有深入的阐述。对于每个问题，通常会给出并分析效率最高的算法。这样的做法有一个主要缺点。尽管同学们了解了很多很快的算法并且也掌握了分析算法的工具，但还是对如何设计一个好的算法信心不足。
这里所欠缺的就是没有强调设计（design）技术。设计方面的知识一定可以帮助创造好的算法，没有分析工具则无法判断算法的优劣。这样设计为主分析为辅的关系就自然地延伸为有效的讲授之道：我们将围绕基本的算法设计策略来组织本书。基本的设计策略是相对比较少的。并且大部分读者想要学习的算法可以划分到这些分类中；例如归并排序和快速排序是分治策略的例子，而Kruskal的最小生成树算法和Dijkstra的单源最短路径算法是贪心策略的例子。理解这些策略是掌握设计技能的重要的第一步。
尽管我们深切地认为强调设计以及分析是组织算法学习的正确之路，这里还是要给出一些注意事项。首先，我们并没有包括所有的设计原理。例如线性规划是最成功的技术之一，由于它往往由单独的课程所讲述从而没有包含到本书中。其次，读者不应该死板地学习算法设计，认为每个算法都是由一种技术得到的。事实并不是如此。
本书的主要篇幅，第3～9章，描述了不同的设计策略。每种策略首先描述一个大概。通常给出一个“程序抽象”来描述采用该策略所形成的计算模式的大纲。接着给出一系列的例子来讲述该策略的复杂以及变化。这些例子往往是按照由易到难的次序安排。其复杂的程度可以在不同的方面升高。我们通常先给出一个非常容易理解的例子，所使用的数据结构也仅仅为一维的数组。对这个例子，所用设计策略显而易见可以得到正确的解法。后面的例子可能需要证明基于该设计技术的算法是正确的。也可能是需要更加复杂的数据结构（例如树或者图），并且分析更加复杂。这样组织的主要目的是强调组成和分析算法的艺术。另外还希望能让读者体会好的程序结构以及算法正确性的证明。
第1～12章中的算法都是用C++或者伪C++代码给出。很多是可以直接运行并且已经经过测试的。选择C++是因为它是面向对象的程序语言。C++在计算机业界被广泛接受还有其他的很多理由。选择这种程序语言并不是说不熟悉C++的读者就不能用这本书。因为本书中大部分的算法都是比较短的，用来描述这些算法的代码也足够简单可以被广大读者所理解。第13～15章讲述并行计算。并行计算是一个飞速发展的领域，没有一个被广泛接受的模型或者程序语言。因此，我们选择用伪代码来描述这些算法。第1～12章中也有些简单的算法是用伪代码描述的。这是因为我们认为这些算法的核心思想用伪代码描述更加清晰。如何将这些伪代码转换为C++代码将作为练习留给读者。
另外本书的一大特色是广泛地讨论了随机算法。第13～15章中的很多算法是随机的。其他章节中也包含了一些随机算法。一门学季制的并行算法导论课程可以包含第13～15章，以及其他少量的补充内容。
我们也标出了一些内容（用*号）是适用于高级课程的。这本书的内容可以作为本科高年级学生或者研究生的一门学期制课程，或者两门学季制的课程。它需要学生具备高级语言的编程能力，其余的内容都自完备的。实践上，一门数据结构课也是有帮助的，这样学生具备更成熟的编程能力。如果是学季制的学校，第一个学季可以讲授一些基本的设计技术，例如第3章～第9章中的分治、贪心、动态规划、搜索和遍历、回溯、分治定界以及代数方法（见表Ⅰ）。第二个学季可以讲授第10～15章：下界定理、 D_Dd__________ǒe??_____________
如果课程是一个学期的，并且学生之前没有接触过数据结构和大O表示，那么第1～7章、第11章以及第13章的内容比较合适（见表Ⅲ）。
如果进度更加紧凑一些可以包含第1～7章、第11章、第13章以及第14章的内容（见表Ⅳ）。
如果学生已经掌握了数据结构和大O表示，可以由第3～11章，以及第13～15章构成一门高级课程（见表Ⅴ）。
表Ⅰ 第一学季
周次
内容
阅读
1
引言
1.1-1.3
2
引言
数据结构
1.4
2.1、2.2
3
数据结构
2.3-2.6
4
分治
第3章
第一次作业
5
贪心算法
第4章
期中考试
6
动态规划
第5章
7
搜索与遍历
第6章
第二次作业
8
回溯
第7章
9
分支定界
第8章
10
代数方法
第9章
第三次作业
期末考试
表Ⅱ 第二学季
周次
内容
阅读
1
下界定理
10.1-10.3
2
下界定理
完全和难问题
10.4
11.1，11.2
3
完全和难问题
11.3，11.4
4
完全和难问题
近似算法
11.5，11.6
12.1，12.2
第一次作业
5
近似算法
12.3-12.6
期中考试
6
PRAM算法
13.1-13.4
7
PRAM算法
13.5-13.9
第二次作业
8
网格算法
14.1-14.5
9
网格算法
超立方算法
14.6-14.8
15.1-15.3
10
超立方算法
15.4-15.8
第三次作业
期末考试
表Ⅲ 学期：中速（无基础）
周次
内容
阅读
1
引言
1.1-1.3
2
引言
数据结构
1.4
2.1，2.2
3
数据结构
2.3-2.6
4
分治
3.1-3.4
第一次作业
5
分治
3.5-3.7
考试Ⅰ
6
贪心算法
4.1-4.4
7
贪心算法
4.5-4.7
第二次作业
8
动态规划
5.1-5.5
9
动态规划
5.6-5.10
10
搜索与遍历
6.1-6.4
第三次作业
考试Ⅱ
11
回溯
7.1-7.3
12
回溯
7.4-7.6
续表
周次
内容
阅读
13
完全和难问题
11.1-11.3
第四次作业
14
完全和难问题
11.4-11.6
15
PRAM算法
13.1-13.4
16
PRAM算法
13.5-13.9
第五次作业
考试Ⅲ
表Ⅳ 学期：快速（无基础）
周次
内容
阅读
1
引言
1.1-1.3
2
引言
数据结构
1.4
2.1，2.2
3
数据结构
2.3-2.6
4
分治
3.1-3.5
第一次作业
5
分治
贪心算法
3.6-3.7
4.1-4.3
考试Ⅰ
6
贪心算法
4.4-4.7
7
动态规划
5.1-5.7
第二次作业
8
动态规划
搜索与遍历
5.8-5.10
6.1-6.2
9
搜索与遍历
回溯
6.3-6.4
7.1-7.2
10
回溯
7.3-7.6
第三次作业
考试Ⅱ
11
完全和难问题
11.1-11.3
12
完全和难问题
11.4-11.6
13
PRAM算法
13.1-13.4
第四次作业
14
PRAM算法
13.5-13.9
15
网格算法
14.1-14.3
16
网格算法
14.4-14.8
第五次作业
考试Ⅲ
表Ⅴ 学期：高级课程（快速）
周次
内容
阅读
1
分治
3.1-3.5
2
分治
贪心算法
3.6-3.7
4.1-4.3
3
贪心算法
4.4-4.7
4
动态规划
第5章
第一次作业
5
搜索与遍历
第6章
考试Ⅰ
6
回溯
第7章
7
分支定界
第8章
第二次作业
8
代数方法
第9章
9
下界定理
第10章
10
完全和难问题
11.1-11.3
第三次作业
考试Ⅱ
11
完全和难问题
11.4-11.6
12
PRAM算法
13.1-13.4
13
PRAM算法
13.5-13.9
第四次作业
14
网格算法
14.1-14.5
15
网格算法
超立方算法
14.6-14.8
15.1-15.3
16
超立方算法
15.4-15.8
第五次作业
考试Ⅲ
每章的最后给出了大量的习题可以作为课程作业。我们发现最受欢迎并且最有启发性的作业是让学生在同一个数据集上运行两个算法并且比较两个算法的运行时间。本书的绝大多数算法都有实现的细节，供学生们使用。将这些C++程序转换为其他语言的程序也不困难。那么剩余的就是构造合适的数据集以及编写一个main函数来完成上述的运行记时。记时的结果应该与算法的时间复杂度渐进分析的结论相一致。这项任务并不简单，是有教育意义并且很有趣的。最重要的是它强调了一个往往被人们忽视的方面，也就是算法在实用过程中还有实践性的一面。
在这个新版中，我们还加入一些新的例子以及习题，加强了平摊复杂度，更新了每章最后的参考文献以及阅读。
致谢
我们要感谢Martin J. Biernat、Jeff Jenness、Saleem Khan、Ming-Yang Kao、Douglas M. Compbell以及Stephen P. Leach的意见和建议。我们要感谢佛罗里达大学的同学指出了较早版本中的错误。我们还要感谢Teo Gonzalez、Danny Krizanc以及David Wei仔细阅读了部分章节。
Ellis Horowitz
Sartaj Sahni
Sanguthevar Rajasekaran
