| |
| |
| About the Authors | |
| |
| |
| Preface | |
| |
| |
| |
| Introduction: Some Representative Problems | |
| |
| |
| |
| A First Problem: Stable Matching | |
| |
| |
| |
| Five Representative Problems | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Basics of Algorithm Analysis | |
| |
| |
| |
| Computational Tractability | |
| |
| |
| |
| Asymptotic Order of Growth | |
| |
| |
| |
| Implementing the Stable Matching Algorithm Using Lists and Arrays | |
| |
| |
| |
| A Survey of Common Running Times | |
| |
| |
| |
| A More Complex Data Structure: Priority Queues | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Graphs | |
| |
| |
| |
| Basic Definitions and Applications | |
| |
| |
| |
| Graph Connectivity and Graph Traversal | |
| |
| |
| |
| Implementing Graph Traversal Using Queues and Stacks | |
| |
| |
| |
| Testing Bipartiteness: An Application of Breadth-First Search | |
| |
| |
| |
| Connectivity in Directed Graphs | |
| |
| |
| |
| Directed Acyclic Graphs and Topological Ordering | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Greedy Algorithms | |
| |
| |
| |
| Interval Scheduling: The Greedy Algorithm Stays Ahead | |
| |
| |
| |
| Scheduling to Minimize Lateness: An Exchange Argument | |
| |
| |
| |
| Optimal Caching: A More Complex Exchange Argument | |
| |
| |
| |
| Shortest Paths in a Graph | |
| |
| |
| |
| The Minimum Spanning Tree Problem | |
| |
| |
| |
| Implementing Kruskal's Algorithm: The Union-Find Data Structure | |
| |
| |
| |
| Clustering | |
| |
| |
| |
| Huffman Codes and Data Compression | |
| |
| |
| |
| Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Divide and Conquer | |
| |
| |
| |
| A First Recurrence: The Mergesort Algorithm | |
| |
| |
| |
| Further Recurrence Relations | |
| |
| |
| |
| Counting Inversions | |
| |
| |
| |
| Finding the Closest Pair of Points | |
| |
| |
| |
| Integer Multiplication | |
| |
| |
| |
| Convolutions and the Fast Fourier Transform | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Dynamic Programming | |
| |
| |
| |
| Weighted Interval Scheduling: A Recursive Procedure | |
| |
| |
| |
| Principles of Dynamic Programming: Memoization or Iteration over Subproblems | |
| |
| |
| |
| Segmented Least Squares: Multi-way Choices | |
| |
| |
| |
| Subset Sums and Knapsacks: Adding a Variable | |
| |
| |
| |
| RNA Secondary Structure: Dynamic Programming over Intervals | |
| |
| |
| |
| Sequence Alignment | |
| |
| |
| |
| Sequence Alignment in Linear Space via Divide and Conquer | |
| |
| |
| |
| Shortest Paths in a Graph | |
| |
| |
| |
| Shortest Paths and Distance Vector Protocols | |
| |
| |
| |
| Negative Cycles in a Graph | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Network Flow | |
| |
| |
| |
| The Maximum-Flow Problem and the Ford-Fulkerson Algorithm | |
| |
| |
| |
| Maximum Flows and Minimum Cuts in a Network | |
| |
| |
| |
| Choosing Good Augmenting Paths | |
| |
| |
| |
| The Preflow-Push Maximum-Flow Algorithm | |
| |
| |
| |
| A First Application: The Bipartite Matching Problem | |
| |
| |
| |
| Disjoint Paths in Directed and Undirected Graphs | |
| |
| |
| |
| Extensions to the Maximum-Flow Problem | |
| |
| |
| |
| Survey Design | |
| |
| |
| |
| Airline Scheduling | |
| |
| |
| |
| Image Segmentation | |
| |
| |
| |
| Project Selection | |
| |
| |
| |
| Baseball Elimination | |
| |
| |
| |
| A Further Direction: Adding Costs to the Matching Problem | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| NP and Computational Intractability | |
| |
| |
| |
| Polynomial-Time Reductions | |
| |
| |
| |
| Reductions via "Gadgets": The Satisfiability Problem | |
| |
| |
| |
| Efficient Certification and the Definition of NP | |
| |
| |
| |
| NP-Complete Problems | |
| |
| |
| |
| Sequencing Problems | |
| |
| |
| |
| Partitioning Problems | |
| |
| |
| |
| Graph Coloring | |
| |
| |
| |
| Numerical Problems | |
| |
| |
| |
| Co-NP and the Asymmetry of NP | |
| |
| |
| |
| A Partial Taxonomy of Hard Problems | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| PSPACE: A Class of Problems beyond NP | |
| |
| |
| |
| PSPACE | |
| |
| |
| |
| Some Hard Problems in PSPACE | |
| |
| |
| |
| Solving Quantified Problems and Games in Polynomial Space | |
| |
| |
| |
| Solving the Planning Problem in Polynomial Space | |
| |
| |
| |
| Proving Problems PSPACE-Complete | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Extending the Limits of Tractability | |
| |
| |
| |
| Finding Small Vertex Covers | |
| |
| |
| |
| Solving NP-Hard Problems on Trees | |
| |
| |
| |
| Coloring a Set of Circular Arcs | |
| |
| |
| |
| Tree Decompositions of Graphs | |
| |
| |
| |
| Constructing a Tree Decomposition | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Approximation Algorithms | |
| |
| |
| |
| Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem | |
| |
| |
| |
| The Center Selection Problem | |
| |
| |
| |
| Set Cover: A General Greedy Heuristic | |
| |
| |
| |
| The Pricing Method: Vertex Cover | |
| |
| |
| |
| Maximization via the Pricing Method: The Disjoint Paths Problem | |
| |
| |
| |
| Linear Programming and Rounding: An Application to Vertex Cover | |
| |
| |
| |
| Load Balancing Revisited: A More Advanced LP Application | |
| |
| |
| |
| Arbitrarily Good Approximations: The Knapsack Problem | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Local Search | |
| |
| |
| |
| The Landscape of an Optimization Problem | |
| |
| |
| |
| The Metropolis Algorithm and Simulated Annealing | |
| |
| |
| |
| An Application of Local Search to Hopfield Neural Networks | |
| |
| |
| |
| Maximum-Cut Approximation via Local Search | |
| |
| |
| |
| Choosing a Neighbor Relation | |
| |
| |
| |
| Classification via Local Search | |
| |
| |
| |
| Best-Response Dynamics and Nash Equilibria | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| |
| Randomized Algorithms | |
| |
| |
| |
| A First Application: Contention Resolution | |
| |
| |
| |
| Finding the Global Minimum Cut | |
| |
| |
| |
| Random Variables and Their Expectations | |
| |
| |
| |
| A Randomized Approximation Algorithm for MAX 3-SAT | |
| |
| |
| |
| Randomized Divide and Conquer: Median-Finding and Quicksort | |
| |
| |
| |
| Hashing: A Randomized Implementation of Dictionaries | |
| |
| |
| |
| Finding the Closest Pair of Points: A Randomized Approach | |
| |
| |
| |
| Randomized Caching | |
| |
| |
| |
| Chernoff Bounds | |
| |
| |
| |
| Load Balancing | |
| |
| |
| |
| Packet Routing | |
| |
| |
| |
| Background: Some Basic Probability Definitions | |
| |
| |
| Solved Exercises | |
| |
| |
| Exercises | |
| |
| |
| Notes and Further Reading | |
| |
| |
| Epilogue: Algorithms That Run Forever | |
| |
| |
| References | |
| |
| |
| Index | |