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