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
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
Succint representation of trees
Succint representation of graphs