The Algorithm Design Manual

Preface
Contents
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
	Chapter Notes
	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
	Chapter Notes
	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
	Chapter Notes
	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 (*)
	Chapter Notes
	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
	Chapter Notes
	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
	Chapter Notes
	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
	Chapter Notes
	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
	Chapter Notes
	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
	Chapter Notes
	9.11 Exercises
10 How to Design Algorithms
11 A Catalog of Algorithmic Problems
	Caveats
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
	18.5 Text Compression
	18.6 Cryptography
	18.7 Finite State Machine Minimization
	18.8 Longest Common Substring/Subsequence
	18.9 Shortest Common Superstring
19 Algorithmic Resources
	19.1 Software Systems
		19.1.1 LEDA
		19.1.2 CGAL
		19.1.3 Boost Graph Library
		19.1.4 GOBLIN
		19.1.5 Netlib
		19.1.6 Collected Algorithms of the ACM
		19.1.7 SourceForge and CPAN
		19.1.8 The Stanford GraphBase
		19.1.9 Combinatorica
		19.1.10 Programs from Books
	19.2 Data Sources
	19.3 Online Bibliographic Resources
	19.4 Professional Consulting Services
Bibliography
Index