CS capstone: a verified dependency planner

Build a dependency planner that returns a precedence certificate, earliest completion times and a critical path, or rejects invalid data and supplies a cycle witness. Use eight tasks with a diamond dependency and an isolated task. The model has unlimited parallel workers, no transfer delays and no worker contention. A dependency edge u→v means u must finish before v starts; the input lists immediate prerequisites, not a precomputed transitive closure. All tasks are available at time zero subject to those edges.

The fourteen-hour core has four stages: two hours specifying, four proving, four implementing, and four quantifying/reporting. This is a project rather than another fourteen-exercise chapter. Produce these seven artefacts; each should be inspectable independently:

1. A one-page input/output contract, including invalid and empty cases.
2. A labelled graph and a table linking its tasks to input records.
3. Standalone Python implementation and a reproducible command.
4. Written order, termination and finish-time proofs tied to the actual loops.
5. Operation counts and memory analysis with a declared arithmetic model.
6. Exact and simulated finite-duration laws, including a dependence comparison.
7. A short report, fault evidence and the rubric-based self-review.

The reference implementation and its actual outputs below are a complete worked solution. First write your own contract and predict the fixture outputs, then compare the reference. Matching one printed order is insufficient: several topological orders can be correct. Assess every edge, the recurrence, a closed cycle witness, and model assumptions.

Use a list of task dictionaries with exactly id, duration, and requires. IDs are unique ASCII strings matching a leading letter followed by at most 31 letters, digits or underscores. A duration is a positive finite Python int or float; Boolean values are rejected. requires is a list of distinct known IDs. Reject unknown prerequisites and duplicate records before graph traversal. A self-dependency is a cycle. Empty input returns an empty order, empty finish map and critical path, with makespan zero.

For this CPU reference, values accepted as finite inputs must pass math.isfinite; an integer too large for that check is rejected explicitly. Integer-only fixture timing is exact Python arithmetic. Floating durations introduce rounding, and completion overflow is a declared error rather than a valid infinity time. Proofs below describe exact real arithmetic; identify this numerical boundary in your report. Validation copies prerequisite lists so later incidental mutation does not change the stored graph during planning.

Choose deterministic ties by input order, using a FIFO ready queue and the first maximum prerequisite for critical-path reconstruction. This gives reproducibility without a heap or lexicographic sort. It does not make the returned order unique mathematically. Your contract may choose another rule if you state it and revise the complexity claim.

Stage gate: reconstruct all seven edges from the table, state the empty result, and write the cycle fixture X→Y→Z→X before implementing anything.

Maintain an indegree count equal to the number of incoming edges from vertices not yet removed. Initialise it from prerequisite lists. Place every zero-indegree vertex in the ready queue. Removing v appends it to the order and decrements each outgoing child’s count once. A child enters the queue exactly when that count reaches zero. This is Kahn’s algorithm with a simple-graph input contract; allowing duplicate prerequisites silently would change the counting obligation.

When v is removed, none of its predecessors remain. Thus every predecessor is already earlier in the output. Induction over removals proves every emitted edge u→v respects position(u)<position(v). Each vertex can enter the queue once, each iteration removes a new vertex, and the finite graph ensures termination. On a DAG the algorithm removes everything: any nonempty remaining acyclic graph has a zero-indegree vertex, as proved in Module 06 by tracing predecessors and ruling out a repeat.

If removal stops early, every remaining vertex has a remaining predecessor. Following such predecessors eventually repeats a vertex in the finite graph, proving a directed cycle exists. A remaining vertex may merely be downstream of that cycle, so returning the entire leftover list is not a cycle witness. The reference performs an iterative colour DFS, keeping an active path and positions. An edge to an active vertex closes the path segment into a genuine directed cycle. The returned witness repeats its start at the end and every adjacent pair is checked against the graph.

Proof obligations and timing recurrence

