Advanced Data Structures: Reading Guide
Read to answer a concrete invariant, proof or design question. The core reading fits within the 33–45 hours allocated to lessons, prerequisites and contracts; the optional shelf adds time. Start with the lessons and attempt an example before opening a second explanation.
Core topic map
| Stage | Reading assignment | Stop with this evidence |
|---|---|---|
| Ordered maps | Skiena, balanced search trees; CLRS, rotations and red-black trees | Subtree ordering proof, rotation metadata trace, AVL deletion repair; distinguish classic red-black from left-leaning variants |
| Amortization | CLRS, aggregate/accounting/potential methods and dynamic tables | First nine append costs, arbitrary-prefix bound, initial-potential term, shrink-thrashing counterexample |
| Disjoint sets | Skiena, union-find; CLRS, disjoint-set forests | Smaller-list doubling argument, size versus historical rank, initialization cost and the stated inverse-Ackermann theorem |
| Meldable heaps | CLRS, binomial/Fibonacci heaps where present in your edition | Binary-carry ownership trace and root/mark potential; say which operations and variants each bound covers |
| Range queries | Competitive Programming, union-find, segment trees and Fenwick trees | Half-open translation, independent array oracle, assignment/addition composition derived in both orders |
| Randomization and representation | The primary-source selections in resources, chosen by the question below | A probability model, lifecycle contract or representation lower bound with payload costs separated |
Book editions differ: these are topic assignments, not verified universal chapter numbers. In particular, do not assume binomial heaps appear as a standalone chapter in every CLRS edition. Use the self-contained lesson if your edition omits a topic. Do not copy a one-based inclusive interface without translating it.
Using this repository's library
The following paths are relative to the parent workspace containing Degree-Plan. They are local reading aids, not public website download URLs.
Books/The Algorithm Design Manual/contents/README.md: inspect the index entries for chunk 033 (balanced search trees) and 078 (union-find).Books/Competitive Programming/contents/README.md: chunks 029 (union-find), 030 (segment trees), and 031–033 (Fenwick material). Chunk boundaries can carry text from the preceding section; follow the actual headings.reading/Algorithms/CLRS.pdf: locate the topic headings above in the local edition.Resources/software-development-main/books/data structures and algorithms/: optional books listed below; filenames identify local copies, not edition guarantees.
For this revision, the two chunk indexes and selected union-find/Fenwick excerpts were inspected. The entire PDFs and all chunks have not been audited. Report OCR errors against the original text; do not treat extraction artifacts as notation.
Optional shelf: one question per source
| Source | When it earns its time | Required output |
|---|---|---|
| Open Data Structures, skiplist and treap sections | Expected search bounds or random-priority assumptions remain unclear | Separate a deterministic invariant from an expectation and a tail event |
| Broder and Mitzenmacher, Bloom-filter survey | You need to justify sizing and understand ideal-hash assumptions | Derive the approximate rate, rounded parameters and overload behavior; qualify the model |
| Original pairing-heap paper and Pettie's 2005 analysis | You want research-level exposure to variant-sensitive amortized claims | A dated theorem card: exact variant, operations, model, bound and limitations |
| Handbook of Data Structures and Applications, edited by Mehta and Sahni | A specific specialization needs broader structures | One comparison tied to a real operation sequence; check the chapter's assumptions |
| Advanced Algorithms and Data Structures, Marcello La Rocca | You want another engineering-oriented treatment | Reproduce one relevant example and compare its contract with this module |
| Algorithms, Sedgewick and Wayne | You choose the left-leaning red-black depth option | Identify representation and deletion rules before comparing with classic red-black trees |
The last three books are local candidates, not fully reviewed chapter assignments. Avoid turning the core into six simultaneous cover-to-cover readings. The full-book path retains its separate reading schedule. Finish core evidence first; optional implementations and papers extend the workload.