Advanced Data Structures & Amortized Analysis

Build structures whose correctness survives long operation sequences, and explain the exact guarantee each offers. This module connects balanced maps, connectivity, meldable queues, amortization, range queries, persistence and probabilistic membership to ownership and resource contracts. Completion depends on evidence, not a speed challenge or a claim to an elite percentile.

Entry and outcomes

Complete the prerequisite diagnostic. You should already reason about recursion, induction, asymptotic costs, basic maps/heaps, graphs and probability. Use its repair routes for gaps. Then read the operation and resource contracts.

By completion, maintain ordering/balance/metadata through mutation; distinguish worst-case, amortized and expected bounds; model destructive ownership; compose range updates in order; preserve branching versions; and use approximate membership only with a correct exact-store lifecycle.

Learning route and workload

Plan 95–135 hours across lessons/reading (33–45), labs (26–38), practice (20–28), assessment/remediation (8–12) and capstone (8–12). These are author estimates pending pilots, excluding depth options and full-book reading.

1. Complete lessons 1–7, using earlier graph work to separate connectivity from paths.
2. Study amortization lessons 11–14, then heaps 8–10; numerical proofs support the heap analysis.
3. Finish randomization, range queries, persistence and representation in lessons 15–19.
4. Interleave worked examples, five guided labs and independent practice. Attempt before consulting the separate keys.
5. Take the independent assessment, satisfy every competency gate, and complete the capstone.

Core implementation: AVL map, DSU, binomial heap, doubling array, Fenwick tree, lazy sum tree, persistent sum tree and Bloom filter. Full implementations of the other structures are explicit depth options; their invariants and guarantee comparisons remain core conceptual work.

Concept lessons

1. Binary Search Trees and the BST Property
2. Red-Black Trees: Invariants, Rotations, and O(log n) Guarantees
3. AVL Trees and the Height-Balanced Alternative
4. Skip Lists as a Randomized Balanced-BST Replacement
5. The Union-Find Problem and the Naive Representation
6. Union by Rank and Path Compression: Near-alpha(n) Amortized
7. Applications: Kruskal MST, Dynamic Connectivity, Equivalence Classes
8. Binomial Heaps: Structure and Merge
9. Fibonacci Heaps: Amortized Bounds That Make Dijkstra Faster
10. Pairing Heaps and the Engineering-vs-Theory Tradeoff
11. Why Amortized Analysis: Smoothing Worst-Case Spikes
12. Aggregate Method and the Dynamic Array
13. Accounting Method: Credits Stored on Operations
14. Potential Method and Formal Amortized Cost Accounting
15. Randomized Data Structures: Skip Lists, Treaps, Randomized BSTs
16. Bloom Filters: Probabilistic Set Membership
17. Segment Trees and Fenwick Trees for Range Queries
18. Persistent Data Structures and Functional Spines
19. Succinct and Cache-Oblivious Structures (Research-Level Intro)

Reading, repair and review

Use the reading guide for bounded assignments drawn from Books, reading and Resources. Use selective reading to resolve a specific question; the full-book path has its own separate schedule. Consult resources and the reference index for specific questions. Repair failures with the mistake clinic, then try case studies with changed assumptions. The instructor guide records scope, scoring and pending human validation.