For a valid order, define earliest finish F(v)=d(v)+max_(u→v) F(u), with empty maximum zero. Start time is that maximum. This recurrence is not the sum of all predecessor durations: independent branches can overlap. For the fixture, F(A)=2, F(B)=5, F(C)=6, F(D)=8, F(E)=9, F(F)=11, F(G)=5 and F(H)=14. A valid order is A,G,B,C,D,E,F,H, but the finish values do not depend on the chosen valid order.

Prove the recurrence by induction over the order. Base vertices have no prerequisites and can start at zero. For an inductive vertex, no feasible schedule can start it before its latest predecessor finishes. The previously computed predecessor times attain their lower bounds, and unlimited workers allow v to start at their maximum without delaying another task. Therefore the recurrence both lower-bounds and attains the earliest finish. The maximum finish is the earliest overall makespan under this model.

For a critical-path certificate, remember a predecessor achieving each maximum, then follow parents backwards from a vertex achieving the overall maximum. Reverse that list. It is a directed path, and its durations sum to T by repeated substitution of the recurrence. Every feasible schedule must take at least the duration of any dependency path, so this path supplies a makespan lower-bound certificate. Ties may create several valid critical paths; returning one is sufficient. Zero-task input needs its separately defined empty path rather than an argmax of an empty set.

Stage gate: submit these proofs in your own words and identify which lines of your code initialise, preserve and use each invariant. A statement that “Kahn is standard” does not replace the proof tied to your edge convention.

Reference planner and contract cases

Run with Python 3.11+; no numerical package is required. Inspect the returned dictionary and the CycleError witness. The six invalid cases exercise duplicate IDs, missing prerequisites, zero duration, NaN, Boolean duration and repeated prerequisite entries. Empty input, exact finish values, every edge’s output position and every cycle edge are asserted. Extend the challenges with a self-loop, a cycle plus a downstream tail, an invalid ID and a long chain that would expose a recursive DFS depth limit.

Download lab1_verified_dependency_planner.py

"""Reference planner: simple prerequisite edges, unlimited parallel workers.

An input list preserves deterministic tie order. Validation rejects rather than
silently repairing duplicates. Critical-path proofs use exact real durations;
the reference fixture uses integers so its calculations are exact in Python.
"""
from collections import deque
import math
import re

class CycleError(ValueError):
    def __init__(self, witness):
        self.witness = witness
        super().__init__('cycle: '+' -> '.join(witness))

def cycle_witness(children):
    colour = {v: 0 for v in children}
    for start in children:
        if colour[start]:
            continue
        path, positions = [start], {start: 0}
        colour[start] = 1
        stack = [(start, iter(children[start]))]
        while stack:
            v, iterator = stack[-1]
            try:
                child = next(iterator)
            except StopIteration:
                colour[v] = 2
                stack.pop()
                positions.pop(v)
                path.pop()
                continue
            if colour[child] == 1:
                return path[positions[child]:]+[child]
            if colour[child] == 0:
                colour[child] = 1
                positions[child] = len(path)
                path.append(child)
                stack.append((child, iter(children[child])))
    return []

