Algorithm Design

by Kleinberg, Jon; Tardos, Éva

• ISBN13: 9780321295354
• ISBN10: 0321295358
• Edition: 1st
• Format: Paperback
• Copyright: 2005-03-16
• Publisher: Pearson

Summary

Algorithm Designintroduces algorithms by looking at the real-world problems that motivate them. The book teaches a range of design and analysis techniques for problems that arise in computing applications. The text encourages an understanding of the algorithm design process and an appreciation of the role of algorithms in the broader field of computer science.

Author Biography

Eva Tardos is a professor of Computer Science at Cornell University.

Table of Contents

About the Authors	v
Preface	xiii
Introduction: Some Representative Problems	1	(28)
A First Problem: Stable Matching	1	(11)
Five Representative Problems	12	(17)
Solved Exercises	19	(3)
Exercises	22	(6)
Notes and Further Reading	28	(1)
Basics of Algorithm Analysis	29	(44)
Computational Tractability	29	(6)
Asymptotic Order of Growth	35	(7)
Implementing the Stable Matching Algorithm Using Lists and Arrays	42	(5)
A Survey of Common Running Times	47	(10)
A More Complex Data Structure: Priority Queues	57	(16)
Solved Exercises	65	(2)
Exercises	67	(3)
Notes and Further Reading	70	(3)
Graphs	73	(42)
Basic Definitions and Applications	73	(5)
Graph Connectivity and Graph Traversal	78	(9)
Implementing Graph Traversal Using Queues and Stacks	87	(7)
Testing Bipartiteness: An Application of Breadth-First Search	94	(3)
Connectivity in Directed Graphs	97	(2)
Directed Acyclic Graphs and Topological Ordering	99	(16)
Solved Exercises	104	(3)
Exercises	107	(5)
Notes and Further Reading	112	(3)
Greedy Algorithms	115	(94)
Interval Scheduling: The Greedy Algorithm Stays Ahead	116	(9)
Scheduling to Minimize Lateness: An Exchange Argument	125	(6)
Optimal Caching: A More Complex Exchange Argument	131	(6)
Shortest Paths in a Graph	137	(5)
The Minimum Spanning Tree Problem	142	(9)
Implementing Kruskal's Algorithm: The Union-Find Data Structure	151	(6)
Clustering	157	(4)
Huffman Codes and Data Compression	161	(16)
Minimum-Cost Arborescences: A Multi-Phase Greedy Algorithm	177	(32)
Solved Exercises	183	(5)
Exercises	188	(17)
Notes and Further Reading	205	(4)
Divide and Conquer	209	(42)
A First Recurrence: The Mergesort Algorithm	210	(4)
Further Recurrence Relations	214	(7)
Counting Inversions	221	(4)
Finding the Closest Pair of Points	225	(6)
Integer Multiplication	231	(3)
Convolutions and the Fast Fourier Transform	234	(17)
Solved Exercises	242	(4)
Exercises	246	(3)
Notes and Further Reading	249	(2)
Dynamic Programming	251	(86)
Weighted Interval Scheduling: A Recursive Procedure	252	(6)
Principles of Dynamic Programming: Memoization or Iteration over Subproblems	258	(3)
Segmented Least Squares: Multi-way Choices	261	(5)
Subset Sums and Knapsacks: Adding a Variable	266	(6)
RNA Secondary Structure: Dynamic Programming over Intervals	272	(6)
Sequence Alignment	278	(6)
Sequence Alignment in Linear Space via Divide and Conquer	284	(6)
Shortest Paths in a Graph	290	(7)
Shortest Paths and Distance Vector Protocols	297	(4)
Negative Cycles in a Graph	301	(36)
Solved Exercises	307	(5)
Exercises	312	(23)
Notes and Further Reading	335	(2)
Network Flow	337	(114)
The Maximum-Flow Problem and the Ford-Fulkerson Algorithm	338	(8)
Maximum Flows and Minimum Cuts in a Network	346	(6)
Choosing Good Augmenting Paths	352	(5)
The Preflow-Push Maximum-Flow Algorithm	357	(10)
A First Application: The Bipartite Matching Problem	367	(6)
Disjoint Paths in Directed and Undirected Graphs	373	(5)
Extensions to the Maximum-Flow Problem	378	(6)
Survey Design	384	(3)
Airline Scheduling	387	(4)
Image Segmentation	391	(5)
Project Selection	396	(4)
Baseball Elimination	400	(4)
A Further Direction: Adding Costs to the Matching Problem	404	(47)
Solved Exercises	411	(4)
Exercises	415	(33)
Notes and Further Reading	448	(3)
NP and Computational Intractability	451	(80)
Polynomial-Time Reductions	452	(7)
Reductions via ``Gadgets'': The Satisfiability Problem	459	(4)
Efficient Certification and the Definition of NP	463	(3)
NP-Complete Problems	466	(7)
Sequencing Problems	473	(8)
Partitioning Problems	481	(4)
Graph Coloring	485	(5)
Numerical Problems	490	(5)
Co-NP and the Asymmetry of NP	495	(2)
A Partial Taxonomy of Hard Problems	497	(34)
Solved Exercises	500	(5)
Exercises	505	(24)
Notes and Further Reading	529	(2)
Pspace: A Class of Problems beyond NP	531	(22)
Pspace	531	(2)
Some Hard Problems in Pspace	533	(3)
Solving Quantified Problems and Games in Polynomial Space	536	(2)
Solving the Planning Problem in Polynomial Space	538	(5)
Proving Problems Pspace-Complete	543	(10)
Solved Exercises	547	(3)
Exercises	550	(1)
Notes and Further Reading	551	(2)
Extending the Limits of Tractability	553	(46)
Finding Small Vertex Covers	554	(4)
Solving NP-Hard Problems on Trees	558	(5)
Coloring a Set of Circular Arcs	563	(9)
Tree Decompositions of Graphs	572	(12)
Constructing a Tree Decomposition	584	(15)
Solved Exercises	591	(3)
Exercises	594	(4)
Notes and Further Reading	598	(1)
Approximation Algorithms	599	(62)
Greedy Algorithms and Bounds on the Optimum: A Load Balancing Problem	600	(6)
The Center Selection Problem	606	(6)
Set Cover: A General Greedy Heuristic	612	(6)
The Pricing Method: Vertex Cover	618	(6)
Maximization via the Pricing Method: The Disjoint Paths Problem	624	(6)
Linear Programming and Rounding: An Application to Vertex Cover	630	(7)
Load Balancing Revisited: A More Advanced LP Application	637	(7)
Arbitrarily Good Approximations: The Knapsack Problem	644	(17)
Solved Exercises	649	(2)
Exercises	651	(8)
Notes and Further Reading	659	(2)
Local Search	661	(46)
The Landscape of an Optimization Problem	662	(4)
The Metropolis Algorithm and Simulated Annealing	666	(5)
An Application of Local Search to Hopfield Neural Networks	671	(5)
Maximum-Cut Approximation via Local Search	676	(3)
Choosing a Neighbor Relation	679	(2)
Classification via Local Search	681	(9)
Best-Response Dynamics and Nash Equilibria	690	(17)
Solved Exercises	700	(2)
Exercises	702	(3)
Notes and Further Reading	705	(2)
Randomized Algorithms	707	(88)
A First Application: Contention Resolution	708	(6)
Finding the Global Minimum Cut	714	(5)
Random Variables and Their Expectations	719	(5)
A Randomized Approximation Algorithm for MAX 3-SAT	724	(3)
Randomized Divide and Conquer: Median-Finding and Quicksort	727	(7)
Hashing: A Randomized Implementation of Dictionaries	734	(7)
Finding the Closest Pair of Points: A Randomized Approach	741	(9)
Randomized Caching	750	(8)
Chernoff Bounds	758	(2)
Load Balancing	760	(2)
Packet Routing	762	(7)
Background: Some Basic Probability Definitions	769	(26)
Solved Exercises	776	(6)
Exercises	782	(11)
Notes and Further Reading	793	(2)
Epilogue: Algorithms That Run Forever	795	(10)
References	805	(10)
Index	815