The Algorithm Design Manual Second Edition

Document Outline

• Preface
  • To the Reader
  • To the Instructor
  • Acknowledgments
  • Caveat
• Contents
• Part I Practical Algorithm Design
  • 1 Introduction to Algorithm Design
    • 1.1 Robot Tour Optimization
    • 1.2 Selecting the Right Jobs
    • 1.3 Reasoning about Correctness
      • 1.3.1 Expressing Algorithms
      • 1.3.2 Problems and Properties
      • 1.3.3 Demonstrating Incorrectness
      • 1.3.4 Induction and Recursion
      • 1.3.5 Summations
    • 1.4 Modeling the Problem
      • 1.4.1 Combinatorial Objects
      • 1.4.2 Recursive Objects
    • 1.5 About the War Stories
    • 1.6 War Story: Psychic Modeling
    • 1.7 Exercises
  • 2 Algorithm Analysis
    • 2.1 The RAM Model of Computation
      • 2.1.1 Best, Worst, and Average-Case Complexity
    • 2.2 The Big Oh Notation
    • 2.3 Growth Rates and Dominance Relations
      • 2.3.1 Dominance Relations
    • 2.4 Working with the Big Oh
      • 2.4.1 Adding Functions
      • 2.4.2 Multiplying Functions
    • 2.5 Reasoning About Efficiency
      • 2.5.1 Selection Sort
      • 2.5.2 Insertion Sort
      • 2.5.3 String Pattern Matching
      • 2.5.4 Matrix Multiplication
    • 2.6 Logarithms and Their Applications
      • 2.6.1 Logarithms and Binary Search
      • 2.6.2 Logarithms and Trees
      • 2.6.3 Logarithms and Bits
      • 2.6.4 Logarithms and Multiplication
      • 2.6.5 Fast Exponentiation
      • 2.6.6 Logarithms and Summations
      • 2.6.7 Logarithms and Criminal Justice
    • 2.7 Properties of Logarithms
    • 2.8 War Story: Mystery of the Pyramids
    • 2.9 Advanced Analysis (*)
      • 2.9.1 Esoteric Functions
      • 2.9.2 Limits and Dominance Relations
    • 2.10 Exercises
  • 3 Data Structures
    • 3.1 Contiguous vs. Linked Data Structures
      • 3.1.1 Arrays
      • 3.1.2 Pointers and Linked Structures
      • 3.1.3 Comparison
    • 3.2 Stacks and Queues
    • 3.3 Dictionaries
    • 3.4 Binary Search Trees
      • 3.4.1 Implementing Binary Search Trees
      • 3.4.2 How Good Are Binary Search Trees?
      • 3.4.3 Balanced Search Trees
    • 3.5 Priority Queues
    • 3.6 War Story: Stripping Triangulations
    • 3.7 Hashing and Strings
      • 3.7.1 Collision Resolution
      • 3.7.2 Efficient String Matching via Hashing
      • 3.7.3 Duplicate Detection Via Hashing
    • 3.8 Specialized Data Structures
    • 3.9 War Story: String 'em Up
    • 3.10 Exercises
  • 4 Sorting and Searching
    • 4.1 Applications of Sorting
    • 4.2 Pragmatics of Sorting
    • 4.3 Heapsort: Fast Sorting via Data Structures
      • 4.3.1 Heaps
      • 4.3.2 Constructing Heaps
      • 4.3.3 Extracting the Minimum
      • 4.3.4 Faster Heap Construction (*)
      • 4.3.5 Sorting by Incremental Insertion
    • 4.4 War Story: Give me a Ticket on an Airplane
    • 4.5 Mergesort: Sorting by Divide-and-Conquer
    • 4.6 Quicksort: Sorting by Randomization
      • 4.6.1 Intuition: The Expected Case for Quicksort
      • 4.6.2 Randomized Algorithms
      • 4.6.3 Is Quicksort Really Quick?
    • 4.7 Distribution Sort: Sorting via Bucketing
      • 4.7.1 Lower Bounds for Sorting
    • 4.8 War Story: Skiena for the Defense
    • 4.9 Binary Search and Related Algorithms
      • 4.9.1 Counting Occurrences
      • 4.9.2 One-Sided Binary Search
      • 4.9.3 Square and Other Roots
    • 4.10 Divide-and-Conquer
      • 4.10.1 Recurrence Relations
      • 4.10.2 Divide-and-Conquer Recurrences
      • 4.10.3 Solving Divide-and-Conquer Recurrences (*)
    • 4.11 Exercises
  • 5 Graph Traversal
    • 5.1 Flavors of Graphs
      • 5.1.1 The Friendship Graph
    • 5.2 Data Structures for Graphs
    • 5.3 War Story: I was a Victim of Moore's Law
    • 5.4 War Story: Getting the Graph
    • 5.5 Traversing a Graph
    • 5.6 Breadth-First Search
      • 5.6.1 Exploiting Traversal
      • 5.6.2 Finding Paths
    • 5.7 Applications of Breadth-First Search
      • 5.7.1 Connected Components
      • 5.7.2 Two-Coloring Graphs
    • 5.8 Depth-First Search
    • 5.9 Applications of Depth-First Search
      • 5.9.1 Finding Cycles
      • 5.9.2 Articulation Vertices
    • 5.10 Depth-First Search on Directed Graphs
      • 5.10.1 Topological Sorting
      • 5.10.2 Strongly Connected Components
    • 5.11 Exercises
  • 6 Weighted Graph Algorithms
    • 6.1 Minimum Spanning Trees
      • 6.1.1 Prim’s Algorithm
      • 6.1.2 Kruskal’s Algorithm
      • 6.1.3 The Union-Find Data Structure
      • 6.1.4 Variations on Minimum Spanning Trees
    • 6.2 War Story: Nothing but Nets
    • 6.3 Shortest Paths
      • 6.3.1 Dijkstra’s Algorithm
      • 6.3.2 All-Pairs Shortest Path
      • 6.3.3 Transitive Closure
    • 6.4 War Story: Dialing for Documents
    • 6.5 Network Flows and Bipartite Matching
      • 6.5.1 Bipartite Matching
      • 6.5.2 Computing Network Flows
    • 6.6 Design Graphs, Not Algorithms
    • 6.7 Exercises
  • 7 Combinatorial Search and Heuristic Methods
    • 7.1 Backtracking
      • 7.1.1 Constructing All Subsets
      • 7.1.2 Constructing All Permutations
      • 7.1.3 Constructing All Paths in a Graph
    • 7.2 Search Pruning
    • 7.3 Sudoku
    • 7.4 War Story: Covering Chessboards
    • 7.5 Heuristic Search Methods
      • 7.5.1 Random Sampling
      • 7.5.2 Local Search
      • 7.5.3 Simulated Annealing
      • 7.5.4 Applications of Simulated Annealing
    • 7.6 War Story: Only it is Not a Radio
    • 7.7 War Story: Annealing Arrays
    • 7.8 Other Heuristic Search Methods
    • 7.9 Parallel Algorithms
    • 7.10 War Story: Going Nowhere Fast
    • 7.11 Exercises
  • 8 Dynamic Programming
    • 8.1 Caching vs. Computation
      • 8.1.1 Fibonacci Numbers by Recursion
      • 8.1.2 Fibonacci Numbers by Caching
      • 8.1.3 Fibonacci Numbers by Dynamic Programming
      • 8.1.4 Binomial Coefficients
    • 8.2 Approximate String Matching
      • 8.2.1 Edit Distance by Recursion
      • 8.2.2 Edit Distance by Dynamic Programming
      • 8.2.3 Reconstructing the Path
      • 8.2.4 Varieties of Edit Distance
    • 8.3 Longest Increasing Sequence
    • 8.4 War Story: Evolution of the Lobster
    • 8.5 The Partition Problem
    • 8.6 Parsing Context-Free Grammars
      • 8.6.1 Minimum Weight Triangulation
    • 8.7 Limitations of Dynamic Programming: TSP
      • 8.7.1 When are Dynamic Programming Algorithms Correct?
      • 8.7.2 When are Dynamic Programming Algorithms Efficient?
    • 8.8 War Story: What's Past is Prolog
    • 8.9 War Story: Text Compression for Bar Codes
    • 8.10 Exercises
  • 9 Intractable Problems and Approximation Algorithms
    • 9.1 Problems and Reductions
      • 9.1.1 The Key Idea
      • 9.1.2 Decision Problems
    • 9.2 Reductions for Algorithms
      • 9.2.1 Closest Pair
      • 9.2.2 Longest Increasing Subsequence
      • 9.2.3 Least Common Multiple
      • 9.2.4 Convex Hull (*)
    • 9.3 Elementary Hardness Reductions
      • 9.3.1 Hamiltonian Cycle
      • 9.3.2 Independent Set and Vertex Cover
      • 9.3.3 Clique
    • 9.4 Satisfiability
      • 9.4.1 3-Satisfiability
    • 9.5 Creative Reductions
      • 9.5.1 Integer Programming
      • 9.5.2 Vertex Cover
    • 9.6 The Art of Proving Hardness
    • 9.7 War Story: Hard Against the Clock
    • 9.8 War Story: And Then I Failed
    • 9.9 P vs. NP
      • 9.9.1 Verification vs. Discovery
      • 9.9.2 The Classes P and NP
      • 9.9.3 Why is Satisfiability the Mother of All Hard Problems?
      • 9.9.4 NP-hard vs. NP-complete?
    • 9.10 Dealing with NP-complete Problems
      • 9.10.1 Approximating Vertex Cover
      • 9.10.2 The Euclidean Traveling Salesman
      • 9.10.3 Maximum Acyclic Subgraph
      • 9.10.4 Set Cover
    • 9.11 Exercises
  • 10 How to Design Algorithms