def plan(tasks):
    if not isinstance(tasks, list):
        raise ValueError('tasks must be a list')
    durations, predecessors = {}, {}
    for task in tasks:
        if not isinstance(task, dict) or set(task) != {'id','duration','requires'}:
            raise ValueError('each task needs exactly id,duration,requires')
        v, duration, requires = task['id'], task['duration'], task['requires']
        if not isinstance(v, str) or not re.fullmatch(r'[A-Za-z][A-Za-z0-9_]{0,31}', v) or v in durations:
            raise ValueError('invalid or duplicate task id')
        if isinstance(duration, bool) or not isinstance(duration, (int,float)):
            raise ValueError('duration must be a positive finite number')
        try:
            finite = math.isfinite(duration)
        except OverflowError:
            finite = False
        if not finite or duration <= 0:
            raise ValueError('duration must be a positive finite number')
        if not isinstance(requires,list) or any(not isinstance(u,str) for u in requires) or len(set(requires)) != len(requires):
            raise ValueError('requires must be a list of distinct ids')
        durations[v], predecessors[v] = duration, requires[:]
    children = {v: [] for v in durations}
    for v, before in predecessors.items():
        for u in before:
            if u not in durations:
                raise ValueError('missing prerequisite: '+u)
            children[u].append(v)
    indegree = {v: len(predecessors[v]) for v in durations}
    ready = deque(v for v in durations if indegree[v] == 0)
    order = []
    while ready:
        v = ready.popleft()
        order.append(v)
        for child in children[v]:
            indegree[child] -= 1
            if indegree[child] == 0:
                ready.append(child)
    if len(order) != len(durations):
        witness = cycle_witness(children)
        assert witness and witness[0] == witness[-1]
        assert all(b in children[a] for a,b in zip(witness,witness[1:]))
        raise CycleError(witness)
    finish, parent = {}, {}
    for v in order:
        before = predecessors[v]
        parent[v] = max(before, key=finish.__getitem__) if before else None
        start = finish[parent[v]] if before else 0
        try:
            finish[v] = start+durations[v]
        except OverflowError as error:
            raise ValueError('completion-time arithmetic overflow') from error
        if isinstance(finish[v], float) and not math.isfinite(finish[v]):
            raise ValueError('completion-time arithmetic overflow')
    endpoint = max(order, key=finish.__getitem__) if order else None
    path = []
    while endpoint is not None:
        path.append(endpoint)
        endpoint = parent[endpoint]
    return {'order':order, 'finish':finish, 'critical_path':path[::-1], 'makespan':max(finish.values(),default=0)}

TASKS = [
    {'id':'A','duration':2,'requires':[]},
    {'id':'B','duration':3,'requires':['A']},
    {'id':'C','duration':4,'requires':['A']},
    {'id':'D','duration':2,'requires':['B','C']},
    {'id':'E','duration':1,'requires':['D']},
    {'id':'F','duration':2,'requires':['E']},
    {'id':'G','duration':5,'requires':[]},
    {'id':'H','duration':3,'requires':['F']},
]
result = plan(TASKS)
positions = {v:i for i,v in enumerate(result['order'])}
assert all(positions[u]<positions[t['id']] for t in TASKS for u in t['requires'])
assert result['makespan'] == 14 and result['critical_path'] == ['A','C','D','E','F','H']
print('order:', result['order'])
print('finish:', result['finish'])
print('critical path:', result['critical_path'], '; makespan:', result['makespan'])
assert plan([]) == {'order':[], 'finish':{}, 'critical_path':[], 'makespan':0}
print('empty input: valid empty plan, makespan zero')
cycle = [{'id':'X','duration':1,'requires':['Z']},{'id':'Y','duration':1,'requires':['X']},{'id':'Z','duration':1,'requires':['Y']}]
try:
    plan(cycle)
    raise AssertionError('cycle accepted')
except CycleError as error:
    print('cycle witness:', error.witness)
invalid = [
    TASKS+[TASKS[0].copy()],
    [{'id':'A','duration':1,'requires':['missing']}],
    [{'id':'A','duration':0,'requires':[]}],
    [{'id':'A','duration':float('nan'),'requires':[]}],
    [{'id':'A','duration':True,'requires':[]}],
    [{'id':'A','duration':1,'requires':[]},{'id':'B','duration':1,'requires':['A','A']}],
]
for case in invalid:
    try:
        plan(case)
        raise AssertionError('invalid input accepted')
    except ValueError:
        pass
print('six contract fault cases rejected; edge/order and closed-cycle witnesses checked')

