From The Art of Computer Programming
The structures and the algorithms of Knuth’s The Art of Computer
Programming that the book leaves out are in ADS too, from volumes 1, 2, 3,
4A and 4B, with a few relatives from the later literature; they are tested
in test/taocp.cpp against the standard library, against
a slower method that is obviously correct (the definition of the
transform, the enumeration of the subsets, the backtrack of chapter 16)
and against the counts and the bounds of their analysis.
What |
Header |
Test |
|---|---|---|
Fibonacci search and uniform binary search (6.2.1) |
|
|
AVL tree (6.2.3) and B-tree with removal (6.2.4) |
|
|
skip list, treap, splay tree |
|
|
trie and compact trie (Patricia) (6.3) |
|
|
coalesced hashing with a cellar and Brent’s double hashing (6.4) |
|
|
Bloom filter |
|
|
binary and list insertion, address calculation, radix exchange, tournament sort, Ford-Johnson merge insertion (5.2, 5.3.1) |
|
|
replacement selection and polyphase merge (5.4) |
|
|
threaded binary tree (2.3.1) |
|
|
boundary-tag allocator with first, best and next fit, buddy system (2.5) |
|
|
heap of cells with the marking of Deutsch, Schorr and Waite (2.3.5) |
|
|
sparse matrix on orthogonal lists, pivot step (2.2.6) |
|
|
broadword tricks: sideways sum, ruler, Gray code, Gosper, Morton code (7.1.3) |
|
|
tuples, permutations, combinations, partitions, nested parentheses, with the Gray orders (7.2.1) |
|
|
linear congruential generators, chi-square, Kolmogorov-Smirnov, serial and spectral tests, shuffling and sampling (3.2-3.4) |
|
|
fast Fourier transform (4.3.3, 4.6.4) |
|
|
integers of any length: Karatsuba, Toom-3, Toom-4, Toom-3/2 and 4/2 and the NTT, Algorithm D and the recursive division, the conversions by halves, the square root of Zimmermann, the gcd of Lehmer on two digits and the half gcd (4.3, 4.4, 4.5.2) |
|
|
exact rationals (4.5.1) |
|
|
exact cover by dancing links, Algorithm X (7.2.2.1) |
|
|
SAT by DPLL and by conflict-driven clause learning (7.2.2.2) |
|