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 on romantic relationships. Episodes talk about the 5 love languages, intimacy, and the taboo topics of sexual desires and infidelity. This topic is a deep dive into the science and complexities that face us in our relationships with others. Add episodes you're interested into your queue below!

Best Episodes on Relationships & Love

The best episodes for anyone looking to learn more about topics such as happiness, fulfillment, depression and psychology/mental health in general. With interviews with industry experts, personal stories of individuals, this topic has lessons applicable to everyone. Add episodes you're interested into your queue below!