From Ferragina’s algorithm engineering
The algorithms of P. Ferragina’s Pearls of Algorithm Engineering, from
the maximum sub-array sum to the compressed data structures, are in ADS as
well. Each header compares the algorithms of its chapter with the variants
of the later literature (e.g., SA-IS beside the skew algorithm, or the
sampled select of the practical libraries beside Clark’s scheme). The tests
in test/pearls_*.cpp check them against brute force, against the standard
library and against the examples of the notes, with their numbers. A class
simulates the two-level memory of chapters 3 to 6 and counts the reads and
the writes of blocks; hence, the tests can also check the bounds on the
I/Os that those chapters prove.
What |
Headers |
Tests |
|---|---|---|
maximum sub-array sum, with lengths in a range and maximum density (2) |
|
|
random sampling, on disk and on streams, Vitter’s skips (3) |
|
|
list ranking by pointer jumping and independent sets, in memory and on disk (4) |
|
|
two-level memory, binary and multiway mergesort, distribution sort, loser tree, I/O lower bounds (5) |
|
|
sorted set intersection: merge, binary search, mutual partition, doubling, two-level (6) |
|
|
universal hashing, d-left, FKS, minimal ordered perfect hashing, cuckoo hashing, Bloom variants (8) |
|
|
prefix search, front coding, Patricia trie, two-level dictionary (9) |
|
|
suffix arrays (six constructions), LCP, range minimum queries, suffix trees and their applications (10) |
|
|
integer codes: gamma, delta, Rice, Golomb, PForDelta, variable-byte, (s,c)-dense, interpolative, Elias-Fano (11) |
|
|
canonical Huffman, arithmetic coding, PPM (12), LZ77, LZSS, LZ78, LZW (13), Burrows-Wheeler, bzip, FM-index (14) |
|
|
bit vectors with rank and select, succinct trees (Jacobson, LOUDS, balanced parentheses) and graphs (k2-tree, Boldi-Vigna) (15) |
|