Implementation and Transfer Studio
The required work is the eight structures in five guided labs, including one complete AVL map. This page defines bounded extensions rather than a second hidden checklist of every named tree and heap.
For each core class, keep the contract, mutation invariant, stateful checks, resource proof, actual repair and assistance record. Use a fresh operation sequence after repair. A test-only implementation delegating all operations to a sorted list or library does not establish the required representation/cost.
Choose one depth extension after the core
| Extension | Deliverable | New obligation |
|---|---|---|
| Red-black map | Mixed insertion/deletion checker | Named fixup variant, colors and black-height proof |
| Skip list or treap | Seeded and supplied-shape traces | Randomness model, ties and structural invariants |
| Rollback DSU | Undo stack and offline event demo | Every mutation logged; compression policy justified |
| Pairing heap | Two-pass mixed-operation implementation | Handles, ownership and variant-specific bounds |
| Shrinking array | Pop plus hysteresis | A proof for alternating grow/shrink sequences |
| General segment monoid | Noncommutative query example | Operand order and valid update action |
| Persistent range updates | Versioned lazy updates | Immutable tag propagation and sharing bounds |
Fibonacci-heap implementation, succinct navigation and cache-oblivious dynamic indexes require additional source study and review. Their names do not imply that their implementation is part of the core workload. Complete the independent assessment and capstone before claiming transfer.