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 self improvement podcast episodes. From improving productivity, to finding purpose in your life to what constitutes freedom, this topic is on anything and everything that can help people to improve their lives. Add episodes you're interested into your queue below!

Best Episodes on Self Improvement, Growth & Development

The best podcast episodes of the most interesting stories and things. From skyping someone while they're in space, to tracking down and meeting a telephone scammer in person, to the story of a Galapagos. These episodes will keep you and all your friends entertained and captivated for hours. Learn something new in every episode! Add episodes you're interested into your queue below!