• Part II The Hitchhiker's Guide to Algorithms
  • 11 A Catalog of Algorithmic Problems
  • 12 Data Structures
    • 12.1 Dictionaries
    • 12.2 Priority Queues
    • 12.3 Suffix Trees and Arrays
    • 12.4 Graph Data Structures
    • 12.5 Set Data Structures
    • 12.6 Kd-Trees
  • 13 Numerical Problems
    • 13.1 Solving Linear Equations
    • 13.2 Bandwidth Reduction 
    • 13.3 Matrix Multiplication
    • 13.4 Determinants and Permanents
    • 13.5 Constrained and Unconstrained Optimization
    • 13.6 Linear Programming
    • 13.7 Random Number Generation
    • 13.8 Factoring and Primality Testing
    • 13.9 Arbitrary-Precision Arithmetic
    • 13.10 Knapsack Problem
    • 13.11 Discrete Fourier Transform
  • 14 Combinatorial Problems
    • 14.1 Sorting
    • 14.2 Searching
    • 14.3 Median and Selection
    • 14.4 Generating Permutations
    • 14.5 Generating Subsets
    • 14.6 Generating Partitions
    • 14.7 Generating Graphs
    • 14.8 Calendrical Calculations
    • 14.9 Job Scheduling
    • 14.10 Satisfiability
  • 15 Graph Problems: Polynomial-Time
    • 15.1 Connected Components
    • 15.2 Topological Sorting
    • 15.3 Minimum Spanning Tree
    • 15.4 Shortest Path
    • 15.5 Transitive Closure and Reduction
    • 15.6 Matching
    • 15.7 Eulerian Cycle/Chinese Postman
    • 15.8 Edge and Vertex Connectivity
    • 15.9 Network Flow
    • 15.10 Drawing Graphs Nicely
    • 15.11 Drawing Trees
    • 15.12 Planarity Detection and Embedding
  • 16 Graph Problems: Hard Problems
    • 16.1 Clique
    • 16.2 Independent Set
    • 16.3 Vertex Cover
    • 16.4 Traveling Salesman Problem
    • 16.5 Hamiltonian Cycle
    • 16.6 Graph Partition
    • 16.7 Vertex Coloring
    • 16.8 Edge Coloring
    • 16.9 Graph Isomorphism
    • 16.10 Steiner Tree
    • 16.11 Feedback Edge/Vertex Set
  • 17 Computational Geometry
    • 17.1 Robust Geometric Primitives
    • 17.2 Convex Hull 
    • 17.3 Triangulation
    • 17.4 Voronoi Diagrams
    • 17.5 Nearest Neighbor Search
    • 17.6 Range Search
    • 17.7 Point Location
    • 17.8 Intersection Detection
    • 17.9 Bin Packing
    • 17.10 Medial-Axis Transform
    • 17.11 Polygon Partitioning
    • 17.12 Simplifying Polygons
    • 17.13 Shape Similarity
    • 17.14 Motion Planning
    • 17.15 Maintaining Line Arrangements
    • 17.16 Minkowski Sum
  • 18 Set and String Problems
    • 18.1 Set Cover
    • 18.2 Set Packing
    • 18.3 String Matching
    • 18.4 Approximate String Matching
    •