order: ['A', 'G', 'B', 'C', 'D', 'E', 'F', 'H']
finish: {'A': 2, 'G': 5, 'B': 5, 'C': 6, 'D': 8, 'E': 9, 'F': 11, 'H': 14}
critical path: ['A', 'C', 'D', 'E', 'F', 'H'] ; makespan: 14
empty input: valid empty plan, makespan zero
cycle witness: ['X', 'Y', 'Z', 'X']
six contract fault cases rejected; edge/order and closed-cycle witnesses checked

Operation counts and memory

Building maps and adjacency lists requires O(V+E) expected dictionary/set operations under the usual unit-cost hashing model. Kahn removes V vertices and examines E outgoing edges. The finish pass considers every predecessor edge once, and critical-path reconstruction uses at most V parents. A cycle DFS uses at most V vertices and E edges. Thus these relevant graph passes are O(V+E), with O(V+E) stored graph plus O(V) traversal state. The iterative stack avoids a dependency on Python’s recursion limit.

ID parsing, numeric bit lengths, hashing pathological cases and input serialisation are not automatically unit-cost. For bounded IDs and ordinary small durations the model is useful; arbitrary large integer arithmetic requires bit-cost analysis. Canonical checksum sorting is additional work and must not be hidden inside a blanket linear claim. Lab 3 counts removals and inspected edges exactly on chains; it does not mistake one measured runtime for an asymptotic proof.

Educational checksum and required fault diagnoses

Canonicalise records by sorted IDs and sorted prerequisite lists, serialise keys deterministically, then sum ASCII payload bytes modulo 257. This is a small consistency exercise connecting Module 07 modular arithmetic to a data representation. Equivalent record ordering intentionally has the same checksum; the checksum does not certify a particular queue tie order. One changed digit can change the sum, but compensating digit changes can preserve it. A matching checksum therefore does not guarantee integrity, authenticity or valid scheduling data.

The reference changes A’s duration 1→2, detecting a checksum change, then changes B’s duration 2→1, restoring the original checksum despite different records. Both changes are valid durations. This is a concrete collision, not merely an abstract warning. Check input validity and mathematical output certificates independently. With a finite residue range and more possible inputs, collisions must also exist by the pigeonhole principle.

Download lab3_checksum_counts_and_worker_limits.py

"""Educational byte checksum, operation counts and scheduling scope faults."""
from collections import deque
from copy import deepcopy
import json

def checksum(tasks):
    canonical = sorted((dict(t, requires=sorted(t['requires'])) for t in tasks),key=lambda t:t['id'])
    payload = json.dumps(canonical,sort_keys=True,separators=(',',':'),ensure_ascii=True).encode('ascii')
    return sum(payload)%257

tasks = [{'id':'A','duration':1,'requires':[]},{'id':'B','duration':2,'requires':[]}]
corrupt = deepcopy(tasks)
corrupt[0]['duration'] = 2
collision = deepcopy(corrupt)
collision[1]['duration'] = 1
print('original/single-change/compensating-change checksums:', checksum(tasks),checksum(corrupt),checksum(collision))
assert checksum(tasks) != checksum(corrupt)
assert checksum(tasks) == checksum(collision) and tasks != collision
print('checksum detects this single change, but accepts this deliberate collision; no integrity guarantee')
for n in (10,100,1000):
    children = {i:[i+1] if i+1<n else [] for i in range(n)}
    indegree = [0]+[1]*(n-1)
    ready = deque([0])
    removed = inspected = 0
    while ready:
        v = ready.popleft()
        removed += 1
        for child in children[v]:
            inspected += 1
            indegree[child] -= 1
            if indegree[child] == 0:
                ready.append(child)
    assert removed == n and inspected == n-1
    print(f'chain V={n},E={n-1}: popped={removed},edge inspections={inspected}')
print('canonical checksum sorting is additional work; it is not included in the linear graph-pass count')
print('three independent tasks of duration two: unlimited workers=2; one worker=6; two workers=4')
print('topological order is a precedence certificate, not a unique order or a fixed-worker optimal schedule')

