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