Ferragina P. The magic of algorithms! Lectures on some algorithmic pearls

Universita di Pisa, 2020. — 259 p.Prologo.
A warm-up!
A cubic-time algorithm.
A quadratic-time algorithm.
A linear-time algorithm.
Another linear-time algorithm.
Few interesting variants.
Random Sampling.
Disk model and known sequence length.
Streaming model and known sequence length.
Streaming model and unknown sequence length.
List Ranking.
The pointer-jumping technique.
Parallel algorithm simulation in a 2-level memory.
A Divide&Conquer approach.
Sorting Atomic Items.
The merge-based sorting paradigm.
Lower bounds.
The distribution-based sorting paradigm.
Sorting with multi-disks.
Set Intersection.
Merge-based approach.
Mutual Partitioning.
Doubling search.
Two-level storage approach.
Sorting Strings.
A lower bound.
RadixSort.
Multi-key Quicksort.
Some observations on the I/O model.
The Dictionary Problem.
Direct-address tables.
Hash Tables.
Universal hashing.
Perfect hashing, minimal, ordered!
A simple perfect hash table.
Cuckoo hashing.
Bloom filters.
Searching Strings by Prefix.
An array of string pointers.
Interpolation search.
Locality-preserving front coding.
Compacted Trie.
Patricia Trie.
Managing Huge Dictionaries.
Searching Strings by Substring.
Notation and terminology.
The Suffix Array.
The Suffix Tree.
Some interesting problems.
Integer Coding.
Elias codes: and.
Rice code.
PForDelta code.
Variable-byte code and (s,c)-dense codes.
Interpolative code.
Elias-Fano code.
Concluding remarks.
Statistical Coding.
Huffman coding.
Arithmetic Coding.
Prediction by Partial Matching.
Dictionary-based compressors.
LZ77.
LZ78.
LZW.
On the optimality of compressors.
The Burrows-Wheeler Transform.
The Burrows-Wheeler Transform.
Two other simple transforms.
The BZIP compressor.
On compression boosting.
On compressed indexing.
Compressed Data Structures.
Compressed representation of arrays.
Succinct representation of trees.
Succinct representation of graphs.