original/single-change/compensating-change checksums: 132 133 132
checksum detects this single change, but accepts this deliberate collision; no integrity guarantee
chain V=10,E=9: popped=10,edge inspections=9
chain V=100,E=99: popped=100,edge inspections=99
chain V=1000,E=999: popped=1000,edge inspections=999
canonical checksum sorting is additional work; it is not included in the linear graph-pass count
three independent tasks of duration two: unlimited workers=2; one worker=6; two workers=4
topological order is a precedence certificate, not a unique order or a fixed-worker optimal schedule

Stage gate: give actual evidence for the empty case, a cycle witness and each requested input fault, then explain the checksum collision and the scope of your operation count.

Exact and simulated duration models

Use a four-task diamond A→B,C→D with d(A)=d(D)=1. B and C each take 1 or 3 with marginal probability one-half. In the independent model their joint outcomes have probabilities one-quarter. Overall duration is T=2+max(B,C), so P(T=3)=1/4 and P(T=5)=3/4. Exact expectation is 9/2 and variance 3/4. Use Fraction weights for exact enumeration, rather than claim a floating sum is symbolic exact arithmetic.

In the shared-delay model, draw one fair duration and set B=C to it. Their marginal distributions are unchanged, but joint outcomes become (1,1) and (3,3), each one-half. Now T has equal mass at 3 and 5, mean four and variance one. This example demonstrates why dependence must be modelled, without asserting that every possible dependence changes a maximum in the same direction.

The recurrence evaluated at marginal means gives 1+max(2,2)+1=4. Independent expected completion is 4.5. In general E[max(B,C)]≥max(E B,E C), because max(B,C)≥each argument; this example gives strict inequality. A deterministic average-duration plan therefore is not generally the expected random makespan. Enumerate the joint duration law or simulate the same joint model before making an expectation claim.

The script uses 20,000 independent simulation replicates for each model and records random.Random seeds 31031/31032. Known-law Monte Carlo SE is sqrt(Var(T)/N); it quantifies simulation error of the mean, not spread of individual project completion times. Since T∈[3,5], a per-model 95% Hoeffding radius is 2sqrt(log40/(2N)), about .019206. This is a separate guarantee for each model, not a claimed simultaneous 95% statement. Pseudorandom code illustrates the ideal sampling model; the exact enumeration remains the reference.

Download lab2_exact_and_simulated_durations.py

"""Exact finite diamond law and simulation of the SAME duration models."""
import argparse
from collections import Counter
from fractions import Fraction
from itertools import product
import math
from pathlib import Path
import random

# A and D last one unit; B,C last one or three with equal marginal probability.
independent = Counter()
for b,c in product((1,3),repeat=2):
    independent[1+max(b,c)+1] += Fraction(1,4)
shared = {3:Fraction(1,2),5:Fraction(1,2)}
def moments(pmf):
    mean = sum(t*p for t,p in pmf.items())
    return mean, sum(p*(t-mean)**2 for t,p in pmf.items())
N = 20000
print('exact independent PMF:', dict(sorted(independent.items())))
print('exact shared-delay PMF:', shared)
for name, pmf, seed in [('independent',independent,31031),('shared',shared,31032)]:
    mean, variance = moments(pmf)
    rng = random.Random(seed)
    observed = []
    for _ in range(N):
        b = rng.choice((1,3))
        c = rng.choice((1,3)) if name == 'independent' else b
        observed.append(1+max(b,c)+1)
    estimate = sum(observed)/N
    se = math.sqrt(float(variance)/N)
    radius = 2*math.sqrt(math.log(2/.05)/(2*N)) # range 5-3, IID simulation replicates
    print(f'{name}: exact mean={mean}; variance={variance}; MC mean={estimate:.6f}; known-law SE={se:.6f}; Hoeffding 95% radius={radius:.6f}; seed={seed}')
    assert abs(estimate-float(mean)) < radius
