Skip to main content

Guided Labs

Implement eight operations across five labs, with 25–35 focused hours for derivation, implementation, testing and repair. Download the offline lab package. The seven teaching files include a starter, reference, independent checker, fixture reporter, contracts and evidence template. Python 3.10+ and its standard library are sufficient; no network or package installation is required after download.

Extract the archive, enter dynamic-programming, 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 should fail. Preserve your attempt before consulting the reference. Reports overwrite the named output path. Read the bundled README for precise input, witness, tie and invalid-input contracts before coding.

Lab A: sequences and witnesses — 5–7 hours​

Implement strict lis(values) and unit-cost edit_distance(source,target). Return subsequence indices and alignment pairs, not merely values. For [3,5,6,2,4], length is 3 although final tails need not form a subsequence. For kitten -> sitting, cost is 3; verify both ungapped alignment columns.

Derive tails dominance and the last-column edit recurrence. Test duplicates, empty inputs, ties and Unicode code points. Compare tiny cases with exhaustive subsequence/alignment enumeration. Explain what row compression would discard.

Lab B: item choices and interval compatibility — 5–7 hours​

Implement knapsack(items,capacity) and weighted_intervals(jobs) with original IDs. Positive weights, signed values, at-most capacity and empty selection are explicit. Intervals are half-open, with start strictly before finish. [(2,3),(3,4),(4,5)] at capacity 5 gives value 7, IDs 0,1. Jobs [(0,2,3),(2,4,3),(0,4,7)] give value 7, ID 2.

Show the take/skip partition and compatible-prefix search. Reject repeated IDs and overlaps. Compare tiny inputs to all subsets. Preserve both the ascending 0/1 update counterexample and the descending capacity-parent witness failure.

Lab C: interval and tree decomposition — 6–8 hours​

Implement matrix_chain(dimensions) and tree_independent_set(weights,edges). Dimensions [10,30,5,60] give cost 4500 and tree ((0,1),2). Path weights [4,10,4] give value 10 from vertex 1. Verify tree leaves, dimension multiplication costs and selection adjacency independently.

Validate graph structure; n-1 edges alone are insufficient. Use iterative tree evaluation/reconstruction and test a 2,500-vertex chain. Compare small instances to all parenthesizations or vertex subsets. Explain signed weights and empty choices.

Lab D: subset history — 5–7 hours​

Implement tsp(costs) for a directed matrix with missing arcs and signed integer costs. For [[0,2,9,10],[1,0,6,4],[15,7,0,8],[6,3,12,0]], the optimum is 21 via [0,2,3,1,0]. Verify the closing edge, unique visits and objective.

Compare against rooted permutations on tiny instances. Test no tour, empty matrix and the one-city convention. Count state slots and transitions before larger runs; do not convert "n is small" into an unmeasured feasibility promise.

Lab E: bounded digit counting — 4–6 hours​

Implement count_digit_sum(bound,target), including F(-1,S)=0. Through 25, sum 3 occurs at 3,12,21; range 10..25 has two. Prove unique padded representations and cache lifetime. Check zero, powers of ten, impossible targets and repeated queries against enumeration. Explain why digit occurrence needs a started flag or equivalent canonical-representation handling while digit sum does not.

Acceptance and evidence​

All nine checker methods must pass, and your code/proof review must support the stated complexity and independent implementation. A matching fixture report alone does not suffice. Copy the evidence template, retain attempts and actual repairs, record help, and complete the assessment and capstone. See state and resource contracts before attempting memory optimizations. Different valid tied witnesses are accepted.