算法設計 英文版

目錄
1　Introduction： Some Representative Problems / 引言：某些有代表性的問題　1
1．1　A First Problem： Stable Matching / 第 一個問題：穩(wěn)定匹配　1
1．2　Five Representative Problems / 五個有代表性的問題　12
Solved　Exercises / 帶解答的練習　19
Exercises　/ 練習　22
Notes　and Further Reading / 注釋和進一步閱讀　28
2　Basics of Algorithm Analysis / 算法分析基礎　29
2．1　Computational Tractability / 計算可解性　29
2．2　Asymptotic Order of Growth / 增長的漸近階　35
2．3　Implementing the Stable Matching Algorithm Using Lists and Arrays / 用列表和數(shù)組實現(xiàn)穩(wěn)定匹配算法42
2．4　A Survey of Common Running Times / 常用運行時間概述　47
2．5　A More Complex Data Structure： Priority Queues / 更復雜的數(shù)據(jù)結構：優(yōu)先隊列　57
Solved　Exercises / 帶解答的練習　65
Exercises　/ 練習　67
Notes　and Further Reading / 注釋和進一步閱讀　70
3　Graphs / 圖　73
3．1　Basic Definitions and Applications / 基本定義與應用　73
3．2　Graph Connectivity and Graph Traversal / 圖的連通性與圖的遍歷　78
3．3　Implementing Graph Traversal Using Queues and Stacks / 用優(yōu)先隊列與棧實現(xiàn)圖的遍歷　87
3．4　Testing Bipartiteness： An Application of Breadth-First Search / 二分性測試：寬度優(yōu)先搜索的應用　94
3．5　Connectivity in Directed Graphs / 有向圖中的連通性　97
3．6　Directed Acyclic Graphs and Topological Ordering / 有向無環(huán)圖與拓撲排序　99
Solved　Exercises / 帶解答的練習　104
Exercises　/ 練習　107
Notes　and Further Reading / 注釋和進一步閱讀　112
4　Greedy Algorithms / 貪心算法　115
4．1　Interval Scheduling： The Greedy Algorithm Stays Ahead / 區(qū)間調(diào)度：貪心算法領先　116
4．2　Scheduling to Minimize Lateness： An Exchange Argument / 最小延遲調(diào)度：交換論證　125
4．3　Optimal Caching： A More Complex Exchange Argument / 最優(yōu)高速緩存：更復雜的交換論證131
4．4　Shortest Paths in a Graph / 圖的最短路徑　137
4．5　The Minimum Spanning Tree Problem / 最小生成樹問題　142
4．6　Implementing Kruskal’s Algorithm： The Union-Find Data Structure / 實現(xiàn)Kruskal算法：Union-Find數(shù)據(jù)結構　151
4．7　Clustering / 聚類　157
4．8　Huffman Codes and Data Compression / 赫夫曼碼與數(shù)據(jù)壓縮　161
4．9 Minimum-Cost Arborescences： A Multi-Phase Greedy Algorithm / 最小費用有向樹：多階段貪心算法　177
Solved　Exercises / 帶解答的練習　183
Exercises　/ 練習　188
Notes　and Further Reading / 注釋和進一步閱讀　205
5　Divide and Conquer / 分治策略　209
5．1　A First Recurrence： The Mergesort Algorithm / 第 一個遞推式：歸并排序算法　210
5．2　Further Recurrence Relations / 更多的遞推關系　214
5．3　Counting Inversions / 計數(shù)逆序　221
5．4　Finding the Closest Pair of Points / 找最接鄰近的點對　225
5．5　Integer Multiplication / 整數(shù)乘法　231
5．6　Convolutions and the Fast Fourier Transform / 卷積與快速傅里葉變換　234
Solved　Exercises / 帶解答的練習　242
Exercises　/ 練習　246
Notes　and Further Reading / 注釋和進一步閱讀　249
6　Dynamic Programming / 動態(tài)規(guī)劃　251
6．1　Weighted Interval Scheduling： A Recursive Procedure / 帶權的區(qū)間調(diào)度：遞歸過程　252
6．2　Principles of Dynamic Programming： Memoization or Iteration over Subproblems / 動態(tài)規(guī)劃原理：備忘錄或者子問題迭代　258
6．3　Segmented Least Squares： Multi-way Choices / 分段的最小二乘：多重選擇　261
6．4　Subset Sums and Knapsacks： Adding a Variable / 子集和與背包：加一個變量　266
6．5　RNA Secondary Structure： Dynamic Programming over Intervals / RNA二級結構：在區(qū)間上的動態(tài)規(guī)劃　272
6．6　Sequence Alignment / 序列比對　278
6．7　Sequence Alignment in Linear Space via Divide and Conquer / 通過分治策略在線性空間的序列比對　284
6．8　Shortest Paths in a Graph / 圖中的最短路徑　290
6．9　Shortest Paths and Distance Vector Protocols / 最短路徑和距離向量協(xié)議　297
6．10 Negative Cycles in a Graph / 圖中的負圈　301
Solved　Exercises / 帶解答的練習　307
Exercises　/ 練習　312
Notes　and Further Reading / 注釋和進一步閱讀　335
7　Network Flow / 網(wǎng)絡流　337
7．1　The Maximum-Flow Problem and the Ford-Fulkerson Algorithm / 最大流問題與Ford-Fulkerson算法　338
7．2　Maximum Flows and Minimum Cuts in a Network / 網(wǎng)絡中的最大流與最小割　346
7．3　Choosing Good Augmenting Paths / 選擇好的增廣路徑352
7．4 The Preflow-Push Maximum-Flow Algorithm / 前向流推動最大流算法　357
7．5　A First Application： The Bipartite Matching Problem / 第 一個應用：二分匹配問題　367
7．6　Disjoint Paths in Directed and Undirected Graphs / 有向與無向圖中的不交路徑　373
7．7　Extensions to the Maximum-Flow Problem / 對最大流問題的推廣　378
7．8　Survey Design / 調(diào)查設計384
7．9　Airline Scheduling / 航線調(diào)度　387
7．10　Image Segmentation / 圖像分割　391
7．11　Project Selection / 項目選擇　396
7．12　Baseball Elimination / 棒球排除　400
7．13 A Further Direction： Adding Costs to the Matching Problem / 進一步的方向：對匹配問題增加費用　404
Solved　Exercises / 帶解答的練習　411
Exercises　/ 練習　415
Notes　and Further Reading / 注釋和進一步閱讀　448
8　NP and Computational Intractability / NP與計算的難解性　451
8．1　Polynomial-Time Reductions / 多項式時間歸約　452
8．2　Reductions via “Gadgets”： The Satisfiability Problem / 使用“零件”的歸約：可滿足性問題　459
8．3　Efficient Certification and the Definition of NP / 有效證書和NP的定義　463
8．4　NP-Complete Problems / NP完全問題　466
8．5　Sequencing Problems / 排序問題　473
8．6　Partitioning Problems / 劃分問題　481
8．7　Graph Coloring / 圖著色　485
8．8　Numerical Problems / 數(shù)值問題　490
8．9　Co-NP and the Asymmetry of NP / Co-NP及NP的不對稱性　495
8．10　A Partial Taxonomy of Hard Problems / 難問題的部分分類　497
Solved　Exercises / 帶解答的練習　500
Exercises　/ 練習　505
Notes　and Further Reading / 注釋和進一步閱讀　529
9　PSPACE： A Class of Problems beyond NP / PSPACE：一類超出NP的問題　531
9．1　PSPACE / PSPACE　531
9．2　Some Hard Problems in PSPACE / PSPACE中的難問題　533
9．3　Solving Quantified Problems and Games in Polynomial Space / 在多項式空間中解量化問題和博弈問題　536
9．4　Solving the Planning Problem in Polynomial Space / 在多項式空間內(nèi)求解規(guī)劃問題　538
9．5　Proving Problems PSPACE-Complete / 證明問題是PSPACE完全的　543
Solved　Exercises / 帶解答的練習　547
Exercises　/ 練習　550
Notes　and Further Reading / 注釋和進一步閱讀　551
10　Extending the Limits of Tractability / 擴展易解性的界限　553
10．1　Finding Small Vertex Covers / 找小的頂點覆蓋　554
10．2　Solving NP-Hard Problems on Trees / 在樹上解NP難問題　558
10．3　Coloring a Set of Circular Arcs / 圓弧集著色　563
10．4 Tree Decompositions of Graphs / 圖的樹分解　572
10．5 Constructing a Tree Decomposition / 構造樹分解　584
Solved　Exercises / 帶解答的練習　591
Exercises　/ 練習　594
Notes　and Further Reading / 注釋和進一步閱讀　598
11　Approximation Algorithms / 近似算法　599
11．1　Greedy Algorithms and Bounds on the Optimum： A Load Balancing Problem / 貪心算法與最優(yōu)值的界限：負載均衡問題　600
11．2　The Center Selection Problem / 中心選址問題　606
11．3　Set Cover： A General Greedy Heuristic / 集合覆蓋：一般的貪心啟發(fā)式方法　612
11．4　The Pricing Method： Vertex Cover / 定價法：頂點覆蓋　618
11．5　Maximization via the Pricing Method： The Disjoint Paths Problem / 用定價法最大化：不交路徑問題　624
11．6　Linear Programming and Rounding： An Application to Vertex Cover / 線性規(guī)劃與舍入：對頂點覆蓋的應用　630
11．7 Load Balancing Revisited： A More Advanced LP Application / 再論負載均衡：更高級的LP應用　637
11．8　Arbitrarily Good Approximations： The Knapsack Problem / 任意好的近似：背包問題　644
Solved　Exercises / 帶解答的練習　649
Exercises　/ 練習　651
Notes　and Further Reading / 注釋和進一步閱讀　659
12　Local Search / 局部搜索　661
12．1　The Landscape of an Optimization Problem / 最優(yōu)化問題的地形圖　662
12．2　The Metropolis Algorithm and Simulated Annealing / Metropolis算法與模擬退火算法　666
12．3　An Application of Local Search to Hopfield Neural Networks / 局部搜索在Hopfield神經(jīng)網(wǎng)絡中的應用　671
12．4　Maximum-Cut Approximation via Local Search / 局部搜索對最大割近似的應用　676
12．5　Choosing a Neighbor Relation / 選擇鄰居關系　679
12．6 Classification via Local Search / 用局部搜索分類　681
12．7　Best-Response Dynamics and Nash Equilibria / 最佳響應動態(tài)過程與納什均衡　690
Solved　Exercises / 帶解答的練習　700
Exercises　/ 練習　702
Notes　and Further Reading / 注釋和進一步閱讀　705
13　Randomized Algorithms / 隨機算法　707
13．1　A First Application： Contention Resolution / 第 一個應用：消除爭用　708
13．2　Finding the Global Minimum Cut / 求完全最小割　714
13．3　Random Variables and Their Expectations / 隨機變量及其期望　719
13．4　A Randomized Approximation Algorithm for MAX 3-SAT / 關于MAX 3-SAT的隨機近似算法　724
13．5　Randomized Divide and Conquer： Median-Finding and Quicksort / 隨機分治策略：求中位數(shù)與快速排序　727
13．6　Hashing： A Randomized Implementation of Dictionaries / 散列法：字典的隨機實現(xiàn)　734
13．7　Finding the Closest Pair of Points： A Randomized Approach / 求最鄰近點對：隨機方法　741
13．8　Randomized Caching / 隨機超高速緩存　750
13．9　Chernoff Bounds / 切爾諾夫界　758
13．10　Load Balancing / 負載均衡　760
13．11　Packet Routing / 包路由選擇　762
13．12　Background： Some Basic Probability Definitions / 背景：某些基本概率定義　769
Solved　Exercises / 帶解答的練習　776
Exercises　/ 練習　782
Notes　and Further Reading / 注釋和進一步閱讀　793
Epilogue：　Algorithms That Run Forever / 后記：永不停止運行的算法　795
References　/ 參考文獻　805