Preface
To the Reader
To the Instructor
Acknowledgments
Caveat
Contents
Part I Practical Algorithm Design
Chapter 1 Introduction to Algorithm Design
1.1 Robot Tour Optimization
1.2 Selecting the Right Jobs
1.3 Reasoning about Correctness
1.3.1 Problems and Properties
1.3.2 Expressing Algorithms
1.3.3 Demonstrating Incorrectness
1.4 Induction and Recursion
1.5 Modeling the Problem
1.5.1 Combinatorial Objects
1.5.2 Recursive Objects
1.6 Proof by Contradiction
1.7 About the War Stories
1.8 War Story: Psychic Modeling
1.9 Estimation
1.10 Exercises
Chapter 2 Algorithm Analysis
2.1 The RAM Model of Computation
2.1.1 Best-Case, Worst-Case, 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 Eciency
2.5.1 Selection Sort
2.5.2 Insertion Sort
2.5.3 String Pattern Matching
2.5.4 Matrix Multiplication
2.6 Summations
2.7 Logarithms and Their Applications
2.7.1 Logarithms and Binary Search
2.7.2 Logarithms and Trees
2.7.3 Logarithms and Bits
2.7.4 Logarithms and Multiplication
2.7.5 Fast Exponentiation
2.7.6 Logarithms and Summations
2.7.7 Logarithms and Criminal Justice
2.8 Properties of Logarithms
2.9 War Story: Mystery of the Pyramids
2.10 Advanced Analysis ()
2.10.1 Esoteric Functions
2.10.2 Limits and Dominance Relations
2.11 Exercises
Chapter 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 Containers: 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
3.7.1 Collision Resolution
3.7.2 Duplicate Detection via Hashing
3.7.3 Other Hashing Tricks
3.7.4 Canonicalization
3.7.5 Compaction
3.8 Specialized Data Structures
3.9 War Story: String 'em Up
3.10 Exercises
Chapter 4 Sorting
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 Exercises
Chapter 5 Divide and Conquer
5.1 Binary Search and Related Algorithms
5.1.1 Counting Occurrences
5.1.2 One-Sided Binary Search
5.1.3 Square and Other Roots
5.2 War Story: Finding the Bug in the Bug
5.3 Recurrence Relations
5.3.1 Divide-and-Conquer Recurrences
5.4 Solving Divide-and-Conquer Recurrences
5.5 Fast Multiplication
5.6 Largest Subrange and Closest Pair
5.7 Parallel Algorithms
5.7.1 Data Parallelism
5.7.2 Pitfalls of Parallelism
5.8 War Story: Going Nowhere Fast
5.9 Convolution ()
5.9.1 Applications of Convolution
5.9.2 Fast Polynomial Multiplication ()
5.10 Exercises
Chapter 6 Hashing and Randomized Algorithms
6.1 Probability Review
6.1.1 Probability
6.1.2 Compound Events and Independence
6.1.3 Conditional Probability
6.1.4 Probability Distributions
6.1.5 Mean and Variance
6.1.6 Tossing Coins
6.2 Understanding Balls and Bins
6.2.1 The Coupon Collector's Problem
6.3 Why is Hashing a Randomized Algorithm?
6.4 Bloom Filters
6.5 The Birthday Paradox and Perfect Hashing
6.6 Minwise Hashing
6.7 Efficient String Matching
6.8 Primality Testing
6.9 War Story: Giving Knuth the Middle Initial
6.10 Where do Random Numbers Come From?
6.11 Exercises
Chapter 7 Graph Traversal
7.1 Flavors of Graphs
7.1.1 The Friendship Graph
7.2 Data Structures for Graphs
7.3 War Story: I was a Victim of Moore's Law
7.4 War Story: Getting the Graph
7.5 Traversing a Graph
7.6 Breadth-First Search
7.6.1 Exploiting Traversal
7.6.2 Finding Paths
7.7 Applications of Breadth-First Search
7.7.1 Connected Components
7.7.2 Two-Coloring Graphs
7.8 Depth-First Search
7.9 Applications of Depth-First Search
7.9.1 Finding Cycles
7.9.2 Articulation Vertices
7.10 Depth-First Search on Directed Graphs
7.10.1 Topological Sorting
7.10.2 Strongly Connected Components
7.11 Exercises
Chapter 8 Weighted Graph Algorithms
8.1 Minimum Spanning Trees
8.1.1 Prim's Algorithm
8.1.2 Kruskal's Algorithm
8.1.3 The UnionβFind Data Structure
8.1.4 Variations on Minimum Spanning Trees
8.2 War Story: Nothing but Nets
8.3 Shortest Paths
8.3.1 Dijkstra's Algorithm
8.3.2 All-Pairs Shortest Path
8.3.3 Transitive Closure
8.4 War Story: Dialing for Documents
8.5 Network Flows and Bipartite Matching
8.5.1 Bipartite Matching
8.5.2 Computing Network Flows
8.6 Randomized Min-Cut
8.7 Design Graphs, Not Algorithms
8.8 Exercises
Chapter 9 Combinatorial Search
9.1 Backtracking
9.2 Examples of Backtracking
9.2.1 Constructing All Subsets
9.2.2 Constructing All Permutations
9.2.3 Constructing All Paths in a Graph
9.3 Search Pruning
9.4 Sudoku
9.5 War Story: Covering Chessboards
9.6 Best-First Search
9.7 The A Heuristic
9.8 Exercises
Chapter 10 Dynamic Programming
10.1 Caching vs. Computation
10.1.1 Fibonacci Numbers by Recursion
10.1.2 Fibonacci Numbers by Caching
10.1.3 Fibonacci Numbers by Dynamic Programming
10.1.4 Binomial Coefficients
10.2 Approximate String Matching
10.2.1 Edit Distance by Recursion
10.2.2 Edit Distance by Dynamic Programming
10.2.3 Reconstructing the Path
10.2.4 Varieties of Edit Distance
10.3 Longest Increasing Subsequence
10.4 War Story: Text Compression for Bar Codes
10.5 Unordered Partition or Subset Sum
10.6 War Story: The Balance of Power
10.7 The Ordered Partition Problem
10.8 Parsing Context-Free Grammars
10.9 Limitations of Dynamic Programming: TSP
10.9.1 When is Dynamic Programming Correct?
10.9.2 When is Dynamic Programming Efficient?
10.10 War Story: What's Past is Prolog
10.11 Exercises
Chapter 11 NP-Completeness
11.1 Problems and Reductions
11.1.1 The Key Idea
11.1.2 Decision Problems
11.2 Reductions for Algorithms
11.2.1 Closest Pair
11.2.2 Longest Increasing Subsequence
11.2.3 Least Common Multiple
11.2.4 Convex Hull (*)
11.3 Elementary Hardness Reductions
11.3.1 Hamiltonian Cycle
11.3.2 Independent Set and Vertex Cover
11.3.3 Clique
11.4 Satisfiability
11.4.1 3-Satisfiability
11.5 Creative Reductions from SAT
11.5.1 Vertex Cover
11.5.2 Integer Programming
11.6 The Art of Proving Hardness
11.7 War Story: Hard Against the Clock
11.8 War Story: And Then I Failed
11.9 P vs. NP
11.9.1 Verification vs. Discovery
11.9.2 The Classes P and NP
11.9.3 Why Satisfiability is Hard
11.9.4 NP-hard vs. NP-complete?
11.10 Exercises
Chapter 12 Dealing with Hard Problems
12.1 Approximation Algorithms
12.2 Approximating Vertex Cover
12.2.1 A Randomized Vertex Cover Heuristic
12.3 Euclidean TSP
12.3.1 The Christofides Heuristic
12.4 When Average is Good Enough
12.4.1 Maximum k-SAT
12.4.2 Maximum Acyclic Subgraph
12.5 Set Cover
12.6 Heuristic Search Methods
12.6.1 Random Sampling
12.6.2 Local Search
12.6.3 Simulated Annealing
12.6.4 Applications of Simulated Annealing
12.7 War Story: Only it is Not a Radio
12.8 War Story: Annealing Arrays
12.9 Genetic Algorithms and Other Heuristics
12.10 Quantum Computing
12.10.1 Properties of "Quantum" Computers
12.10.2 Grover's Algorithm for Database Search
12.10.3 The Faster "Fourier Transform"
12.10.4 Shor's Algorithm for Integer Factorization
12.10.5 Prospects for Quantum Computing
12.11 Exercises
Chapter 13 How to Design Algorithms
13.1 Preparing for Tech Company Interviews
Part II The Hitchhiker's Guide to Algorithms
Chapter 14 A Catalog of Algorithmic Problems
Chapter 15 Data Structures
15.1 Dictionaries
15.2 Priority Queues
15.3 Suffix Trees and Arrays
15.4 Graph Data Structures
15.5 Set Data Structures
15.6 Kd-Trees
Chapter 16 Numerical Problems
16.1 Solving Linear Equations
16.2 Bandwidth Reduction
16.3 Matrix Multiplication
16.4 Determinants and Permanents
16.5 Constrained/Unconstrained Optimization
16.6 Linear Programming
16.7 Random Number Generation
16.8 Factoring and Primality Testing
16.9 Arbitrary-Precision Arithmetic
16.10 Knapsack Problem
16.11 Discrete Fourier Transform
Chapter 17 Combinatorial Problems
17.1 Sorting
17.2 Searching
17.3 Median and Selection
17.4 Generating Permutations
17.5 Generating Subsets
17.6 Generating Partitions
17.7 Generating Graphs
17.8 Calendrical Calculations
17.9 Job Scheduling
17.10 Satisfiability
Chapter 18 Graph Problems: Polynomial Time
18.1 Connected Components
18.2 Topological Sorting
18.3 Minimum Spanning Tree
18.4 Shortest Path
18.5 Transitive Closure and Reduction
18.6 Matching
18.7 Eulerian Cycle/Chinese Postman
18.8 Edge and Vertex Connectivity
18.9 Network Flow
18.10 Drawing Graphs Nicely
18.11 Drawing Trees
18.12 Planarity Detection and Embedding
Chapter 19 Graph Problems: NP-Hard
19.1 Clique
19.2 Independent Set
19.3 Vertex Cover
19.4 Traveling Salesman Problem
19.5 Hamiltonian Cycle
19.6 Graph Partition
19.7 Vertex Coloring
19.8 Edge Coloring
19.9 Graph Isomorphism
19.10 Steiner Tree
19.11 Feedback Edge/Vertex Set
Chapter 20 Computational Geometry
20.1 Robust Geometric Primitives
20.2 Convex Hull
20.3 Triangulation
20.4 Voronoi Diagrams
20.5 Nearest-Neighbor Search
20.6 Range Search
20.7 Point Location
20.8 Intersection Detection
20.9 Bin Packing
20.10 Medial-Axis Transform
20.11 Polygon Partitioning
20.12 Simplifying Polygons
20.13 Shape Similarity
20.14 Motion Planning
20.15 Maintaining Line Arrangements
20.16 Minkowski Sum
Chapter 21 Set and String Problems
21.1 Set Cover
21.2 Set Packing
21.3 String Matching
21.4 Approximate String Matching
21.5 Text Compression
21.6 Cryptography
21.7 Finite State Machine Minimization
21.8 Longest Common Substring/Subsequence
21.9 Shortest Common Superstring
Chapter 22 Algorithmic Resources
22.1 Algorithm Libraries
22.1.1 LEDA
22.1.2 CGAL
22.1.3 Boost Graph Library
22.1.4 Netlib
22.1.5 Collected Algorithms of the ACM
22.1.6 GitHub and SourceForge
22.1.7 The Stanford GraphBase
22.1.8 Combinatorica
22.1.9 Programs from Books
22.2 Data Sources
22.3 Online Bibliographic Resources
22.4 Professional Consulting Services
Chapter 23 Bibliography
Index