Guided Labs
Four offline labs turn the lessons into runnable work. Budget 14–20 focused hours including proofs, debugging, and evidence. Attempt before reading the reference. Download the Python lab package.
Python 3.10+ and its standard library are sufficient. Extract the archive, open
the sorting-structures folder, then run:
python check.py --module reference
python run_labs.py --module reference --output results-reference.json
Implement starter.py, then run the same commands with --module starter.
The untouched starter is expected to fail. The included README defines every
contract, cost model, invalid-input rule, and known limitation. The package also
contains reference implementations, independent checks, and an evidence template.
| Lab | Implementation and acceptance | Required explanation |
|---|---|---|
| A: stable records, 3–4 h | Bottom-up merge sort; tagged duplicate keys and unorderable payloads; no mutation | Sortedness, multiplicity, stable ties, memory |
| B: boundaries and selection, 3–5 h | Equal range and three-way quickselect; exhaustive short arrays and access budget | Shrinking regions, expected versus worst-case selection, copied input |
| C: dictionary sequences, 4–6 h | Integer-key linear probing with deletion, update, growth and cleanup; compare stateful operations to a dictionary | Reachability, tombstones, occupancy, deterministic collision limits |
| D: heap and stream merge, 4–5 h | Bottom-up heapify and mixed operations; lazily merge sorted generators | Height sum, application invariant, retained state, tie policy |
Check the fixture
The report sorts tags into B,D,A,C; finds range (1,4) for 2; returns rank-2
value 4; retains two map keys after delete/update with 8→updated and 16→C;
drains [1,1,3,5]; and merges [1,1,2,4,5]. Two runs should match byte for byte.
These outputs illustrate the contract; public tests exercise more cases.
Falsification and feedback
For A, deliberately take the right record on ties. For B, remove the equal region or break one bound's strictness. For C, stop at a tombstone or insert there before checking for an existing key. For D, choose the left child unconditionally or eagerly consume every stream. Retain a small failing example, explain the violated invariant, repair it, and test a fresh case. Do not leave deliberate bugs enabled.
Finite tests do not prove complexity or compliance with the implementation restriction. Inspect source for forbidden delegation to the algorithm being implemented and derive the cost independently. A slow full sort can pass many selection-output tests while failing the intended complexity objective.
Evidence and remediation
Submit source, commands, test results, deterministic report, proofs, counterexamples, cost models, and assistance disclosure. If a check fails, use the corresponding worked example, then attempt fresh input before resubmission. Measurement guidance and changed assumptions are in Contracts, Representation, and Performance.