Semester 2 Project: A Versioned Release Rehearsal Planner

Build a small CLI service that schedules valuable rehearsal jobs after their preparation is ready. Reuse your module implementations and evidence. The project adds 24–36 hours of integration, verification, analysis and packaging; it does not ask you to rebuild five algorithm libraries.

Download the offline project kit. It includes a fixture, starter API, readable reference, independent checker and evidence template. Python 3.10+ needs no extra packages. Another language is valid with equivalent input/output behavior and checks. Preserve an attempt before using the reference. The kit checks behavior; the rubric also requires proof and defense.

The exact problem

A directed acyclic graph describes preparation tasks. Node duration is a positive integer; edge u→v requires u to finish before v starts. Preparations start as early as possible with unlimited parallelism and consume no rehearsal budget. Ready(v) is the earliest finish of v, including its own duration.

Each rehearsal job has a unique nonnegative integer ID, fixed half-open interval [start,end) with nonnegative start and end > start, nonnegative integer cost, integer value and a list of required preparation nodes. It is eligible only when its start is at least the maximum ready time of those nodes; an empty requirement list has release time zero. Choose distinct nonoverlapping jobs of total cost at most integer budget B, maximizing total value. Touching endpoints are compatible; zero-cost jobs and negative values are legal; the empty selection is allowed.

Selected jobs have no dependencies on other selected jobs. The preparation graph is a separate readiness computation. Constraining selection by arbitrary job dependencies would change the optimization problem and invalidate the simple interval DP. Likewise, limited preparation machines require a different model.

Stage 1: contracts and readiness

Validate IDs, durations, endpoints, budgets and prerequisite references. Reject cycles, duplicate edges/IDs and unknown references before returning a plan. Use topological processing to compute readiness. Return an ordering containing every preparation node once and an earliest-finish certificate. Verify edges respect the ordering and readiness equals duration plus the maximum predecessor finish.

Stage 2: order, optimize and recover a witness

Filter ineligible jobs. Reuse a tested stable sort by finish time, retaining input order on ties, and binary search for compatible prefixes. For eligible jobs 1..m, let p(i) be the number of earlier jobs with finish at most job i's start. Define D(i,b) as the maximum value among the first i jobs under budget b.

Base: D(0,b)=0. Skip i using D(i-1,b); if its cost c(i) fits, compare with value(i)+D(p(i),b-c(i)). Prove the two cases exhaustive and the include case compatible. Zero cost still decreases the job prefix, so it does not cause a cycle. Recover actual IDs, not just a value. Any optimum is acceptable; verify IDs, eligibility, interval compatibility, cost and value independently.

Stage 3: explicit versions and exact membership

Implement the kit's Planner API: constructor, lookup(version,id), fork(version,edits), and plan(version). Fork from any retained version using a batch of set/delete edits. Replacement keeps catalogue position; new IDs append. Keep the graph and budget fixed across forks. Invalid batches publish nothing and consume no version ID. Returned records and reports must be detached from stored history. Lookup returns a record or None for absence, including ineligible jobs; it does not query the chosen schedule.

A copied dictionary/list snapshot is an acceptable baseline. Count its copying, lookup and retention costs. A persistent sum tree alone does not maintain the optimal schedule after interval changes; any incremental replacement needs a new state invariant and proof. Optional Bloom shortcuts must preserve exact membership for every supported version and always confirm positives. They are not core scope.

Integration fixture

Preparation durations: 0:2, 1:3, 2:1, 3:2. Edges: 0→1, 0→2, 1→3, 2→3. Budget: 5. The kit contains this same input in fixtures.json.

ID	Interval	Cost	Value	Required node
10	[2,4)	2	5	0
11	[4,6)	2	6	2
12	[6,8)	2	6	1
13	[2,6)	3	10	0
14	[7,9)	2	8	3
15	[6,7)	0	2	3

Predict readiness, exclusions, optimum and witness before running the checker. Then branch from version 0 to delete 13; independently branch from version 0 to delete 14. Check every version again. Worked calibration includes the results and explains the greedy failure.

Independent verification and measurement

Enumerate subsets on tiny catalogues and compute preparation path lengths independently. The kit uses these bounded oracles, validates returned witnesses, and checks histories. Add adversarial cases: equal endpoints/finish times, empty catalogues, zero budgets/costs, negative values, cycles, redundant graph routes, duplicate IDs, failed batches, old-root branches and caller mutation.

Choose one meaningful comparison: brute force versus DP on tiny inputs, linear versus binary predecessor search, or full-copy versus a justified immutable catalogue representation. State the workload, prediction, included setup/copy/output costs, repetitions and variation. Use operation counts alongside timings. Neither one timing nor a fixed random seed proves an asymptotic or adversarial guarantee.

Complete adversarial/search transfer within this scope: a resource admission policy and a memo separating exact optimization from heuristic search. No separate AI application or production deployment is required.

Resource contract

Let V/E be graph size, J all jobs, R prerequisite references, m eligible jobs, and B budget. Readiness/validation is O(V+E+J+R); sort and predecessor work is O(m log(m+1)); the full DP table uses O((m+1)(B+1)) time and cells. Include returned witnesses, snapshot copies and retained versions. B is a numeric magnitude, so this bound is pseudopolynomial in a binary-encoded input. Declare word/bit costs. The map/set portions assume expected constant-time operations with bounded hash costs, or a dense indexed representation after an explicitly costed ID-mapping step. Do not claim deterministic linear validation from arbitrary hash tables.

Document an admission rule for table cells and input sizes, checked before expensive allocation. An over-limit request must be explicitly declined or routed to a separately specified method; a partial or approximate answer must not claim exact optimality. The kit reference deliberately has no production resource guard; adding and defending your application's guard is part of the project review, beyond its tiny test inputs.

Deliverables and acceptance

• Runnable CLI, environment/setup instructions, fixture and source revision.
• Reused module implementation links, contracts, proof and witness checks.
• Version isolation/atomic-publication tests and independent tiny-instance oracles.
• Resource analysis, admission behavior and one reproducible comparison.
• One rejected alternative with a counterexample; declared assistance and verification.
• An evidence map for S1–S6, oral defense and delayed transfer.

Suggested milestones: contracts/readiness (4–6 hours), scheduling integration (6–9), versions and verification (7–10), comparison/defense/packaging (7–11). Critical invalid plans, stale histories or unsupported optimality claims block acceptance even if the repository is polished. Existing module artifacts provide breadth; this project supplies integration. Keep raw exam work separate from the portfolio packet.

Complexity and approximation evidence

Attach the Module 6 solver-selection appendix as separate evidence for S6. Reuse its cover/matching results and reduction proof; keep the existing planner’s objective unchanged. The original 25–35-hour complexity package already counts this work; the separate computability bridge brings Module 6 to 45–65 hours.

Automata and computability evidence

Reuse the Module 6 bridge packet for S6: AC1–AC4 each require level 2 alongside CA1–CA6. Preserve the state invariant, language-boundary proof, impossibility/reduction argument and fresh transfer. A timeout called infeasible, or NP-completeness called undecidability, requires repair. This is module assessment evidence, not an additional timed exam or planner feature. Its 20–30 hours are counted in Module 6 (45–65 total), making the semester 465–660 hours.