## Table of Contents

1. Algorithm Analysis

1.1 Introduction to algorithm analysis

1.2 Analyzing algorithms

1.3 A quick mathematical review

1.4 A case study in algorithm analysis

1.5 Amortization

1.6 Exercises

1.7 Chapter notes

2. Basic Data Structures

2.1 Introduction to basic data structures

2.2 Stacks and queues

2.3 Lists

2.4 Trees

2.5 Exercises

2.6 Chapter notes

3. Binary Search Trees

3.1 Introduction to binary search trees

3.2 Searches and updates

3.3 Range queries

3.4 Index-based searching

3.5 Randomly constructed search trees

3.6 Exercises

3.7 Chapter notes

4. Balanced Binary Search Trees

4.1 Introduction to balanced binary search trees

4.2 Ranks and rotations

4.3 AVL trees

4.4 Red-black trees

4.5 Weak AVL trees

4.6 Splay trees

4.7 Exercises

4.8 Chapter notes

5. Priority Queues and Heaps

5.1 Introduction to priority queue and heaps

5.2 Priority queues

5.3 PQ-sort, selection-sort, and insertion-sort

5.4 Heaps

5.5 Heap-sort

5.6 Extending priority queues

5.7 Exercises

5.8 Chapter notes

6. Hash Tables

6.1 Introduction to hash tables

6.2 Maps

6.3 Hash functions

6.4 Handling collisions and rehashing

6.5 Cuckoo hashing

6.6 Universal hashing

6.7 Exercises

6.8 Chapter notes

7. Union-find Structures

7.1 Introduction to union-find structures

7.2 Union-find and its applications

7.3 A list-based implementation

7.4 A tree-based implementation

7.5 Exercises

7.6 Chapter notes

8. Merge-Sort and Quick-Sort

8.1 Introduction to merge-sort and quick sort

8.2 Merge-sort

8.3 Quick-sort

8.4 A lower bound on comparison-based sorting

8.5 Exercises

8.6 Chapter notes

9. Fast Sorting and Selection

9.1 Introduction to fast sorting and selection

9.2 Bucket-sort and radix-sort

9.3 Selection

9.4 Weighted medians

9.5 Exercises

9.6 Chapter notes

10. The Greedy Method

10.1 Introduction to the greedy method

10.2 The fractional knapsack problem

10.3 Task scheduling

10.4 Text compression and Huffman coding

10.5 Exercises

10.6 Chapter notes

11. Divide-and-Conquer

11.1 Introduction to divide-and-conquer

11.2 Recurrences and the master theorem

11.3 Integer multiplication

11.4 Matrix multiplication

11.5 The maxima-set problem

11.6 Exercises

11.7 Chapter notes

12. Dynamic Programming

12.1 Introduction to dynamic programming

12.2 Manufacturing costs

12.3 The longest common subsequence problem

12.4 The general technique

12.5 Telescope scheduling

12.6 Matrix chain-products

12.7 Game strategies

12.8 The 0-1 knapsack problem

12.9 Exercises

12.10 Chapter notes

13. Graphs and Traversals

13.1 Introduction to graphs and traversals

13.2 Graph terminology and representations

13.3 Depth-first search

13.4 Breadth-first search

13.5 Transitive closure

13.6 Directed acyclic graphs

13.7 Biconnected components

13.8 Exercises

13.9 Chapter notes

14. Shortest Paths

14.1 Introduction to shortest paths

14.2 Single-source shortest paths

14.3 Dijkstra’s algorithm

14.4 The Bellman-Ford algorithm

14.5 Shortest paths in directed acyclic graphs

14.6 All-pairs shortest paths

14.7 Exercises

14.8 Chapter notes

15. Minimum Spanning Trees

15.1 Introduction to minimum spanning trees

15.2 Properties of minimum spanning trees

15.3 Kruskal’s algorithm

15.4 The Prim-JarnÃk algorithm

15.5 BarÅ¯vka’s algorithm

15.6 Exercises

15.7 Chapter notes

16. Network Flow and Matching

16.1 Introduction to network flow and matching

16.2 Flows and cuts

16.3 Maximum flow algorithms

16.4 Maximum bipartite matching

16.5 Baseball elimination

16.6 Minimum-cost flow

16.7 Exercises

16.8 Chapter notes

17. NP-Completeness

17.1 Introduction to NP-completeness

17.2 P and NP

17.3 NP-completeness

17.4 CNF-SAT and 3SAT

