Skip to main content

Module 05 Advanced Structures Teaching Units

UnitKindSource linksRoute
Accounting Method: Credits Stored on Operationsconcept2Open
Aggregate Method and the Dynamic Arrayconcept2Open
Applications: Kruskal MST, Dynamic Connectivity, Equivalence Classesconcept5Open
AVL Trees and the Height-Balanced Alternativeconcept3Open
Binary Search Trees and the BST Propertyconcept3Open
Binomial Heaps: Structure and Mergeconcept6Open
Bloom Filters: Probabilistic Set Membershipconcept4Open
Exercisesexercise8Open
Fibonacci Heaps: Amortized Bounds That Make Dijkstra Fasterconcept5Open
Pairing Heaps and the Engineering-vs-Theory Tradeoffconcept5Open
Persistent Data Structures and Functional Spinesconcept4Open
Potential Method and Formal Amortized Cost Accountingconcept2Open
Randomized Data Structures: Skip Lists, Treaps, Randomized BSTsconcept4Open
Red-Black Trees: Invariants, Rotations, and O(log n) Guaranteesconcept2Open
Referencereference11Open
Resourcesresource12Open
Segment Trees and Fenwick Trees for Range Queriesconcept3Open
Skip Lists as a Randomized Balanced-BST Replacementconcept4Open
Succinct and Cache-Oblivious Structures (Research-Level Intro)concept4Open
The Union-Find Problem and the Naive Representationconcept3Open
Union by Rank and Path Compression: Near-alpha(n) Amortizedconcept2Open
Why Amortized Analysis: Smoothing Worst-Case Spikesconcept3Open