本书源自加州大学伯克利分校和加州大学圣迭戈分校本科生的算法课讲义，以独特的视角展现了算法设计的精巧技术及魅力。在表达每一种技术时，强调每个算法背后的简洁数学思想，分析其时间和空间效率，运用与其他技术类比的方法来说明特征，并提供了大量实例。

本书以人类最古老的算法(算术运算)为起点，将各种算法中优美而有代表性的内容囊括书中，并以最前沿的理论(量子算法)结束，构成了较为完整的算法知识体系。

本书共分为四个部分。其中，第一部分是引论和算术运算(这是算法的起源)，包括复杂度分析、算术运算、最大公约数、素性测试、散列函数、快速乘法、递归、合并排序、矩阵乘法，还有在一般算法书中不多见的RSA公钥体制和快速傅里叶变换等内容。第二部分是“传统”的算法和数据结构(树和图)：图的搜索、连通性、最短路径、最小生成树、堆、赫夫曼编码等。在第三部分里，作者用新颖的方式介绍了两种强大的运筹学算法——动态规划和线性规划，以及它们的应用。利用这两种运筹学算法，能够优美地解决一大批实际问题。最后一部分是关于如何解决困难的问题，包括NP完全、优化搜索(回溯、分支限界)、近似算法等。值得一提的是本书的最后一章——量子算法。作者首次将理论研究中最前沿的内容以通俗易懂的形式写入算法教科书中，给人耳目一新的感觉。

出版者的话

序言

Preface

方框目录

0 Prologue(序论)

 0.1 Books and algorithms(书和算法)

 0.2 Enter Fibonacci(斐波那契数列)

 0.3 Big-O notation(大O记号)

 Exercises(习题) 

1 Algorithms with numbers(数的算法)

 1.1 Basic arithmetic(基本算术)

 1.2 Modular arithmetic(模运算)

 1.3 Primality testing(素性测试)

 1.4 Cryptography(密码学)

 1.5 Universal hashing(全域散列)

 Exercises(习题)

Randomized algorithms：a virtual chapter(虚拟章：随机化算法)

2 Divide-and-conquer algorithms(分而治之算法)

 2.1 Multiplication(乘法)

 2.2 Recurrence relations(递归关系)

 2.3 Mergesort(合并排序)

 2.4 Medians(中位数)

 2.5 Matrix multiplication(矩阵乘法)

 2.6 The fast Fourier transform(快速傅里叶变换)

 Exercises(习题)

3 Decompositions of graphs(图的分解)

 3.1 Why graphs?(图论)

 3.2 Depth-first search in undirected graphs(无向图中的深度优先搜索)

 3.3 Depth-first search in directed graphs(有向图中的深度优先搜索)

 3.4 Strongly connected components(强连通分量)

 Exercises(习题)

4 Paths in graphs(图的路径)

 4.1 Distances(距离)

 4.2 Breadth-first search(广度优先搜索)

 4.3 Lengths on edges(边的长度)

 4.4 Dijkstra’s algorithm(Dijkstra算法)

 4.5 Priority queue implementations(实现优先队列)

 4.6 Shortest paths in the presence of negative edges(带负权的边的图中的最短路径)

 4.7 Shortest paths in dags(有向无环图中的最短路径)

 Exercises(习题)

5 Greedy algorithms(贪婪算法)

 5.1 Minimum spanning trees(最小生成树)

 5.2 Huffman encoding(赫夫曼编码)

 5.3 Horn formulas(Horn公式)

 5.4 Set cover(集合覆盖)

 Exercises(习题)

6 Dynamic programming(动态规划)

 6.1 Shortest paths in dags，revisited(回顾：有向无环图中的最短路径)

 6.2 Longest increasing subsequences(最长递增子序列)

 6.3 Edit distance(编辑距离)

 6.4 Knapsack(背包问题)

 6.5 Chain matrix multiplication(链式矩阵乘法)

 6.6 Shortestpaths(最短路径)

 6.7 Independent sets in trees(树中的独立集)

 Exercises(习题)

7 Linear programming and reductions(线性规划与归约)

 7.1 An introduction to linear programming(线性规划入门)

 7.2 Flows in networks(网络流)

 7.3 Bipartite matching(二部图匹配)

 7.4 Duality(对偶性)

 7.5 Zero-sum games(零和游戏)

 7.6 The simplex algorithm(单纯形算法)

 7.7 Postscript：circuit evaluation(附录：电路求值)

 Exercises(习题)

8 NP-complete prob!ems(NP完全问题)

 8.1 Search problems(搜索问题)

 8.2 NP-complete problems(NP完全问题)

 8.3 The reductions(归约)

 Exercises(习题)

9 Coping with NP-completeness(处理NP完全问题)

 9.1 Intelligent exhaustive search(智能穷举搜索)

 9.2 Approximation algorithms(近似算法)

 9.3 Local search heuristics(局部启发式搜索)

 Exercises(习题)

10 Quantum algorithms(量子算法)

 10.1 Qubits，superposition，and measurement(量子比特、叠加态与测量)

 10.2 The plan(下文纵览)

 10.3 The quantum Fourier transform(量子傅里叶变换)

 10.4 Periodicity(周期性)

 10.5 Quantum circuits(量子电路)

 10.6 Factoring as periodicity(因子分解：利用周期性)

 10.7 The quantum algorithm for factoring(因子分解的量子算法)

 Exercises(习题)

Historical notes and further reading(历史注记与扩展阅读)

索引

注释