Table of Contents

   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.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.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.2 Bucket-sort and radix-sort

   9.3 Selection

   9.4 Weighted medians

   9.5 Exercises

   9.6 Chapter notes

   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.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.4 Breadth-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.4 Quadtrees and k-d 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.

Instructors: Interested in evaluating this zyVersion for your class? Sign up for a Free Trial and check out the first chapter of any zyBook or zyVersion today!

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