Preface
0 Prologue
0.1 Books and algorithms
0.2 Enter Fibonacci
0.3 Big-O notation

Exercises

1 Algorithms with numbers
1.1 Basic arithmetic
1.2 Modular arithmetic
1.3 Primality testing
1.4 Cryptography
1.5 Universal hashing
Exercises
Randomized algorithms: a virtual chapter

2 Divide-and-conquer algorithms
2.1 Multiplication
2.2 Recurrence relations
2.3 Mergesort
2.4 Medians
2.5 Matrix multiplication
2.6 The fast Fourier transform
Exercises

3 Decompositions of graphs
3.1 Why graphs?
3.2 Depth-first search in undirected graphs
3.3 Depth-first search in directed graphs
3.4 Strongly connected components
Exercises

4 Paths in graphs
4.1 Distances
4.2 Breadth-first search
4.3 Lengths on edges
4.4 Dijkstra's algorithm
4.5 Priority queue implementations
4.6 Shortest paths in the presence of negative edges
4.7 Shortest paths in dags
Exercises

5 Greedy algorithms
5.1 Minimum spanning trees
5.2 Huffman encoding
5.3 Horn formulas
5.4 Set cover
Exercises

6 Dynamic programming
6.1 Shortest paths in dags, revisited
6.2 Longest increasing subsequences
6.3 Edit distance
6.4 Knapsack
6.5 Chain matrix multiplication
6.6 Shortest paths
6.7 Independent sets in trees
Exercises

7 Linear programming and reductions
7.1 An introduction to linear programming
7.2 Flows in networks
7.3 Bipartite matching
7.4 Duality
7.5 Zero-sum games
7.6 The simplex algorithm
7.7 Postscript: circuit evaluation
Exercises

8 NP-complete problems
8.1 Search problems
8.2 NP-complete problems
8.3 The reductions
Exercises

9 Coping with NP-completeness
9.1 Intelligent exhaustive search
9.2 Approximation algorithms
9.3 Local search heuristics
Exercises

10 Quantum algorithms
10.1 Qubits, superposition, and measurement
10.2 The plan
10.3 The quantum Fourier transform
10.4 Periodicity
10.5 Quantum circuits
10.6 Factoring as periodicity
10.7 The quantum algorithm for factoring
Exercises

Historical notes and further reading
Index