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

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.

See it in action with this animation of Dijkstra’s Algorithm: During this exciting time for computer science, computers have moved beyond their early uses as computational engines to information processors.  Computers can be used to store and retrieve large amounts of data, and they are used in many other application areas.  Thus, algorithms are taught to emphasize not only their mathematical analysis but also their practical applications.

## 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