17.5 Vertex-cover, clique, and set-cover

17.6 Subset-sum and knapsack

17.7 Hamiltonian-cycle and TSP

17.8 Exercises

17.9 Chapter notes

18. Approximation Algorithms

18.1 Introduction to approximation algorithms

18.2 The metric traveling salesperson problem

18.3 Approximations for covering problems

18.4 Polynomial-time approximation schemes

18.5 Backtracking and branch-and-bound

18.6 Exercises

18.7 Chapter notes

19. Randomized Algorithms

19.1 Introduction to randomized algorithms

19.2 Generating random permutations

19.3 Stable matching and coupon collecting

19.4 Minimum cuts

19.5 Finding prime numbers

19.6 Chernoff bounds

19.7 Skip lists

19.8 Exercises

19.9 Chapter notes

20. B-Trees and External-Memory

20.1 Introduction to B-trees and external memory

20.2 External memory

20.3 (2,4) trees and B-trees

20.4 External-memory sorting

20.5 Online caching algorithms

20.6 Exercises

20.7 Chapter notes

21. Multi-Dimensional Searching

21.1 Introduction to multidimensional searching

21.2 Range trees

21.3 Priority search trees

21.4 Quadtrees and k-d trees

21.5 Exercises

21.6 Chapter notes

22. Computational Geometry

22.1 Introduction to computational geometry

22.2 Operations on geometric objects

22.3 Convex hulls

22.4 Segment intersection

22.5 Finding a closest pair of points

22.6 Exercises

22.7 Chapter notes

23. String Algorithms

23.1 Introduction to string algorithms

23.2 String operations

23.3 The Boyer-Moore algorithm

23.4 The Knuth-Morris-Pratt algorithm

23.5 Hash-based lexicon matching

23.6 Tries

23.7 Exercises

23.8 Chapter notes

24. Cryptography

24.1 Introduction to cryptography

24.2 Greatest common divisors (GCD)

24.3 Modular arithmetic

24.4 Cryptographic operations

24.5 The RSA cryptosystem

24.6 The El Gamal cryptosystem

24.7 Exercises

24.8 Chapter notes

25. The Fast Fourier Transform

25.1 Introduction to the fast Fourier transform

25.2 Convolution

25.3 Primitive roots of unity

25.4 The discrete Fourier transform

25.5 The fast Fourier transform algorithm

25.6 Exercises

25.7 Chapter notes

26. Linear Programming

26.1 Introduction to linear programming

26.2 Formulating the problem

26.3 The simplex method

26.4 Duality

26.5 Applications of linear programming

26.6 Exercises

26.7 Chapter notes

27. Useful Mathematical Facts

27.1 Introduction

27.2 Logarithms and exponents

27.3 Integer functions and relations

27.4 Summations

27.5 Useful mathematical techniques

28. Bibliography

28.1 Bibliography

## The zyBooks version of Algorithm Design and Applications provides a powerful interactive learning experience

**Algorithm Design and Applications **zyVersion contains the complete content of the original plus new interactive animations and learning questions to engage students.

- Over 70 animations to illustrate examples
- Emphasizes both mathematical analysis and practical applications
- Hundreds of interactive learning questionsÂ

**Animation of Dijkstraâ€™s Algorithm**

## What is a zyVersion?

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.

zyBooksâ€™ web-native content helps students visualize concepts toÂ learn faster and more effectivelyÂ than with a traditional textbook. (Check out our research.)

### This zyVersion ofÂ **Algorithm Design and Applications**Â benefits both students and instructors:

- Instructor benefits
- Customize your course by reorganizing existing content or adding your own
- Continuous publication model updates your course with the latest content and technologies
- Robust reporting gives you insight into studentsâ€™ progress, reading and participation
- Animations and other interactive content can be shown in presentation mode and used during a lecture

- Student benefits
- Learning questions and other content serve as an interactive form of reading
- Instant feedback on labs and homework
- Concepts come to life through extensive animations embedded into the interactive content
- Save chapters as PDFs to reference the material at any time

## Authors

**Michael Goodrich**, PhDÂ

Distinguished Professor of Computer Science / University of California, IrvineÂ

**Roberto Tamassia**, PhDÂ

Professor of Computer Science / Brown University

**Michael Goldwasser, **PhDÂ Â

Professor of Computer Science / Saint Louis University

### Senior Contributor

**Evan Olds
**Senior Content Developer, zyBooks