Session 22: History of Memory Models
Session 22: History of Memory Models
History of memory models: idealized 2-level, red-blue pebble game, external memory, HMM, BT, (U)MH, cache oblivious
28 Jun 2017
•
59mins
Session 21: Dynamic Connectivity Lower Bound
Session 21: Dynamic Connectivity Lower Bound
Dynamic graphs: Ω(lg n) lower bound for dynamic connectivity
28 Jun 2017
•
1hr 22mins
Similar Podcasts
Session 20: Dynamic Graphs II
Session 20: Dynamic Graphs II
Dynamic graphs: Euler tour trees, decremental connectivity in trees in O(1), fully dynamic connectivity in O(lg2 n), sur... Read more
28 Jun 2017
•
1hr 24mins
Session 19: Dynamic Graphs I
Session 19: Dynamic Graphs I
Dynamic graphs: link-cut trees, heavy-light decomposition
28 Jun 2017
•
1hr 14mins
Session 18: Succinct Structures II
Session 18: Succinct Structures II
Succinct: compact suffix arrays and trees
28 Jun 2017
•
1hr 24mins
Session 17: Succinct Structures I
Session 17: Succinct Structures I
Succinct: rank, select, tries
28 Jun 2017
•
1hr 20mins
Session 16: Strings
Session 16: Strings
Strings: suffix tree, suffix array, linear-time construction for large alphabets, suffix tray, document retrieval
28 Jun 2017
•
1hr 24mins
Session 15: Static Trees
Session 15: Static Trees
Static trees: least common ancestor, range minimum queries, level ancestor
28 Jun 2017
•
1hr 23mins
Session 14: Sorting in Linear Time
Session 14: Sorting in Linear Time
Integer: sorting in linear time for w = O(lg2+ε n), priority queues
28 Jun 2017
•
1hr 24mins
Session 12: Fusion Trees
Session 12: Fusion Trees
Fusion trees: sketching, parallel comparison, most significant set bit
28 Jun 2017
•
1hr 24mins