Skip to main content

Guided Labs

Implement eight structures in five labs, estimated at 26–38 focused hours. Download the offline lab package. Seven files include starter/reference code, independent checks, fixture reporting, contracts and an evidence template. Python 3.10+ and standard library suffice.

Extract, enter advanced-structures, then run:

python check.py --module reference
python run_labs.py --module reference --output results-reference.json

Implement starter.py independently and repeat with --module starter. The untouched starter fails intentionally. Reports overwrite the named path. Read the bundled README for the complete public and inspection interfaces; those attributes let the checker inspect invariants independently of your own validator.

Lab A: complete ordered map — 6–9 hours​

Implement AVL set/get/delete/rank/select/items with unique integer keys and integer values. Inspect global ordering, identity, exact height, balance and subtree sizes after each mutation. Compare to a dictionary plus sorted keys. Required tests include all four rotations, replacement, root and two-child deletion, and invalid rank/select positions. Red-black and randomized implementations are depth options; their proof/contract comparisons remain part of the lessons.

Lab B: partitions and destructive meld — 6–9 hours​

Implement size/compression DSU and a binomial multiset heap. Use graph traversal as a connectivity oracle and sorted multisets for heap behavior. Verify no-op unions and root sizes; do not force a minimum-ID representative. Check binomial orders, exact subtree counts and ownership across every live heap. Meld empties the donor and rejects self-meld. Test high-degree donors and reusing emptied heaps.

Lab C: amortized operation ledger — 3–4 hours​

Implement the specified doubling array and exact copy/write counters. First nine costs are [1,2,3,1,5,1,1,1,9], total 24, capacity 16. Derive the geometric bound and Phi=2*size-capacity, including initial allocation. Keep actual and amortized costs separate from elapsed time and allocation initialization. Explain a shrink-thrashing counterexample without silently extending the append-only API.

Lab D: range algebra and immutable history — 7–10 hours​

Implement Fenwick point-add sums, lazy add/assign sums and persistent point-set sum versions. All ranges are half-open, including empty ranges. Derive the affine action on sums and new-after-old composition. Test overlapping updates, assignment zero, negative values and partially pushed tags against a plain list. Fork old versions, recheck every historical range and inspect shared siblings. The fixture branch sums from [1,2,3,4] are 10,18,5.

Lab E: approximate membership with exact confirmation — 4–6 hours​

Implement a packed-bit Bloom filter for bytes, with stable reproducible hashes. Test all inserted keys, idempotence, monotone bits and the guaranteed one-bit false-positive example. The reporter uses m=9586,k=7,1000 distinct inserted keys and 10000 disjoint absent queries. Report observed positives with the denominator separately from the ideal-hash sizing approximation. Explain no-false-negative lifecycle requirements and confirm every positive in an exact store.

Acceptance​

All nine checker methods must pass, with source/invariant review supporting the required structure and resource model. Finite tests do not establish asymptotic bounds or independent authorship. Preserve attempts, actual repairs, help and a fresh transfer in the evidence template. Use the contracts, assessment and capstone to complete the path.