Algorithm Design
Jon Kleinberg and Eva Tardos
Table of Contents
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
Ask a Question About this Product More... |