Algorithm Design

Cover......Page 1
Title Page......Page 5
Copyright Page......Page 6
Contents......Page 9
About the Authors......Page 7
Preface......Page 15
Acknowledgments......Page 23
1.1 A First Problem: Stable Matching......Page 27
1.2 Five Representative Problems......Page 38
Solved Exercises......Page 45
Exercises......Page 48
Notes and Further Reading......Page 54
2.1 Computational Tractability......Page 55
2.2 Asymptotic Order of Growth......Page 61
2.3 Implementing the Stable Matching Algorithm Using Lists and Arrays......Page 68
2.4 A Survey of Common Running Times......Page 73
2.5 A More Complex Data Structure: Priority Queues......Page 83
Solved Exercises......Page 91
Exercises......Page 93
Notes and Further Reading......Page 96
3.1 Basic Definitions and Applications......Page 99
3.2 Graph Connectivity and Graph Traversal......Page 104
3.3 Implementing Graph Traversal Using Queues and Stacks......Page 113
3.4 Testing Bipartiteness: An Application of Breadth-First Search......Page 120
3.5 Connectivity in Directed Graphs......Page 123
3.6 Directed Acyclic Graphs and Topological Ordering......Page 125
Solved Exercises......Page 130
Exercises......Page 133
Notes and Further Reading......Page 138
4 Greedy Algorithms......Page 141
4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead......Page 142
4.2 Scheduling to Minimize Lateness: An Exchange Argument......Page 151
4.3 Optimal Caching: A More Complex Exchange Argument......Page 157
4.4 Shortest Paths in a Graph......Page 163
4.5 The Minimum Spanning Tree Problem......Page 168
4.6 Implementing Kruskal?s Algorithm: The Union-Find Data Structure......Page 177
4.7 Clustering......Page 183
4.8 Huffman Codes and Data Compression......Page 187
*4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm......Page 203
Solved Exercises......Page 209
Exercises......Page 214
Notes and Further Reading......Page 231
5 Divide and Conquer......Page 235
5.1 A First Recurrence: The Mergesort Algorithm......Page 236
5.2 Further Recurrence Relations......Page 240
5.3 Counting Inversions......Page 247
5.4 Finding the Closest Pair of Points......Page 251
5.5 Integer Multiplication......Page 257
5.6 Convolutions and the Fast Fourier Transform......Page 260
Solved Exercises......Page 268
Exercises......Page 272
Notes and Further Reading......Page 275
6 Dynamic Programming......Page 277
6.1 Weighted Interval Scheduling: A Recursive Procedure......Page 278
6.2 Principles of Dynamic Programming: Memoization or Iteration over Subproblems......Page 284
6.3 Segmented Least Squares: Multi-way Choices......Page 287
6.4 Subset Sums and Knapsacks: Adding a Variable......Page 292
6.5 RNA Secondary Structure: Dynamic Programming over Intervals......Page 298
6.6 Sequence Alignment......Page 304
6.7 Sequence Alignment in Linear Space via Divide and Conquer......Page 310
6.8 Shortest Paths in a Graph......Page 316
6.9 Shortest Paths and Distance Vector Protocols......Page 323
*6.10 Negative Cycles in a Graph......Page 327
Solved Exercises......Page 333
Exercises......Page 338
Notes and Further Reading......Page 361
7 Network Flow......Page 363
7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm......Page 364
7.2 Maximum Flows and Minimum Cuts in a Network......Page 372
7.3 Choosing Good Augmenting Paths......Page 378
*7.4 The Preflow-Push Maximum-Flow Algorithm......Page 383
7.5 A First Application: The Bipartite Matching Problem......Page 393
7.6 Disjoint Paths in Directed and Undirected Graphs......Page 399
7.7 Extensions to the Maximum-Flow Problem......Page 404
7.8 Survey Design......Page 410
7.9 Airline Scheduling......Page 413
7.10 Image Segmentation......Page 417
7.11 Project Selection......Page 422
7.12 Baseball Elimination......Page 426
*7.13 A Further Direction: Adding Costs to the Matching Problem......Page 430
Solved Exercises......Page 437
Exercises......Page 441
Notes and Further Reading......Page 474
8 NP and Computational Intractability......Page 477
8.1 Polynomial-Time Reductions......Page 478
8.2 Reductions via ?Gadgets?: The Satisfiability Problem......Page 485
8.3 Efficient Certification and the Definition of NP......Page 489
8.4 NP-Complete Problems......Page 492
8.5 Sequencing Problems......Page 499
8.6 Partitioning Problems......Page 507
8.7 Graph Coloring......Page 511
8.8 Numerical Problems......Page 516
8.9 Co-NP and the Asymmetry of NP......Page 521
8.10 A Partial Taxonomy of Hard Problems......Page 523
Solved Exercises......Page 526
Exercises......Page 531
Notes and Further Reading......Page 555
9.1 PSPACE......Page 557
9.2 Some Hard Problems in PSPACE......Page 559
9.3 Solving Quanti.ed Problems and Games in Polynomial Space......Page 562
9.4 Solving the Planning Problem in Polynomial Space......Page 564
9.5 Proving Problems PSPACE-Complete......Page 569
Solved Exercises......Page 573
Exercises......Page 576
Notes and Further Reading......Page 577
10 Extending the Limits of Tractability......Page 579
10.1 Finding Small Vertex Covers......Page 580
10.2 Solving NP-Hard Problems on Trees......Page 584
10.3 Coloring a Set of Circular Arcs......Page 589
*10.4 Tree Decompositions of Graphs......Page 598
*10.5 Constructing a Tree Decomposition......Page 610
Solved Exercises......Page 617
Exercises......Page 620
Notes and Further Reading......Page 624
11 Approximation Algorithms......Page 625
11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem......Page 626
11.2 The Center Selection Problem......Page 632
11.3 Set Cover: A General Greedy Heuristic......Page 638
11.4 The Pricing Method: Vertex Cover......Page 644
11.5 Maximization via the Pricing Method: The Disjoint Paths Problem......Page 650
11.6 Linear Programming and Rounding: An Application to Vertex Cover......Page 656
*11.7 Load Balancing Revisited: A More Advanced LP Application......Page 663
11.8 Arbitrarily Good Approximations: The Knapsack Problem......Page 670
Solved Exercises......Page 675
Exercises......Page 677
Notes and Further Reading......Page 685
12 Local Search......Page 687
12.1 The Landscape of an Optimization Problem......Page 688
12.2 The Metropolis Algorithm and Simulated Annealing......Page 692
12.3 An Application of Local Search to Hopfield Neural Networks......Page 697
12.4 Maximum-Cut Approximation via Local Search......Page 702
12.5 Choosing a Neighbor Relation......Page 705
*12.6 Classification via Local Search......Page 707
12.7 Best-Response Dynamics and Nash Equilibria......Page 716
Solved Exercises......Page 726
Exercises......Page 728
Notes and Further Reading......Page 731
13 Randomized Algorithms......Page 733
13.1 A First Application: Contention Resolution......Page 734
13.2 Finding the Global Minimum Cut......Page 740
13.3 Random Variables and Their Expectations......Page 745
13.4 A Randomized Approximation Algorithm for MAX 3-SAT......Page 750
13.5 Randomized Divide and Conquer: Median-Finding and Quicksort......Page 753
13.6 Hashing: A Randomized Implementation of Dictionaries......Page 760
13.7 Finding the Closest Pair of Points: A Randomized Approach......Page 767
13.8 Randomized Caching......Page 776
13.9 Chernoff Bounds......Page 784
13.10 Load Balancing......Page 786
13.11 Packet Routing......Page 788
13.12 Background: Some Basic Probability Definitions......Page 795
Solved Exercises......Page 802
Exercises......Page 808
Notes and Further Reading......Page 819
Epilogue: Algorithms That Run Forever......Page 821
References......Page 831
A......Page 841
B......Page 842
C......Page 843
D......Page 846
E......Page 847
F......Page 848
G......Page 849
H......Page 850
I......Page 851
L......Page 852
M......Page 853
N......Page 855
O......Page 856
P......Page 857
R......Page 858
S......Page 860
T......Page 862
U......Page 863
Z......Page 864