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
