Claim OwnershipAdvanced Data Structures
Subscribed: 143Played: 1,211
Subscribe
© http://ocw.mit.edu; Creative Commons Attribution-NonCommercial-ShareAlike 3.0; http://ocw.mit.edu/terms; Album art image courtesy of Randall Munroe.
Description
Data structures play a central role in modern computer science. You interact with data structures even more often than with algorithms (think Google, your mail server, and even your network routers). In addition, data structures are essential building blocks in obtaining efficient algorithms. This course covers major results and current directions of research in data structure.
License: Creative Commons BY-NC-SA
License: Creative Commons BY-NC-SA
22 Episodes
Reverse
History of memory models: idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious
Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity
Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), survey
Dynamic graphs: link-cut trees, heavy-light decomposition
Succinct: compact suffix arrays and trees
Succinct: rank, select, tries
Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval
Integer: sorting in linear time for w = O(lg2+ε n), priority queues
Static trees: least common ancestor, range minimum queries, level ancestor
Fusion trees: sketching, parallel comparison, most significant set bit
Integer: models, predecessor problem, van Emde Boas, x-fast and y-fast trees, indirection
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.
Dictionaries: universal, k-wise independent, simple tabulation hashing; chaining, dynamic perfect hashing, linear probing, cuckoo hashing
Memory hierarchy: distribution sweeping via lazy funnelsort; cache-oblivious orthogonal 2D range searching: batched and online
Memory hierarchy: ordered-file maintenance, list labeling, order queries, cache-oblivious priority queues
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.
Dynamic optimality: independent rectangle, Wilber, and Signed Greedy lower bounds; key-independent optimality; O(lg lg n)-competitive Tango trees
Dynamic optimality: binary search trees, analytic bounds, splay trees, geometric view, greedy algorithm
1Fractional 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.
Point location and range searching: persistence, retroactivity, dynamization of augmentation through weight balance, and fractional cascading.
Comments
Download from Google Play
Download from App Store
United States