Learning CS-166: Design, analysis and implementation of data structures.
Course link: CS 166 Data Structures
Last year 2021 Lecture Topics:
- Week 1: Range Minimum Queries
- Week 2: 2-3-4 Trees, Red/Black Trees, Augmented Trees
- Week 3: Amortized Analysis, Binomial Heaps
- Week 4: Fibonacci Heaps, Cuckoo Hashing
- Week 5: Count-Min Sketches, Count Sketches, HyperLogLog
- Week 6: Orthogonal Range Searching, Planar Point Location
- Week 7: Bloom Filter, Cuckoo Filters, XOR Filters
- Week 8: Better-than-Balanced Trees, Splay Trees
- Week 9: Suffix Trees, Suffix Arrays
- Week 10: Building Suffix Arrays
Updating 2022 Lecture Topics:
- (March 29) Range Minimum Queries Part One (Full Preprocessing, Block Partition, Sparse Table, Hybrid Methods, ...)
- (April 1) Range Minimum Queries Part Two (Cartesian Tree, Fischer-Heun Structure, Method of Four Russians, ...)
- (April 6) Balanced Trees Part One (B-Trees, Red/Black Trees, Augmented Search Trees, ...)
- (April 8) Balanced Trees Part Two (Red/Black Trees, Order Statistic Trees, 1D-Hierarchical Clustering, ...)
- (April 13) Hashing and Sketching Part One (Hash Functions, Approximating Quantities, Frequency Estimation, Count-Min Sketch, ...)
- (April 15) Hashing and Sketching Part Two (Count Sketches, Cardinality Estimation, HyperLogLog)
- (April 19) Cuckoo Hashing (Hash Tables with no collisions, Random Graph Theory)
- (April 21) Amortized Analysis (Amortized Analysis, Potential Functions)
- (April 26) Scapegoat Trees (BST - Scapegoat Tree,
$\alpha$ -imbalanced) - (April 29) Tournament Heaps (Priority Queue, Meldable Priority Queue, Tournament Heaps, Lazy Tournament Heaps)