History of memory models: idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious

Session 22: History of Memory Models

Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity

Session 21: Dynamic Connectivity Lower Bound

Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey

Session 20: Dynamic Graphs II

Dynamic graphs: link-cut trees, heavy-light decomposition

Session 19: Dynamic Graphs I

Succinct: compact suffix arrays and trees

Session 18: Succinct Structures II

Session 17: Succinct Structures I

Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval

Session 16: Strings

Static trees: least common ancestor, range minimum queries, level ancestor

Session 15: Static Trees

Integer: sorting in linear time for w = O(lg2+ε n), priority queues

Session 14: Sorting in Linear Time

Fusion trees: sketching, parallel comparison, most significant set bit

Session 12: Fusion Trees

Advanced Data Structures

Integer: models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection

Session 11: Integer Models

Integer data structure lower bounds. In particular, we'll prove that the min of van Emde Boas and fusion trees is an optimal (static) predecessor data structure up to a log log factor, assuming polynomial space.

Session 13: Integer Lower Bounds

Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing

Session 10: Dictionaries

Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online

Session 9: Cache-Oblivious Structures II

Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues

Session 8: Cache-Oblivious Structures I

The Best Multi-Part Documentaries, with documentaries on Obama, Federer vs Nadal, the making of Star Wars, Netflix vs Blockbuster and more. Add episodes you're interested into your queue below!

Best Multi-Part Documentaries

The best podcast episodes of anyone with an interesting story. With famous guests like Obama, LeBron James, Drake, Oprah Winfrey, Richard Branson, Michelle Obama, Serena Williams, to anyone who has a unique and interesting story to tell. Add episodes you're interested into your queue below!