## Table of Contents

1. Algorithm Analysis

1.1 Analyzing Algorithms

1.2 A Quick Mathematical Review

1.3 A Case Study in Algorithm Analysis

1.4 Amortization

1.5 Exercises

2. Basic Data Structures

2.1 Stacks and Queues

2.2 Lists

2.3 Trees

2.4 Exercises

3. Binary Search Trees

3.1 Searches and Updates

3.2 Range Queries

3.3 Index-Based Searching

3.4 Randomly-Constructed Search Trees

3.5 Exercises

4. Balanced Binary Search Trees

4.1 Ranks and Rotations

4.2 AVL Trees

4.3 Red-Black Trees

4.4 Weak AVL Trees

4.5 Splay Trees

4.6 Exercises

5. Priority Queues and Heaps

5.1 Priority Queues

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

5.3 Heaps

5.4 Heap-Sort

5.5 Extending Priority Queues

5.6 Exercises

6. Hash Tables

6.1 Maps

6.2 Hash Functions

6.3 Handling Collisions and Rehashing

6.4 Cuckoo Hashing

6.5 Universal Hashing

6.6 Exercises

7. Union-FindStructures

7.1 Union-Find and its Applications

7.2 A List-Based Implementation

7.3 A Tree-Based Implementation

7.4 Exercises

8. Merge-Sort and Quick-Sort

8.1 Merge-Sort

8.2 Quick-Sort

8.3 A Lower Bound on Comparison-Based Sorting

8.4 Exercises

9. Fast Sorting and Selection

9.1 Bucket Sort and Radix Sort

9.2 Selection

9.3 Weighted Medians

9.4 Exercises

10. The Greedy Method

10.1 The Fractional Knapsack Problem

10.2 Task Scheduling

10.3 Text Compression and Huffman Coding

10.4 Exercises

11. Divide-and-Conquer

11.1 Recurrences and the Master Theorem

11.2 Integer Multiplication

11.3 Matrix Multiplication

11.4 The Maxima-Set Problem

11.5 Exercises

12. Dynamic Programming

12.1 Matrix Chain-Products

12.2 The General Technique

12.3 Telescope Scheduling

12.4 Game Strategies

12.5 The Longest Common Subsequence Problem

12.6 The 0-1 Knapsack Problem

12.7 Exercises

13. Graphs and Traversals

13.1 Graph Terminology and Representations

13.2 Depth-First Search

13.3 Breadth-First Search

13.4 Directed Graphs

13.5 Biconnected Components

13.6 Exercises

14. Shortest Paths

14.1 Single-Source Shortest Paths

14.2 Dijkstra’s Algorithm

14.3 The Bellman-Ford Algorithm

14.4 Shortest Paths in Directed Acyclic Graphs

14.5 All-Pairs Shortest Paths

14.6 Exercises

15. Minimum Spanning Trees

15.1 Properties of Minimum Spanning Trees

15.2 Kruskal’s Algorithm

15.3 The Prim-Jarn´ýk Algorithm

15.4 Bar°uvka’s Algorithm

15.5 Exercises

16. Network Flow and Matching

16.1 Flows and Cuts

16.2 Maximum Flow Algorithms

16.3 Maximum Bipartite Matching

16.4 Baseball Elimination

16.5 Minimum-Cost Flow

16.6 Exercises

17. NP-Completeness

17.1 **P** and **NP**

17.2 **NP**-Completeness

17.3 CNF-SAT and 3SAT 489

17.4 VERTEX-COVER, CLIQUE, and SET-COVER

17.5 SUBSET-SUM and KNAPSACK

17.6 HAMILTONIAN-CYCLE and TSP

17.7 Exercises 502

18. Approximation Algorithms

18.1 The Metric Traveling Salesperson Problem

18.2 Approximations for Covering Problems

18.3 Polynomial-Time Approximation Schemes

18.4 Backtracking and Branch-and-Bound

18.5 Exercises

19. Randomized Algorithms

19.1 Generating Random Permutations

19.2 Stable Marriages and Coupon Collecting

19.3 Minimum Cuts

19.4 Finding Prime Numbers

19.5 Chernoff Bounds

19.6 Skip Lists

19.7 Exercises

20. B-Trees and External-Memory

20.1 External Memory

20.2 (2,4) Trees and B-Trees

20.3 External-Memory Sorting

20.4 Online Caching Algorithms

20.5 Exercises

21. Multi-Dimensional Searching

21.1 Range Trees

21.2 Priority Search Trees

21.3 Quadtrees and k-D Trees

21.4 Exercises

22. Computational Geometry

22.1 Operations on Geometric Objects

22.2 Convex Hulls

22.3 Segment Intersection

22.4 Finding a Closest Pair of Points

22.5 Exercises

23. String Algorithms

23.1 String Operations

23.2 The Boyer-Moore Algorithm

23.3 The Knuth-Morris-Pratt Algorithm

23.4 Hash-Based Lexicon Matching

23.5 Tries

23.6 Exercises

24. Cryptography

24.1 Greatest Common Divisors (GCD)

24.2 Modular Arithmetic

24.3 Cryptographic Operations

24.4 The RSA Cryptosystem

24.5 The El Gamal Cryptosystem

24.6 Exercises

25. The Fast Fourier Transform

25.1 Convolution

25.2 Primitive Roots of Unity

25.3 The Discrete Fourier Transform

25.4 The Fast Fourier Transform Algorithm

25.5 Exercises

26. Linear Programming

26.1 Formulating the Problem

26.2 The Simplex Method

26.3 Duality

26.4 Applications of Linear Programming

26.5 Exercises

A. Useful Mathematical Facts

Bibliography

Index

**zyVersions** are leading print titles converted and adapted to zyBooks’ interactive learning platform, allowing for a quick and easy transition to an engaging digital experience for instructors and students.

## What You’ll Find In This zyVersion

### The Same Text with More Action

Based on *Algorithm Design and Applications*, this zyVersion contains the complete text of the original plus new interactive animations and learning questions to engage the student. This zyVersion embeds hundreds of learning questions and more than 55 dynamic animations to illustrate examples.

## The zyBooks Approach

zyVersions utilize the “Say, Show, Ask” approach.

Say: We use the trusted content of the textbook to explain concepts and teach students subject matter.

Show: Through animations and learning questions students can see concepts come to life.

Ask: Our built-in learning questions and homework with instant feedback encourage interactivity.

## Authors

**Michael T. Goodrich
**University of California, Irvine

**Roberto Tamassia
**Brown University

## Senior Contributors

**Evan Olds
**Senior Content Developer, zyBooks