Assessment Solutions and Scoring

Use after the independent attempt. Accept equivalent correct algorithms, tie choices and witnesses. Apply the per-competency rubric and critical-error gates.

A1 / C1

The graph is a directed weighted multigraph with four explicit vertices. Zero weight is valid and missing edges need a distinct sentinel. Source-0 distances are [0,2,2,None]; a route to 2 uses edge IDs [1,2]. A scalar minimum-weight matrix may preserve distances but lose physical parallel-edge identity. Capacities ask a throughput question, not additive routing; reversing edges changes source reachability. Level 3 explicitly states which representation conversion preserves which answer contract and includes conversion/validation costs.

A2 / C2

BFS distances [0,1,2,3,4,None]. SCCs {0,1},{2,3},{4},{5}; condensation edges {0,1}→{2,3}→{4} with isolated {5}. Kahn can emit 5 but not a full order. Actual cycle vertices are 0,1,2,3; vertex 4 is only downstream-blocked. Kosaraju's component finish ordering prevents a transpose search from escaping to another unvisited component. Iterator frames retain the next neighbor and produce a finish event only after all children finish. Level 3 distinguishes weak components, reaches, SCC maximality and cycle witnesses.

A3 / C3

Distances [0,3,2,7,None]; parent IDs [None,2,1,3,None]. Records for vertex 1 at 9 and vertex 3 at 10 become stale. Current minimum extraction is safe because a cheaper path would cross from a finalized prefix to a frontier vertex with a tentative label no larger than that path, contradicting the minimum; nonnegative remaining edges are essential. Lazy-heap bounds are O(V+E log(E+2)) time and O(V+E) space including representation. Counterexample 0→1:2,0→2:5, 2→1:-10 has true distance -5 to 1 despite early extraction at 2. Level 3 handles zero/parallel edges and explains why indexed-heap space cannot be assumed.

A4 / C4

Labels [0,-inf,-inf,8,-inf,None]. Cycle 1→2→1 has cost -3; it reaches 4 but not 3. Vertex 5's negative self-loop is source-unreachable. An in-place pass over 0→1:1,1→2:1 can set distance 2 immediately; a snapshot round cannot. After V-1 passes, seed still-improving reachable heads and traverse descendants. Floyd–Warshall sets diagonal zero then takes minima with every input edge, so negative self-loops and cheaper parallel edges survive. Level 3 explains pairwise cycle effects and the absence of a finite optimum witness in affected regions.

A5 / C5

Choose IDs [0,1,3] (or another two triangle edges plus 3), total 0, three edges for V-c=5-2. Ignore the self-loop, even though its weight is very negative. Light cut edge: some MST, or every MST if uniquely light. Heavy cycle edge: some MST omits it, or all omit it if uniquely heavy. The cut must respect the already chosen forest; exchange an uncommitted crossing edge without increasing weight. Verify edge identity, coverage, acyclicity and sum, then optimality. Level 3 supplies an alternative tied optimum and a shortest-path-tree counterexample.

A6 / C6

Value 5; flows [3,2,1,2,3]; cut {s} has capacity 3+2=5. At a, inflow 3 equals 1+2 outflow; at b, inflow 2+1 equals 3 outflow. Terminal net values match. Reverse residual arcs cancel existing flow and must be paired per original edge, not confused with separately capacitated antiparallel originals. Edmonds–Karp uses fewest-hop positive-residual paths. BFS levels never decrease; repeated critical saturation of one oriented edge requires its tail level to advance, giving O(VE) augmentations and the usual O(VE²) work plus setup. Level 3 can reject a corrupted vector that preserves the reported scalar value.

A7 / C7

One maximum is (1,0),(2,1) of size 2; many witnesses are possible. All three workers have only two neighbors, a Hall obstruction to assigning everyone. Each matching maps to feasible unit paths; integral flow maps back to distinct endpoint pairs because terminal capacities are one. Increase worker 0's source capacity for two allowed jobs and change output semantics; job capacities remain one. Monetary minimization requires a cost objective and appropriate algorithm, not merely maximum cardinality. Level 3 distinguishes preference stability as yet another contract and prices the constructed network.

A8 / C8

An order is [0,1,2,3]. Earliest starts [0,0,3,7], finishes [3,2,7,8], makespan 8 with unlimited workers and nonnegative fixed durations. Task 2 waits for both predecessors, so use max predecessor finish, not min or sum. With one worker all four tasks require total work 10; critical-path length 8 is only a lower bound, not an attainable one-worker makespan.

Adding 2→0 makes SCC {0,2} cyclic; task 3 is downstream-blocked; task 1 is outside that region. A planner can return cycle diagnostics and refuse a complete schedule rather than treating the condensed cycle as a runnable task. Review needs edge-direction/model checks, SCC evidence, order inequalities, start/finish recurrence and resource assumptions. Level 3 revises the model for the changed worker limit or graph mutation without carrying over the old guarantee.