Algorithm Design

Foundations, Analysis, and Internet Examples

by
Michael T. Goodrich and Roberto Tamassia

Table of Contents

Part I. Fundamental Tools

• 1. Algorithm Analysis

  • 1.1 Methodologies for Analyzing Algorithms
  • 1.2 Asymptotic Notation
  • 1.3 A Quick Mathematical Review
  • 1.4 Case Studies in Algorithm Analysis
  • 1.5 Amortization
  • 1.6 Experimentation
  • 1.7 Exercises

  2. Basic Data Structures

  • 2.1 Stacks and Queues
  • 2.2 Vectors, Lists, and Sequences
  • 2.3 Trees
  • 2.4 Priority Queues and Heaps
  • 2.5 Dictionaries and Hash Tables
  • 2.6 Java Example: Heap
  • 2.7 Exercises

  3. Search Trees and Skip Lists

  • 3.1 Ordered Dictionaries and Binary Search Trees
  • 3.2 AVL Trees
  • 3.3 Bounded-Depth Search Trees
  • 3.4 Splay Trees
  • 3.5 Skip Lists
  • 3.6 Java Example: AVL and Red-Black Trees
  • 3.7 Exercises

  4. Sorting, Sets, and Selection

  • 4.1 Merge-Sort
  • 4.2 The Set Abstract Data Type
  • 4.3 Quick-Sort
  • 4.4 A Lower Bound on Comparison-Based Sorting
  • 4.5 Bucket-Sort and Radix-Sort
  • 4.6 Comparison of Sorting Algorithms
  • 4.7 Selection
  • 4.8 Java Example: In-Place Quick-Sort
  • 4.9 Exercises

  5. Fundamental Techniques

  • 5.1 The Greedy Method
  • 5.2 Divide-and-Conquer
  • 5.3 Dynamic Programming
  • 5.4 Exercises

  Part II. Graph Algorithms

  6. Graphs

  • 6.1 The Graph Abstract Data Type
  • 6.2 Data Structures for Graphs
  • 6.3 Graph Traversal
  • 6.4 Directed Graphs
  • 6.5 Java Example: Depth-First Search
  • 6.6 Exercises

  7. Weighted Graphs

  • 7.1 Single-Source Shortest Paths
  • 7.2 All-Pairs Shortest Paths
  • 7.3 Minimum Spanning Trees
  • 7.4 Java Example: Dijkstra's Algorithm
  • 7.5 Exercises

  8. Network Flow and Matching

  • 8.1 Flows and Cuts
  • 8.2 Maximum Flow
  • 8.3 Maximum Bipartite Matching
  • 8.4 Minimum-Cost Flow
  • 8.5 Java Example: Minimum-Cost Flow
  • 8.6 Exercises

  Part III. Internet Algorithmics

  9. Text Processing

  • 9.1 Strings and Pattern Matching Algorithms
  • 9.2 Tries
  • 9.3 Text Compression
  • 9.4 Text Similarity Testing
  • 9.5 Exercises

  10. Number Theory and Cryptography

  • 10.1 Fundamental Algorithms Involving Numbers
  • 10.2 Cryptographic Computations
  • 10.3 Information Security Algorithms and Protocols
  • 10.4 The Fast Fourier Transform
  • 10.5 Java Example: FFT
  • 10.6 Exercises

  11. Network Algorithms

  • 11.1 Complexity Measures and Models
  • 11.2 Fundamental Distributed Algorithms
  • 11.3 Broadcast and Unicast Routing
  • 11.4 Multicast Routing
  • 11.5 Exercises

  Part IV. Additional Topics

  12. Computational Geometry

  • 12.1 Range Trees
  • 12.2 Priority Search Trees
  • 12.3 Quadtrees and k-D Trees
  • 12.4 The Plane Sweep Technique
  • 12.5 Convex Hulls
  • 12.6 Java Example: Convex Hull
  • 12.7 Exercises

  13. NP-Completeness

  • 13.1 P and NP
  • 13.2 NP-Completeness
  • 13.3 Important NP-Complete Problems
  • 13.4 Approximation Algorithms
  • 13.5 Backtracking and Branch-and-Bound
  • 13.6 Exercises

  14. Algorithmic Frameworks

  • 14.1 External-Memory Algorithms
  • 14.2 Parallel Algorithms
  • 14.3 Online Algorithms
  • 14.4 Exercises

  A. Useful Mathematical Facts

  Bibliography

  Index