1.1 Introduction

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.1 Introduction

2.2 Stacks and queues

2.3 Lists

2.4 Trees

2.5 Exercises

2.6 Chapter notes

3.1 Introduction

3.3 Range queries

3.4 Index-based searching

3.5 Randomly constructed search trees

3.6 Exercises

3.7 Chapter notes

4.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

9.3 Selection

9.4 Weighted medians

9.5 Exercises

9.6 Chapter notes

10.1 Introduction

10.2 The fractional knapsack problem

10.4 Text compression and Huffman coding

10.5 Exercises

10.6 Chapter notes

11.1 Introduction

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.1 Introduction

12.2 Matrix chain-products

12.3 The general technique

12.4 Telescope scheduling

12.5 Game strategies

12.6 The longest common subsequence problem

12.7 The 0-1 knapsack problem

12.8 Exercises

12.9 Chapter notes

13.1 Introduction

13.2 Graph terminology and representations

13.3 Depth-first search

13.5 Directed graphs

13.6 Biconnected components

13.7 Exercises

13.8 Chapter notes

14.1 Introduction

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.1 Introduction

15.2 Properties of minimum spanning trees

15.3 Kruskal’s algorithm

15.4 The Prim-Jarnik algorithm

15.5 Baruvka’s algorithm

15.6 Exercises

15.7 Chapter notes

16.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

19.2 Generating random permutations

19.3 Stable marriages 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.1 Introduction

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.1 Introduction

21.2 Range trees

21.3 Priority search trees

21.5 Exercises

21.6 Chapter notes

22.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

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.1 Introduction

27.2 Logarithms and exponents

27.3 Integer functions and relations

27.4 Summations

27.5 Useful mathematical techniques

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 55 animations to illustrate examples
• Emphasizes both mathematical analysis and practical applications
• Hundreds of interactive learning questions

#### Example of Dijkstra’s Algorithm from the zyBook version ## 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 and Design Application benefits both students and instructors:

• Instructor benefits
• 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 T. Goodrich
University of California, Irvine

Roberto Tamassia
Brown University

## Senior Contributors

Evan Olds
Senior Content Developer, zyBooks