Guided Labs
Download the offline Python package. Repository path: labs/algorithm-analysis/. Python 3.10+ and its standard library suffice. Extract it and follow README.md; no account or installation is needed. Estimated effort is9–11 hours, not yet learner-calibrated.
python check.py --module reference
python run_labs.py --module reference --output results-reference.json
These commands verify setup. Implement the four functions in starter.py, then rerun with --module starter. Unfinished functions intentionally fail. Passing instructor code is not evidence of learner completion.
| Lab | Work and prerequisite | Acceptance and repair |
|---|---|---|
| A: aggregate and potential cost | After concepts 1–4, implement growth traces | At n=16 doubling total 31,max9; +1 total 136,max16. Derive counts and potential before execution; fix startup or resize boundaries using n=0,1,2,3. |
| B: proof-guided search | After concepts 5–7, implement first-position lower bound | Handle duplicates and empty input; provide invariant, maintenance, exit argument, and variant. Repair using the first divergent interval. |
| C: count versus weighted scheduling | After concepts 8–14, implement both objectives | Fixture optimum count3 and value 10, with feasible original indices. Defend exchange proof and DP recurrence; fix objective errors with a small exhaustive subset table. |
| D: falsification and evidence | After concepts 15–18, run finite oracles and repeat the report | Introduce then repair the wrong weighted greedy and endpoint-strictness variants. Retain minimal counterexamples and explain why tests do not prove universal correctness or Big-O. |
Contracts, cost units, validation rules, and expected outputs are in the package README. The checker exercises short exhaustive searches, finite subset enumeration, duplicate jobs, touching endpoints, invalid triples, and100 seeded scheduling cases. It permits different optimal witnesses and verifies their value and feasibility.
Submit code, checker output, reproducible report, and the evidence template. Include a derivation of sorting/predecessor/reconstruction costs, not just the DP recurrence. Complete the measurement lesson and assessment. A fast program with an invalid proof remains unfinished; a correct proof with a broken implementation also needs repair.