Algorithm design

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 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
Index 815