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

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

Cache-efficient structures. B-trees are good at data transferred in blocks between cache and main memory, main memory and disk, and so on, achieving O(logB N) insert/delete/predecessor/successor for N items and memory block transfers of size B.

Session 7: Memory Hierarchy Models

Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees

Session 6: Dynamic Optimality II

Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm

Session 5: Dynamic Optimality I

Fractional cascading in 3D orthogonal range searching in O(log n) time.  Moving data, e.g., where 2D points move at known velocity and acceleration: kinetic predecessor and kinetic priority queues.

Session 4: Geometric Structures II

Point location and range searching: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.

Session 3: Geometric Structures I

Advanced Data Structures

The best podcast episodes about true crime. For any thrill seeking podcast listeners who just can't get enough of the captivating stories of murderers and criminals. This topic has all the best episodes from many different true crime podcasts.  Add episodes you're interested into your queue below!

Best True Crime Podcasts

The best podcast episodes on non-current politics. Covering topics such as universal basic income, democracy, poverty & justice and more. For anyone interested in learning more about politics that affect that world, not just now, but in the longer term. Add episodes you're interested into your queue below!