Table of Contents
1. Algorithm Analysis
   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. Basic Data Structures
   2.1 Introduction
   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
   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
   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
   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
   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-FindStructures
   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. Merge-Sort and Quick-Sort
   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. Fast Sorting and Selection
   9.1 Introduction
   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
   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
   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
   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. Graphs and Traversals
   13.1 Introduction
   13.2 Graph terminology and representations
   13.3 Depth-first search
   13.4 Breadth-first search
   13.5 Directed graphs
   13.6 Biconnected components
   13.7 Exercises
   13.8 Chapter notes
14. Shortest Paths
   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. Minimum Spanning Trees
   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. Network Flow and Matching
   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. NP-Completeness
   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. Approximation Algorithms
   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. Randomized Algorithms
   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. B-Trees and External-Memory
   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. Multi-Dimensional Searching
   21.1 Introduction
   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
   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
   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
   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
   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
   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
Index
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
- 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 T. Goodrich
University of California, Irvine
Roberto Tamassia
Brown University
Senior Contributors
Evan Olds
Senior Content Developer, zyBooks
