Algorithm Design and Applications

“This is a wonderful book, covering both classical and contemporary topics in algorithms. I look forward to trying it out in my algorithms class. I especially like the diversity in topics and difficulty of the problems.”
ROBERT TARJAN, PRINCETON UNIVERSITY

“The clarity of explanation is excellent. I like the inclusion of the three types of exercises very much.”
MING-YANG KAO, NORTHWESTERN UNIVERSITY

“Goodrich and Tamassia have designed a book that is both remarkably comprehensive in its coverage and innovative in its approach. Their emphasis on motivation and applications, throughout the text as well as in the many exercises, provides a book well-designed for the boom in students from all areas of study who want to learn about computing. The book contains more than one could hope to cover in a semester course, giving instructors a great deal of flexibility and students a reference that they will turn to well after their class is over.”
MICHAEL MITZENMACHER, HARVARD UNIVERSITY

“I highly recommend this accessible roadmap to the world of algorithm design. The authors provide motivating examples of problems faced in the real world and guide the reader to develop workable solutions, with a number of challenging exercises to promote deeper understanding.”
JEFFREY S. VITTER, UNIVERSITY OF KANSAS

DidYouKnow?

This book is available as a Wiley E-Text.

The Wiley E-Text is a complete digital version of the text that makes time spent studying more efficient. Course materials can be accessed on a desktop, laptop, or mobile device—so that learning can take place anytime, anywhere.

A more affordable alternative to traditional print, the Wiley E-Text creates a flexible user experience:

• Access on-the-go
• Search across content
• Highlight and take notes
• Save money!

The Wiley E-Text can be purchased in the following ways:

Via your campus bookstore:
Wiley E-Text: Powered by VitalSource^®
ISBN 9781119028796
*Instructors: This ISBN is needed when placing an order.

Directly from:
www.wiley.com/college/goodrich

Preface xi

1 AlgorithmAnalysis 1

1.1 Analyzing Algorithms 3

1.2 A Quick Mathematical Review 19

1.3 A Case Study in Algorithm Analysis 29

1.4 Amortization 34

1.5 Exercises 42

Part I: Data Structures

2 BasicDataStructures 51

2.1 Stacks and Queues 53

2.2 Lists 60

2.3 Trees 68

2.4 Exercises 84

3 BinarySearchTrees 89

3.1 Searches and Updates 91

3.2 Range Queries 101

3.3 Index-Based Searching 104

3.4 Randomly-Constructed Search Trees 107

3.5 Exercises 110

4 BalancedBinarySearchTrees 115

4.1 Ranks and Rotations 117

4.2 AVL Trees 120

4.3 Red-Black Trees 126

4.4 Weak AVL Trees 130

4.5 Splay Trees 139

4.6 Exercises 149

5 PriorityQueuesandHeaps 155

5.1 Priority Queues 157

5.2 PQ-Sort, Selection-Sort, and Insertion-Sort 158

5.3 Heaps 163

5.4 Heap-Sort 174

5.5 Extending Priority Queues 179

5.6 Exercises 182

6 HashTables 187

6.1 Maps 189

6.2 Hash Functions 192

6.3 Handling Collisions and Rehashing 198

6.4 Cuckoo Hashing 206

6.5 Universal Hashing 212

6.6 Exercises 215

7 Union-FindStructures 219

7.1 Union-Find and its Applications 221

7.2 A List-Based Implementation 225

7.3 A Tree-Based Implementation 228

7.4 Exercises 236

Part II: Sorting and Selection

8 Merge-SortandQuick-Sort 241

8.1 Merge-Sort 243

8.2 Quick-Sort 250

8.3 A Lower Bound on Comparison-Based Sorting 257

8.4 Exercises 259

9 FastSortingandSelection 265

9.1 Bucket Sort and Radix Sort 267

9.2 Selection 270

9.3 Weighted Medians 276

9.4 Exercises 279

Part III: Fundamental Techniques

10 The Greedy Method 283

10.1 The Fractional Knapsack Problem 286

10.2 Task Scheduling 289

10.3 Text Compression and Huffman Coding 292

10.4 Exercises 298

11 Divide-and-Conquer 303

11.1 Recurrences and the Master Theorem 305

11.2 Integer Multiplication 313

11.3 Matrix Multiplication 315

11.4 The Maxima-Set Problem 317

