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
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-_rst search in undirected graphs
3.3 Depth-_rst search in directed graphs
3.4 Strongly connected components
Exercises
3
4 Algorithms
4 Paths in graphs
4.1 Distances
4.2 Breadth-_rst 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 311
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
