Jon Kleinberg是美国国家科学院（NAS）、美国国家工程院（NAE）、美国人文与科学院（AAAS）三料院士。在计算机科学领域是“传说级”的人物，而且还获得过靠前数学家大会颁发“奈望林纳奖”，该奖是数学家大会为了表彰信息科学方面的重要数学贡献而设的。
目录
1Introduction:Some Representative Problems/引言：某些有代表性的问题1
1.1A First Problem:Stable Matching/第 一个问题：稳定匹配1
1.2Five Representative Problems/五个有代表性的问题12
SolvedExercises/带解答的练习19
Exercises/练习22
Notesand Further Reading/注释和进一步阅读28
2Basics of Algorithm Analysis/算法分析基础29
2.1Computational Tractability/计算可解性29
2.2Asymptotic Order of Growth/增长的渐近阶35
2.3Implementing the Stable Matching Algorithm Using Lists and Arrays/用列表和数组实现稳定匹配算法42
2.4A Survey of Common Running Times/常用运行时间概述47
2.5A More Complex Data Structure:Priority Queues/更复杂的数据结构：优先队列57
SolvedExercises/带解答的练习65
Exercises/练习67
Notesand Further Reading/注释和进一步阅读70
3Graphs/图73
3.1Basic Definitions and Applications/基本定义与应用73
3.2Graph Connectivity and Graph Traversal/图的连通性与图的遍历78
3.3Implementing Graph Traversal Using Queues and Stacks/用优先队列与栈实现图的遍历87
3.4Testing Bipartiteness:An Application of Breadth-First Search/二分性测试：宽度优先搜索的应用94
3.5Connectivity in Directed Graphs/有向图中的连通性97
3.6Directed Acyclic Graphs and Topological Ordering/有向无环图与拓扑排序99
SolvedExercises/带解答的练习104
Exercises/练习107
Notesand Further Reading/注释和进一步阅读112
4Greedy Algorithms/贪心算法115
4.1Interval Scheduling:The Greedy Algorithm Stays Ahead/区间调度：贪心算法领先116
4.2Scheduling to Minimize Lateness:An Exchange Argument/最小延迟调度：交换论证125
4.3Optimal Caching:A More Complex Exchange Argument/很优高速缓存：更复杂的交换论证131
4.4Shortest Paths in a Graph/图的最短路径137
4.5The Minimum Spanning Tree Problem/最小生成树问题142
4.6Implementing Kruskal’s Algorithm:The Union-Find Data Structure/实现Kruskal算法：Union-Find数据结构151
4.7Clustering/聚类157
4.8Huffman Codes and Data Compression/赫夫曼码与数据压缩161
4.9 Minimum-Cost Arborescences:A Multi-Phase Greedy Algorithm/最小费用有向树：多阶段贪心算法177
SolvedExercises/带解答的练习183
Exercises/练习188
Notesand Further Reading/注释和进一步阅读205
5Divide and Conquer/分治策略209
5.1A First Recurrence:The Mergesort Algorithm/第 一个递推式：归并排序算法210
5.2Further Recurrence Relations/更多的递推关系214
5.3Counting Inversions/计数逆序221
5.4Finding the Closest Pair of Points/找最接邻近的点对225
5.5Integer Multiplication/整数乘法231
5.6Convolutions and the Fast Fourier Transform/卷积与快速傅里叶变换234
SolvedExercises/带解答的练习242
Exercises/练习246
Notesand Further Reading/注释和进一步阅读249
6Dynamic Programming/动态规划251
6.1Weighted Interval Scheduling:A Recursive Procedure/带权的区间调度：递归过程252
6.2Principles of Dynamic Programming:Memoization or Iteration over Subproblems/动态规划原理：备忘录或者子问题迭代258
6.3Segmented Least Squares:Multi-way Choices/分段的最小二乘：多重选择261
6.4Subset Sums and Knapsacks:Adding a Variable/子集和与背包：加一个变量266
6.5RNA Secondary Structure:Dynamic Programming over Intervals/RNA二级结构：在区间上的动态规划272
6.6Sequence Alignment/序列比对278
6.7Sequence Alignment in Linear Space via Divide and Conquer/通过分治策略在线性空间的序列比对284
6.8Shortest Paths in a Graph/图中的最短路径290
6.9Shortest Paths and Distance Vector Protocols/最短路径和距离向量协议297
6.10 Negative Cycles in a Graph/图中的负圈301
SolvedExercises/带解答的练习307
Exercises/练习312
Notesand Further Reading/注释和进一步阅读335
7Network Flow/网络流337
7.1The Maximum-Flow Problem and the Ford-Fulkerson Algorithm/优选流问题与Ford-Fulkerson算法338
7.2Maximum Flows and Minimum Cuts in a Network/网络中的优选流与最小割346
7.3Choosing Good Augmenting Paths/选择好的增广路径352
7.4 The Preflow-Push Maximum-Flow Algorithm/前向流推动优选流算法357
7.5A First Application:The Bipartite Matching Problem/第 一个应用：二分匹配问题367
7.6Disjoint Paths in Directed and Undirected Graphs/有向与无向图中的不交路径373
7.7Extensions to the Maximum-Flow Problem/对优选流问题的推广378
7.8Survey Design/调查设计384
7.9Airline Scheduling/航线调度387
7.10Image Segmentation/图像分割391
7.11Project Selection/项目选择396
7.12Baseball Elimination/棒球排除400
7.13 A Further Direction:Adding Costs to the Matching Problem/进一步的方向：对匹配问题增加费用404
SolvedExercises/带解答的练习411
Exercises/练习415
Notesand Further Reading/注释和进一步阅读448
8NP and Computational Intractability/NP与计算的难解性451
8.1Polynomial-Time Reductions/多项式时间归约452
8.2Reductions via “Gadgets”:The Satisfiability Problem/使用“零件”的归约：可满足性问题459
8.3Efficient Certification and the Definition of NP/有效证书和NP的定义463
8.4NP-Complete Problems/NP接近问题466
8.5Sequencing Problems/排序问题473
8.6Partitioning Problems/划分问题481
8.7Graph Coloring/图着色485
8.8Numerical Problems/数值问题490
8.9Co-NP and the Asymmetry of NP/Co-NP及NP的不对称性495
8.10A Partial Taxonomy of Hard Problems/难问题的部分分类497
SolvedExercises/带解答的练习500
Exercises/练习505
Notesand Further Reading/注释和进一步阅读529
9PSPACE:A Class of Problems beyond NP/PSPACE：一类超出NP的问题531
9.1PSPACE/PSPACE531
9.2Some Hard Problems in PSPACE/PSPACE中的难问题533
9.3Solving Quantified Problems and Games in Polynomial Space/在多项式空间中解量化问题和博弈问题536
9.4Solving the Planning Problem in Polynomial Space/在多项式空间内求解规划问题538
9.5Proving Problems PSPACE-Complete/证明问题是PSPACE接近的543
SolvedExercises/带解答的练习547
Exercises/练习550
Notesand Further Reading/注释和进一步阅读551
10Extending the Limits of Tractability/扩展易解性的界限553
10.1Finding Small Vertex Covers/找小的顶点覆盖554
10.2Solving NP-Hard Problems on Trees/在树上解NP难问题558
10.3Coloring a Set of Circular Arcs/圆弧集着色563
10.4 Tree Decompositions of Graphs/图的树分解572
10.5 Constructing a Tree Decomposition/构造树分解584
SolvedExercises/带解答的练习591
Exercises/练习594
Notesand Further Reading/注释和进一步阅读598
11Approximation Algorithms/近似算法599
11.1Greedy Algorithms and Bounds on the Optimum:A Load Balancing Problem/贪心算法与很优值的界限：负载均衡问题600
11.2The Center Selection Problem/中心选址问题606
11.3Set Cover:A General Greedy Heuristic/集合覆盖：一般的贪心启发式方法612
11.4The Pricing Method:Vertex Cover/定价法：顶点覆盖618
11.5Maximization via the Pricing Method:The Disjoint Paths Problem/用定价法优选化：不交路径问题624
11.6Linear Programming and Rounding:An Application to Vertex Cover/线性规划与舍入：对顶点覆盖的应用630
11.7 Load Balancing Revisited:A More Advanced LP Application/再论负载均衡：更不错的LP应用637
11.8Arbitrarily Good Approximations:The Knapsack Problem/任意好的近似：背包问题644
SolvedExercises/带解答的练习649
Exercises/练习651
Notesand Further Reading/注释和进一步阅读659
12Local Search/局部搜索661
12.1The Landscape of an Optimization Problem/很优化问题的地形图662
12.2The Metropolis Algorithm and Simulated Annealing/Metropolis算法与模拟退火算法666
12.3An Application of Local Search to Hopfield Neural Networks/局部搜索在Hopfield神经网络中的应用671
12.4Maximum-Cut Approximation via Local Search/局部搜索对优选割近似的应用676
12.5Choosing a Neighbor Relation/选择邻居关系679
12.6 Classification via Local Search/用局部搜索分类681
12.7Best-Response Dynamics and Nash Equilibria/很好响应动态过程与纳什均衡690
SolvedExercises/带解答的练习700
Exercises/练习702
Notesand Further Reading/注释和进一步阅读705
13Randomized Algorithms/随机算法707
13.1A First Application:Contention Resolution/第 一个应用：消除争用708
13.2Finding the Global Minimum Cut/求接近最小割714
13.3Random Variables and Their Expectations/随机变量及其期望719
13.4A Randomized Approximation Algorithm for MAX 3-SAT/关于MAX 3-SAT的随机近似算法724
13.5Randomized Divide and Conquer:Median-Finding and Quicksort/随机分治策略：求中位数与快速排序727
13.6Hashing:A Randomized Implementation of Dictionaries/散列法：字典的随机实现734
13.7Finding the Closest Pair of Points:A Randomized Approach/求最邻近点对：随机方法741
13.8Randomized Caching/随机超高速缓存750
13.9Chernoff Bounds/切尔诺夫界758
13.10Load Balancing/负载均衡760
13.11Packet Routing/包路由选择762
13.12Background:Some Basic Probability Definitions/背景：某些基本概率定义769
SolvedExercises/带解答的练习776
Exercises/练习782
Notesand Further Reading/注释和进一步阅读793
Epilogue:Algorithms That Run Forever/后记：永不停止运行的算法795
References/参考文献805
