Advanced Structures: Resources
Use the reading guide for bounded assignments and local-library paths. These sources support specific questions; a bibliography is not a completion gate.
Books
- The Algorithm Design Manual: operation-driven selection, balanced trees and disjoint sets.
- Introduction to Algorithms: balanced-tree invariants, amortized analysis, disjoint-set forests and advanced heaps, subject to edition coverage.
- Competitive Programming: executable union-find, Fenwick and segment-tree patterns. Translate its indexing and problem assumptions before reuse.
Primary technical sources
- Open Data Structures: basic skiplist structure: random heights and expected search analysis. State the independence assumptions rather than turning expectation into a per-request guarantee.
- Open Data Structures: select the treap treatment for random-priority BST analysis; chapter navigation varies by language edition.
- Broder and Mitzenmacher, Network Applications of Bloom Filters: A Survey: approximate sizing and applications. The lab's deterministic hash construction is not a proof of the ideal independent-hash model.
- Fredman, Sedgewick, Sleator and Tarjan, The Pairing Heap: original structure and partial analysis.
- Pettie, Towards a Final Analysis of Pairing Heaps (2005): historical analysis requiring careful variant and operation identification. Neither pairing source is presented as a survey of the latest bounds.
Reproducible module artifacts
Start with contracts, then the five labs. Keep model checks, structural invariants, resource counts and theorem arguments distinct. The downloadable package contains the starter, reference, checker, deterministic report and evidence template.
Use worked examples for guided reasoning, practice solutions after an independent attempt, and assessment for the competency gates. Source disagreements belong in a theorem card with edition, assumptions and a separating example.