Algorithm Design, 1st edition

Algorithm Design

Jon Kleinberg and Eva Tardos

1. Introduction: Some Representative Problems
   • 1.1 A First Problem: Stable Matching
   • 1.2 Five Representative Problems
   • Solved Exercises
   • Excercises
   • Notes and Further Reading
2. Basics of Algorithms Analysis
   • 2.1 Computational Tractability
   • 2.2 Asymptotic Order of Growth Notation
   • 2.3 Implementing the Stable Matching Algorithm using Lists and Arrays
   • 2.4 A Survey of Common Running Times
   • 2.5 A More Complex Data Structure: Priority Queues
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
3. Graphs
   • 3.1 Basic Definitions and Applications
   • 3.2 Graph Connectivity and Graph Traversal
   • 3.3 Implementing Graph Traversal using Queues and Stacks
   • 3.4 Testing Bipartiteness: An Application of Breadth-First Search
   • 3.5 Connectivity in Directed Graphs
   • 3.6 Directed Acyclic Graphs and Topological Ordering
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
4. Greedy Algorithms
   • 4.1 Interval Scheduling: The Greedy Algorithm Stays Ahead
   • 4.2 Scheduling to Minimize Lateness: An Exchange Argument
   • 4.3 Optimal Caching: A More Complex Exchange Argument
   • 4.4 Shortest Paths in a Graph
   • 4.5 The Minimum Spanning Tree Problem
   • 4.6 Implementing Kruskal's Algorithm: The Union-Find Data Structure
   • 4.7 Clustering
   • 4.8 Huffman Codes and the Problem of Data Compression
   • *4.9 Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm
   • Solved Exercises
   • Excercises
   • Notes and Further Reading
5. Divide and Conquer
   • 5.1 A First Recurrence: The Mergesort Algorithm
   • 5.2 Further Recurrence Relations
   • 5.3 Counting Inversions
   • 5.4 Finding the Closest Pair of Points
   • 5.5 Integer Multiplication
   • 5.6 Convolutions and The Fast Fourier Transform
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
6. Dynamic Programming
   • 6.1 Weighted Interval Scheduling: A Recursive Procedure
   • 6.2 Weighted Interval Scheduling: Iterating over Sub-Problems
   • 6.3 Segmented Least Squares: Multi-way Choices
   • 6.4 Subset Sums and Knapsacks: Adding a Variable
   • 6.5 RNA Secondary Structure: Dynamic Programming Over Intervals
   • 6.6 Sequence Alignment
   • 6.7 Sequence Alignment in Linear Space
   • 6.8 Shortest Paths in a Graph
   • 6.9 Shortest Paths and Distance Vector Protocols
   • *6.10 Negative Cycles in a Graph
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
7. Network Flow
   • 7.1 The Maximum Flow Problem and the Ford-Fulkerson Algorithm
   • 7.2 Maximum Flows and Minimum Cuts in a Network
   • 7.3 Choosing Good Augmenting Paths
   • *7.4 The Preflow-Push Maximum Flow Algorithm
   • 7.5 A First Application: The Bipartite Matching Problem
   • 7.6 Disjoint Paths in Directed and Undirected Graphs
   • 7.7 Extensions to the Maximum Flow Problem
   • 7.8 Survey Design
   • 7.9 Airline Scheduling
   • 7.10 Image Segmentation
   • 7.11 Project Selection
   • 7.12 Baseball Elimination
   • *7.13 A Further Direction: Adding Costs to the Matching Problem
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
8. NP and Computational Intractability
   • 8.1 Polynomial-Time Reductions
   • 8.2 Reductions via "Gadgets": The Satisfiability Problem
   • 8.3 Efficient Certification and the Definition of NP
   • 8.4 NP-Complete Problems
   • 8.5 Sequencing Problems
   • 8.6 Partitioning Problems
   • 8.7 Graph Coloring
   • 8.8 Numerical Problems
   • 8.9 Co-NP and the Asymmetry of NP
   • 8.10 A Partial Taxonomy of Hard Problems
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
9. PSPACE: A Class of Problems Beyond NP
   • 9.1 PSPACE
   • 9.2 Some Hard Problems in PSPACE
   • 9.3 Solving Quantified Problems and Games in Polynomial Space
   • 9.4 Solving the Planning Problem in Polynomial Space
   • 9.5 Proving Problems PSPACE-Complete
   • Solved Exercises
   • Exercises
   • Notes and Further Reading
10. Extending the Limits of Tractability
    • 10.1 Finding Small Vertex Covers
    • 10.2 Solving NP-Hard Problem on Trees
    • 10.3 Coloring a Set of Circular Arcs
    • *10.4 Tree Decompositions of Graphs
    • *10.5 Constructing a Tree Decomposition
    • Solved Exercises
    • Exercises
    • Notes and Further Reading
11. Approximation Algorithms
    • 11.1 Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem
    • 11.2 The Center Selection Problem
    • 11.3 Set Cover: A General Greedy Heuristic
    • 11.4 The Pricing Method: Vertex Cover
    • 11.5 Maximization via the Pricing method: The Disjoint Paths Problem
    • 11.6 Linear Programming and Rounding: An Application to Vertex Cover
    • *11.7 Load Balancing Revisited: A More Advanced LP Application
    • 11.8 Arbitrarily Good Approximations: the Knapsack Problem
    • Solved Exercises
    • Exercises
    • Notes and Further Reading
12. Local Search
    • 12.1 The Landscape of an Optimization Problem
    • 12.2 The Metropolis Algorithm and Simulated Annealing
    • 12.3 An Application of Local Search to Hopfield Neural Networks
    • 12.4 Maximum Cut Approximation via Local Search
    • 12.5 Choosing a Neighbor Relation
    • *12.6 Classification via Local Search
    • 12.7 Best-Response Dynamics and Nash Equilibria
    • Solved Exercises
    • Exercises
    • Notes and Further Reading
13. Randomized Algorithms
    • 13.1 A First Application: Contention Resolution
    • 13.2 Finding the Global Minimum Cut
    • 13.3 Random Variables and their Expectations
    • 13.4 A Randomized Approximation Algorithm for MAX 3-SAT
    • 13.5 Randomized Divide-and-Conquer: Median-Finding and Quicksort
    • 13.6 Hashing: A Randomized Implementation of Dictionaries
    • 13.7 Finding the Closest Pair of Points: A Randomized Approach
    • 13.8 Randomized Caching
    • 13.9 Chernoff Bounds
    • 13.10 Load Balancing
    • *13.11 Packet Routing
    • 13.12 Background: Some Basic Probability Definitions
    • Solved Exercises
    • Exercises
    • Notes and Further Reading

Epilogue: Algorithms that Run Forever

References

Index