11.5 Exercises 319

12 Dynamic Programming 323

12.1 Matrix Chain-Products 325

12.2 The General Technique 329

12.3 Telescope Scheduling 331

12.4 Game Strategies 334

12.5 The Longest Common Subsequence Problem 339

12.6 The 0-1 Knapsack Problem 343

12.7 Exercises 346

Part IV: Graph Algorithms

13 Graphs and Traversals 353

13.1 Graph Terminology and Representations 355

13.2 Depth-First Search 365

13.3 Breadth-First Search 370

13.4 Directed Graphs 373

13.5 Biconnected Components 386

13.6 Exercises 392

14 Shortest Paths 397

14.1 Single-Source Shortest Paths 399

14.2 Dijkstra’s Algorithm 400

14.3 The Bellman-Ford Algorithm 407

14.4 Shortest Paths in Directed Acyclic Graphs 410

14.5 All-Pairs Shortest Paths 412

14.6 Exercises 418

15 Minimum Spanning Trees 423

15.1 Properties of Minimum Spanning Trees 425

15.2 Kruskal’s Algorithm 428

15.3 The Prim-Jarn´ýk Algorithm 433

15.4 Bar°uvka’s Algorithm 436

15.5 Exercises 439

16 Network Flow and Matching 443

16.1 Flows and Cuts 445

16.2 Maximum Flow Algorithms 452

16.3 Maximum Bipartite Matching 458

16.4 Baseball Elimination 460

16.5 Minimum-Cost Flow 462

16.6 Exercises 469

Part V: Computational Intractability

17 NP-Completeness 473

17.1 P and NP 476

17.2 NP-Completeness 483

17.3 CNF-SAT and 3SAT 489

17.4 VERTEX-COVER, CLIQUE, and SET-COVER 492

17.5 SUBSET-SUM and KNAPSACK 496

17.6 HAMILTONIAN-CYCLE and TSP 499

17.7 Exercises 502

18 Approximation Algorithms 507

18.1 The Metric Traveling Salesperson Problem 511

18.2 Approximations for Covering Problems 515

18.3 Polynomial-Time Approximation Schemes 518

18.4 Backtracking and Branch-and-Bound 521

18.5 Exercises 525

Part VI: Additional Topics

19 Randomized Algorithms 529

19.1 Generating Random Permutations 531

19.2 Stable Marriages and Coupon Collecting 534

19.3 Minimum Cuts 539

19.4 Finding Prime Numbers 546

19.5 Chernoff Bounds 551

19.6 Skip Lists 557

19.7 Exercises 563

20 B-Trees and External-Memory 569

20.1 External Memory 571

20.2 (2,4) Trees and B-Trees 574

20.3 External-Memory Sorting 590

20.4 Online Caching Algorithms 593

20.5 Exercises 600

21 Multi-Dimensional Searching 603

21.1 Range Trees 605

21.2 Priority Search Trees 609

21.3 Quadtrees and k-D Trees 614

21.4 Exercises 618

22 Computational Geometry 623

22.1 Operations on Geometric Objects 625

22.2 Convex Hulls 630

22.3 Segment Intersection 638

22.4 Finding a Closest Pair of Points 642

22.5 Exercises 646

23 String Algorithms 651

23.1 String Operations 653

23.2 The Boyer-Moore Algorithm 656

23.3 The Knuth-Morris-Pratt Algorithm 660

23.4 Hash-Based Lexicon Matching 664

23.5 Tries 669

23.6 Exercises 680

24 Cryptography 685

24.1 Greatest Common Divisors (GCD) 687

24.2 Modular Arithmetic 691

24.3 Cryptographic Operations 699

24.4 The RSA Cryptosystem 703

24.5 The El Gamal Cryptosystem 706

24.6 Exercises 708

25 The Fast Fourier Transform 711

25.1 Convolution 713

25.2 Primitive Roots of Unity 715

25.3 The Discrete Fourier Transform 717

25.4 The Fast Fourier Transform Algorithm 721

25.5 Exercises 727

26 Linear Programming 731

26.1 Formulating the Problem 734

26.2 The Simplex Method 739

26.3 Duality 746

26.4 Applications of Linear Programming 750

26.5 Exercises 753

A UsefulMathematicalFacts 761

Bibliography 765

Index 774

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.