22 Elementary Graph Algorithms

22.1 Representations of graphs

22.2 Breadth-first search

22.3 Depth-first search

22.4 Topological sort

22.5 Strongly connected components

23 Minimum Spanning Trees

23.1 Growing a minimum spanning tree

23.2 The algorithms of Kruskal and Prim

24 Single-Source Shortest Paths

24.1 The Bellman-Ford algorithm

24.2 Single-source shortest paths in directed acyclic graphs

24.3 Dijkstra's algorithm

24.4 Difference constraints and shortest paths

24.5 Proofs of shortest-paths properties

25 All-Pairs Shortest Paths

25.1 Shortest paths and matrix multiplication

25.2 The Floyd-Warshall algorithm

25.3 Johnson's algorithm for sparse graphs

26 Maximum Flow

26.1 Flow networks

26.2 The Ford-Fulkerson method

26.3 Maximum bipartite matching

26.4 Push-relabel algorithms

26.5 The relabel-to-front algorithm

27 Sorting Networks

27.1 Comparison networks

27.2 The zero-one principle

27.3 A bitonic sorting network

27.4 A merging network

27.5 A sorting network

28 Matrix Operations

28.1 Properties of matrices

28.2 Strassen's algorithm for matrix multiplication

28.3 Solving systems of linear equations

28.4 Inverting matrices

28.5 Symmetric positive-definite matrices and least-squares approximation

29 Linear Programming

29.1 Standard and slack forms

29.2 Formulating problems as linear programs

29.3 The simplex algorithm

29.4 Duality

29.5 The initial basic feasible solution

30 Polynomials and the FFT

30.1 Representation of polynomials

30.2 The DFT and FFT

30.3 Efficient FFT implementations

31 Number-Theoretic Algorithms

31.1 Elementary number-theoretic notions

31.2 Greatest common divisor

31.3 Modular arithmetic

31.4 Solving modular linear equations

31.5 The Chinese remainder theorem

31.6 Powers of an element

31.7 The RSA public-key cryptosystem

31.8 Primality testing

31.9 Integer factorization

32 String Matching

32.1 The naive string-matching algorithm

32.2 The Rabin-Karp algorithm

32.3 String matching with finite automata

32.4 The Knuth-Morris-Pratt algorithm

33 Computational Geometry

33.1 Line-segment properties

33.2 Determining whether any pair of segments intersects

33.3 Finding the convex hull

33.4 Finding the closest pair of points

34 NP-Completeness

34.1 Polynomial time

34.2 Polynomial-time verification

34.3 NP-completeness and reducibility

34.4 NP-completeness proofs

34.5 NP-complete problems

35 Approximation Algorithms

35.1 The vertex-cover problem

35.2 The traveling-salesman problem

35.3 The set-covering problem

35.4 Randomization and linear programming

35.4 The subset-sum problem