Algorithm Design

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.

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

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

What is included with this book?

The New copy of this book will include any supplemental materials advertised. Please check the title of the book to determine if it should include any access cards, study guides, lab manuals, CDs, etc.

The Used, Rental and eBook copies of this book are not guaranteed to include any supplemental materials. Typically, only the book itself is included. This is true even if the title states it includes any access cards, study guides, lab manuals, CDs, etc.

FREE SHIPPING

Amazon no longer offers textbook rentals. We do!

Summary

Author Biography

Table of Contents

Supplemental Materials