Contents

• Techniques
  • Introduction to Algorithms
    • Correctness and Efficiency
      • Correctness
      • Efficiency
    • Expressing Algorithms
    • Keeping Score
      • The RAM Model of Computation
      • Best, Worst, and Average-Case Complexity
    • The Big Oh Notation
    • Growth Rates
    • Logarithms
    • Modeling the Problem
    • About the War Stories
    • War Story: Psychic Modeling
    • Exercises
  • Data Structures and Sorting
    • Fundamental Data Types
      • Containers
      • Dictionaries
      • Binary Search Trees
      • Priority Queues
    • Specialized Data Structures
    • Sorting
    • Applications of Sorting
    • Approaches to Sorting
      • Data Structures
      • Incremental Insertion
      • Divide and Conquer
      • Randomization
      • Bucketing Techniques
    • War Story: Stripping Triangulations
    • War Story: Mystery of the Pyramids
    • War Story: String 'em Up
    • Exercises
  • Breaking Problems Down
    • Dynamic Programming
      • Fibonacci numbers
      • The Partition Problem
      • Approximate String Matching
      • Longest Increasing Sequence
      • Minimum Weight Triangulation
    • Limitations of Dynamic Programming
    • War Story: Evolution of the Lobster
    • War Story: What's Past is Prolog
    • War Story: Text Compression for Bar Codes
    • Divide and Conquer
      • Fast Exponentiation
      • Binary Search
      • Square and Other Roots
    • Exercises
  • Graph Algorithms
    • The Friendship Graph
    • Data Structures for Graphs
    • War Story: Getting the Graph
    • Traversing a Graph
      • Breadth-First Search
      • Depth-First Search
    • Applications of Graph Traversal
      • Connected Components
      • Tree and Cycle Detection
      • Two-Coloring Graphs
      • Topological Sorting
      • Articulation Vertices
    • Modeling Graph Problems
    • Minimum Spanning Trees
      • Prim's Algorithm
      • Kruskal's Algorithm
    • Shortest Paths
      • Dijkstra's Algorithm
      • All-Pairs Shortest Path
    • War Story: Nothing but Nets
    • War Story: Dialing for Documents
    • Exercises
  • Combinatorial Search and Heuristic Methods
    • Backtracking
      • Constructing All Subsets
      • Constructing All Permutations
      • Constructing All Paths in a Graph
    • Search Pruning
    • Bandwidth Minimization
    • War Story: Covering Chessboards
    • Heuristic Methods
      • Simulated Annealing
        • Traveling Salesman Problem
        • Maximum Cut
        • Independent Set
        • Circuit Board Placement
      • Neural Networks
      • Genetic Algorithms
    • War Story: Annealing Arrays
    • Parallel Algorithms
    • War Story: Going Nowhere Fast
    • Exercises
  • Intractable Problems and Approximations
    • Problems and Reductions
    • Simple Reductions
      • Hamiltonian Cycles
      • Independent Set and Vertex Cover
      • Clique and Independent Set
    • Satisfiability
      • The Theory of NP-Completeness
      • 3-Satisfiability
    • Difficult Reductions
      • Integer Programming
      • Vertex Cover
    • Other NP-Complete Problems
    • The Art of Proving Hardness
    • War Story: Hard Against the Clock
    • Approximation Algorithms
      • Approximating Vertex Cover
      • The Euclidean Traveling Salesman
    • Exercises
  • How to Design Algorithms
• Resources
  • A Catalog of Algorithmic Problems
    • Data Structures
      • Dictionaries
      • Priority Queues
      • Suffix Trees and Arrays
      • Graph Data Structures
      • Set Data Structures
      • Kd-Trees
    • Numerical Problems
      • Solving Linear Equations
      • Bandwidth Reduction
      • Matrix Multiplication
      • Determinants and Permanents
      • Constrained and Unconstrained Optimization
      • Linear Programming
      • Random Number Generation
      • Factoring and Primality Testing
      • Arbitrary-Precision Arithmetic
      • Knapsack Problem
      • Discrete Fourier Transform
    • Combinatorial Problems
      • Sorting
      • Searching
      • Median and Selection
      • Generating Permutations
      • Generating Subsets
      • Generating Partitions
      • Generating Graphs
      • Calendrical Calculations
      • Job Scheduling
      • Satisfiability
    • Graph Problems: Polynomial-Time
      • Connected Components
      • Topological Sorting
      • Minimum Spanning Tree
      • Shortest Path
      • Transitive Closure and Reduction
      • Matching
      • Eulerian Cycle / Chinese Postman
      • Edge and Vertex Connectivity
      • Network Flow
      • Drawing Graphs Nicely
      • Drawing Trees
      • Planarity Detection and Embedding
    • Graph Problems: Hard Problems
      • Clique
      • Independent Set
      • Vertex Cover
      • Traveling Salesman Problem
      • Hamiltonian Cycle
      • Graph Partition
      • Vertex Coloring
      • Edge Coloring
      • Graph Isomorphism
      • Steiner Tree
      • Feedback Edge/Vertex Set
    • Computational Geometry
      • Robust Geometric Primitives
      • Convex Hull
      • Triangulation
      • Voronoi Diagrams
      • Nearest Neighbor Search
      • Range Search
      • Point Location
      • Intersection Detection
      • Bin Packing
      • Medial-Axis Transformation
      • Polygon Partitioning
      • Simplifying Polygons
      • Shape Similarity
      • Motion Planning
      • Maintaining Line Arrangements
      • Minkowski Sum
    • Set and String Problems
      • Set Cover
      • Set Packing
      • String Matching
      • Approximate String Matching
      • Text Compression
      • Cryptography
      • Finite State Machine Minimization
      • Longest Common Substring
      • Shortest Common Superstring
  • Algorithmic Resources
    • Software systems
      • LEDA
      • Netlib
        • Collected Algorithms of the ACM
      • The Stanford GraphBase
      • Combinatorica
      • Algorithm Animations with XTango
      • Programs from Books
        • Discrete Optimization Algorithms in Pascal
        • Handbook of Data Structures and Algorithms
        • Combinatorial Algorithms for Computers and Calculators
        • Algorithms from P to NP
        • Computational Geometry in C
        • Algorithms in C++
    • Data Sources
    • Textbooks
    • On-Line Resources
      • Literature
      • People
      • Software
    • Professional Consulting Services
• References
• Index
• About this document ...