Case Studies

These synthetic cases extend the assessed path. They are original teaching scenarios, not claims about documented production incidents.

1. A scheduler silently changes its objective

An earliest-finish scheduler handles (0,1,1),(1,2,1),(0,2,5). It returns two short jobs, correctly maximizing count. Product requirements change to maximum value, but implementation stays the same; the correct result is now the single value 5 job.

Artifact: write the old/new contracts, a counterexample, and a weighted-DP replacement. Preserve original indices, validate compatibility, and review the proof against the new objective. Reusing correct code under an invalid contract is still a system bug.

2. A latency promise inferred from throughput

A buffer doubles from capacity 16 to32 on append17. Under the copy/write model that append costs17 while total cost for 17 appends is48. A team advertises an amortized cost below3 as if no individual call can cost more than 3.

Artifact: show total, amortized, and maximum cost, then identify allocation and element-copy costs omitted by the model. Evaluate fixed capacity, incremental copying, or a different representation against the actual deadline and constraints; do not claim a universal best choice without measuring the relevant implementation.

3. A correct optimum with an impossible witness

A weighted-DP table returns value 10 for the lab fixture, but a reconstruction bug returns indices 0,2,3. That list overlaps and its weights sum12. Checking only the table's final value would miss the broken output contract.

Artifact: validate indices, duplicates, compatibility, and sum of selected weights independently of the recurrence. Retain a recovery trace and explain how predecessor pointers avoid copying whole schedules into every state.

4. A benchmark compares different work

One program scans a list for each query; another builds a hash table outside the timed region and reports only lookup time. For a one-shot query workload, construction is part of the task. For a reused index, reporting build and lookup separately can be appropriate.

Artifact: define two explicit workloads, include equivalent output and setup, and design repeated measurements. Report dispersion and environment; do not fabricate a universal query-count crossover. Use the measurement lesson for the evidence memo.

5. Pruning erases a valid signed solution

A subset-sum solver targeting3 prunes immediately after selecting5. A later item-2 could complete the solution. The prune was sound only when remaining items were nonnegative.

Artifact: state the old domain, exhibit the failure, and derive a safe lower/upper completion range for signed remaining items: add all negative remaining values for a lower bound and all positive ones for an upper bound. If target lies outside that range the branch is impossible; being inside does not guarantee a solution. Compare the repaired search with complete enumeration on small cases.