print('recurrence at marginal means:', 1+max(2,2)+1, '; expected independent completion:', moments(independent)[0])
parser = argparse.ArgumentParser()
parser.add_argument('--output')
args = parser.parse_args()
if args.output:
    drawing = '<svg xmlns="http://www.w3.org/2000/svg" viewBox="0 0 760 340" role="img" aria-label="Exact independent and shared duration masses at completion times three and five"><rect width="760" height="340" fill="white"/><g font-family="system-ui" fill="#1a2e4a"><text x="380" y="30" text-anchor="middle" font-size="20">Exact completion PMF / 精确完成时间质量</text><path d="M70,70V270H700" fill="none" stroke="#64748b"/>'
    for i,t in enumerate((3,5)):
        x = 180+i*300
        for offset,pmf,colour,label in [(0,independent,'#0284c7','independent / 独立'),(65,shared,'#7e22ce','shared / 共享')]:
            mass = float(pmf[t])
            drawing += f'<rect x="{x+offset}" y="{270-220*mass}" width="50" height="{220*mass}" fill="{colour}"/><text x="{x+offset+25}" y="{255-220*mass}" text-anchor="middle" font-size="18">{mass:g}</text>'
        drawing += f'<text x="{x+55}" y="300" text-anchor="middle" font-size="20">T={t}</text>'
    drawing += '<text x="380" y="333" text-anchor="middle" font-size="17">Blue: independent / 独立; purple: shared / 共享</text></g></svg>'
    Path(args.output).write_text(drawing,encoding='utf-8')

exact independent PMF: {3: Fraction(1, 4), 5: Fraction(3, 4)}
exact shared-delay PMF: {3: Fraction(1, 2), 5: Fraction(1, 2)}
independent: exact mean=9/2; variance=3/4; MC mean=4.485700; known-law SE=0.006124; Hoeffding 95% radius=0.019206; seed=31031
shared: exact mean=4; variance=1; MC mean=3.989500; known-law SE=0.007071; Hoeffding 95% radius=0.019206; seed=31032
recurrence at marginal means: 4 ; expected independent completion: 9/2

Stage gate: report both exact laws, simulated means, sampling units, SE and bound interpretations. Explain why random duration does not change the deterministic graph-pass operation count. If the graph itself changes, that is a different input model.

Use a report of roughly 1,200–1,800 words plus code, figures and tables. Include the input schema and fixture, edge direction, real-arithmetic proof boundary, algorithm invariants, one critical-path trace, invalid/cyclic outputs, complexity model, canonical checksum collision, exact joint-law enumeration, Monte Carlo evidence and worker limitation. Record Python version, command, seeds and any changed fixture. If you alter the reference, regenerate outputs instead of copying its numbers.

For oral or written defence, answer: why does the ready count certify predecessors are already removed? Why do leftovers imply some cycle but not that every leftover is on it? Why is max rather than sum used at a join? Which schedule attains the recurrence? Why does a checksum collision invalidate an integrity guarantee? Why are E[max] and max(E) different? What changes with one or two workers?

Score each criterion from zero to its weight and cite its artefact. Recommended pass is at least 80/100, with no missing correctness proof or uncertainty explanation. A high total does not compensate for those missing obligations. The reference is evidence to compare with, not a completed learner submission merely because it executes.

The optional extension adds a worker limit and a feasible scheduling policy, then explains why the previous critical-path recurrence remains a lower bound but no longer determines the whole schedule. Three independent two-unit tasks finish at time two with unlimited workers, six with one worker, and four with two. After Module 20, formulate precedence and capacity constraints; label heuristic output separately from any claim of optimality. This extension is outside the fourteen-hour core.

Revisit Modules 04, 06, 07, 08, 21 and 24 for induction, graph structure, modular arithmetic, complexity, finite probability and Monte Carlo bounds. The capstone derives its recurrence and certificates here. Return to the course overview; the AI capstone integrates the numerical learning route.