1 Introduction：Some Representative Problems 1
1.1 A First Problem：Stable Matching 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 42
2.4 A Survey of Common Running Times 47
2.5 A More Complex Data Structure：Priority Queues 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 87
3.4 Testing Bipartiteness：An Application of Breadth-First Search 94
3.5 Connectivity in Directed Graphs 97
3.6 Directed Acyclic Graphs and Topological Ordering 99
Solved Exercises 104
Exercises 107
Notes and Further Reading 112
4 Greedy Algorithms 115
4.1 Interval Scheduling：The Greedy Algorithm Stays Ahead 116
4.2 Scheduling to Minimize Lateness：An Exchange Argument 125
4.3 Optimal Caching：A More Complex Exchange Argument 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 151
4.7 Clustering 157
4.8 Huffman Codes and Data Compression 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 221
5.4 Finding the Closest Pair of Points 225
5.5 Integer Multiplication 231
5.6 Convolutions and the Fast Fourier Transform 234
Solved Exercises 242
Exercises 246
Notes and Further Reading 249
6 Dynamic Programming 251
6.1 Weighted Interval Scheduling：A Recursive Procedure 252
6.2 Principles of Dynamic Programming：Memoization or Iteration over Subproblems 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 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 297
6.10 Negative Cycles in a Graph 301
Solved Exercises 307
Exercises 312
Notes and Further Reading 335
7 Network Flow 337
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm 338
7.2 Maximum Flows and Minimum Cuts in a Network 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 384
7.9 Airline Scheduling 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 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 463
8.4 NP-Complete Problems 466
8.5 Sequencing Problems 473
8.6 Partitioning Problems 481
8.7 Graph Coloring 485
8.8 Numerical Problems 490
8.9 Co-NP and the Asymmetry of 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 531
9.1 PSPACE 531
9.2 Some Hard Problems in PSPACE 533
9.3 Solving Quantified Problems and Games in Polynomial Space 536
9.4 Solving the Planning Problem in Polynomial Space 538
9.5 Proving Problems PSPACE-Complete 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 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 600
11.2 The Center Selection Problem 606
11.3 Set Cover：A General Greedy Heuristic 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 630
11.7 Load Balancing Revisited：A More Advanced LP Application 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 662
12.2 The Metropolis Algorithm and Simulated Annealing 666
12.3 An Application of Local Search to Hopfield Neural Networks 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 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 724
13.5 Randomized Divide and Conquer：Median-Finding and Quicksort 727
13.6 Hashing：A Randomized Implementation of Dictionaries 734
13.7 Finding the Closest Pair of Points：A Randomized Approach 741
13.8 Randomized Caching 750
13.9 Chemoff 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
Index 815