Algorithm design

The general strategies behind most algorithms: divide and conquer, greedy choice with its exchange arguments, dynamic programming, backtracking with branch and bound, number theory and randomization. Each strategy is shown on several problems, including the cases where it fails.

This part builds on Trees.

1 of 8 topics ready, listed in reading order

Divide and conquerMaximum subarray, Karatsuba multiplication, Strassen's matrix multiplication and the closest pair of points.Planned

Greedy algorithmsActivity selection, the fractional knapsack, exchange arguments and the problems where greed fails.Planned

Huffman codingPrefix codes, building the optimal tree with a priority queue, encoding and decoding, and the proof of optimality.Planned

Dynamic programmingOptimal substructure and overlapping subproblems, memoization against tables, rod cutting, 0/1 knapsack and matrix-chain multiplication.Ready

Dynamic programming on sequencesLongest common subsequence, edit distance and longest increasing subsequence, with the tables filled cell by cell.Planned

Backtracking and branch and boundPermutations and subsets, the n-queens puzzle, subset sum, pruning, and branch and bound for the 0/1 knapsack.Planned

Number-theoretic algorithmsEuclid's algorithm, modular arithmetic and inverses, fast exponentiation and the Chinese remainder theorem, the arithmetic behind hashing, Rabin-Karp and primality tests.Planned

Randomized algorithmsLas Vegas and Monte Carlo algorithms, randomized quicksort and selection, reservoir sampling and primality testing.Planned