About the Authors 

v  
Preface 

xiii  

Introduction: Some Representative Problems 


1  (28) 

A First Problem: Stable Matching 


1  (11) 

Five Representative Problems 


12  (17) 


19  (3) 


22  (6) 

Notes and Further Reading 


28  (1) 

Basics of Algorithm Analysis 


29  (44) 

Computational Tractability 


29  (6) 

Asymptotic Order of Growth 


35  (7) 

Implementing the Stable Matching Algorithm Using Lists and Arrays 


42  (5) 

A Survey of Common Running Times 


47  (10) 

A More Complex Data Structure: Priority Queues 


57  (16) 


65  (2) 


67  (3) 

Notes and Further Reading 


70  (3) 


73  (42) 

Basic Definitions and Applications 


73  (5) 

Graph Connectivity and Graph Traversal 


78  (9) 

Implementing Graph Traversal Using Queues and Stacks 


87  (7) 

Testing Bipartiteness: An Application of BreadthFirst Search 


94  (3) 

Connectivity in Directed Graphs 


97  (2) 

Directed Acyclic Graphs and Topological Ordering 


99  (16) 


104  (3) 


107  (5) 

Notes and Further Reading 


112  (3) 


115  (94) 

Interval Scheduling: The Greedy Algorithm Stays Ahead 


116  (9) 

Scheduling to Minimize Lateness: An Exchange Argument 


125  (6) 

Optimal Caching: A More Complex Exchange Argument 


131  (6) 

Shortest Paths in a Graph 


137  (5) 

The Minimum Spanning Tree Problem 


142  (9) 

Implementing Kruskal's Algorithm: The UnionFind Data Structure 


151  (6) 


157  (4) 

Huffman Codes and Data Compression 


161  (16) 

MinimumCost Arborescences: A MultiPhase Greedy Algorithm 


177  (32) 


183  (5) 


188  (17) 

Notes and Further Reading 


205  (4) 


209  (42) 

A First Recurrence: The Mergesort Algorithm 


210  (4) 

Further Recurrence Relations 


214  (7) 


221  (4) 

Finding the Closest Pair of Points 


225  (6) 


231  (3) 

Convolutions and the Fast Fourier Transform 


234  (17) 


242  (4) 


246  (3) 

Notes and Further Reading 


249  (2) 


251  (86) 

Weighted Interval Scheduling: A Recursive Procedure 


252  (6) 

Principles of Dynamic Programming: Memoization or Iteration over Subproblems 


258  (3) 

Segmented Least Squares: Multiway Choices 


261  (5) 

Subset Sums and Knapsacks: Adding a Variable 


266  (6) 

RNA Secondary Structure: Dynamic Programming over Intervals 


272  (6) 


278  (6) 

Sequence Alignment in Linear Space via Divide and Conquer 


284  (6) 

Shortest Paths in a Graph 


290  (7) 

Shortest Paths and Distance Vector Protocols 


297  (4) 

Negative Cycles in a Graph 


301  (36) 


307  (5) 


312  (23) 

Notes and Further Reading 


335  (2) 


337  (114) 

The MaximumFlow Problem and the FordFulkerson Algorithm 


338  (8) 

Maximum Flows and Minimum Cuts in a Network 


346  (6) 

Choosing Good Augmenting Paths 


352  (5) 

The PreflowPush MaximumFlow Algorithm 


357  (10) 

A First Application: The Bipartite Matching Problem 


367  (6) 

Disjoint Paths in Directed and Undirected Graphs 


373  (5) 

Extensions to the MaximumFlow Problem 


378  (6) 


384  (3) 


387  (4) 


391  (5) 


396  (4) 


400  (4) 

A Further Direction: Adding Costs to the Matching Problem 


404  (47) 


411  (4) 


415  (33) 

Notes and Further Reading 


448  (3) 

NP and Computational Intractability 


451  (80) 

PolynomialTime Reductions 


452  (7) 

Reductions via ``Gadgets'': The Satisfiability Problem 


459  (4) 

Efficient Certification and the Definition of NP 


463  (3) 


466  (7) 


473  (8) 


481  (4) 


485  (5) 


490  (5) 

CoNP and the Asymmetry of NP 


495  (2) 

A Partial Taxonomy of Hard Problems 


497  (34) 


500  (5) 


505  (24) 

Notes and Further Reading 


529  (2) 

Pspace: A Class of Problems beyond NP 


531  (22) 


531  (2) 

Some Hard Problems in Pspace 


533  (3) 

Solving Quantified Problems and Games in Polynomial Space 


536  (2) 

Solving the Planning Problem in Polynomial Space 


538  (5) 

Proving Problems PspaceComplete 


543  (10) 


547  (3) 


550  (1) 

Notes and Further Reading 


551  (2) 

Extending the Limits of Tractability 


553  (46) 

Finding Small Vertex Covers 


554  (4) 

Solving NPHard Problems on Trees 


558  (5) 

Coloring a Set of Circular Arcs 


563  (9) 

Tree Decompositions of Graphs 


572  (12) 

Constructing a Tree Decomposition 


584  (15) 


591  (3) 


594  (4) 

Notes and Further Reading 


598  (1) 


599  (62) 

Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem 


600  (6) 

The Center Selection Problem 


606  (6) 

Set Cover: A General Greedy Heuristic 


612  (6) 

The Pricing Method: Vertex Cover 


618  (6) 

Maximization via the Pricing Method: The Disjoint Paths Problem 


624  (6) 

Linear Programming and Rounding: An Application to Vertex Cover 


630  (7) 

Load Balancing Revisited: A More Advanced LP Application 


637  (7) 

Arbitrarily Good Approximations: The Knapsack Problem 


644  (17) 


649  (2) 


651  (8) 

Notes and Further Reading 


659  (2) 


661  (46) 

The Landscape of an Optimization Problem 


662  (4) 

The Metropolis Algorithm and Simulated Annealing 


666  (5) 

An Application of Local Search to Hopfield Neural Networks 


671  (5) 

MaximumCut Approximation via Local Search 


676  (3) 

Choosing a Neighbor Relation 


679  (2) 

Classification via Local Search 


681  (9) 

BestResponse Dynamics and Nash Equilibria 


690  (17) 


700  (2) 


702  (3) 

Notes and Further Reading 


705  (2) 


707  (88) 

A First Application: Contention Resolution 


708  (6) 

Finding the Global Minimum Cut 


714  (5) 

Random Variables and Their Expectations 


719  (5) 

A Randomized Approximation Algorithm for MAX 3SAT 


724  (3) 

Randomized Divide and Conquer: MedianFinding and Quicksort 


727  (7) 

Hashing: A Randomized Implementation of Dictionaries 


734  (7) 

Finding the Closest Pair of Points: A Randomized Approach 


741  (9) 


750  (8) 


758  (2) 


760  (2) 


762  (7) 

Background: Some Basic Probability Definitions 


769  (26) 


776  (6) 


782  (11) 

Notes and Further Reading 


793  (2) 
Epilogue: Algorithms That Run Forever 

795  (10) 
References 

805  (10) 
Index 

815  