Skip to main content

Independent Mastery Assessment

Allow 3–4 hours for an initial independent attempt, then a separate review. Do not consult the solution key or reference code during the attempt. Disclose assistance; assisted work is practice and needs a fresh independent recheck. Use the competency rubric, not a single aggregate pass score.

A1. Model before algorithm​

Four declared vertices have records (0,1,6),(0,1,2),(1,2,0) representing directed route costs. Specify direction, multiplicity, numeric domain, absent-edge representation and source-0 outputs. Give a path to 2 with original edge IDs. Explain what a scalar matrix may discard, and how the question changes if the numbers are channel capacities or edge directions are reversed.

A2. Reachability, SCCs and blocked descendants​

Graph on 0–5: 0→1,1→0,1→2,2→3,3→2,3→4, with isolated 5. Give source-0 BFS distances, the SCC partition, condensation edges and Kahn's cycle outcome. Identify which vertices actually belong to cycles and which are only blocked. Explain the finish-order/transposition proof and the state needed for iterative DFS.

A3. Nonnegative routes​

Edges by ID: 0:0→1:9, 1:0→2:2, 2:2→1:1, 3:1→3:4, 4:2→3:8; vertex 4 is isolated. Trace lazy Dijkstra from 0, return distances and parent edge IDs, and identify stale entries. Prove safe finalization and price time and space without assuming at most one heap entry per vertex. Give a negative-edge counterexample to the finalization argument.

A4. Signed routes and round semantics​

For six vertices and edges 0→1:4,1→2:-5,2→1:2,0→3:8,2→4:1,5→5:-1, classify every source-0 target as finite, unreachable or unbounded. Explain why not every reachable vertex is affected. Contrast snapshot and in-place relaxation on a two-edge chain, and explain the extra-pass plus reachability procedure. How should Floyd–Warshall initialize a negative self-loop and parallel edges?

A5. Forests with ties​

Undirected edges by ID: (0,1,1),(1,2,1),(0,2,1),(3,4,-2),(3,3,-99). Give an optimal spanning forest, its cost and edge count. State tied cut/cycle rules precisely, give the respecting-cut exchange proof, and explain how to verify an alternative witness. Contrast this objective with a shortest-path tree.

A6. A checkable flow optimum​

Source s, sink t, edges s→a:3,s→b:2,a→b:1,a→t:2,b→t:3. Return a maximum value, per-edge feasible flow in that order, and an equal-capacity cut. Verify conservation and terminal net values. Explain reverse residual arcs and why an original antiparallel edge requires a separate record. State the Edmonds–Karp path rule and outline its capacity-independent augmentation bound.

A7. Assignment reduction​

Three workers and two jobs have allowed pairs (0,0),(0,1),(1,0),(2,1). Give a maximum matching and an upper-bound obstruction to assigning everyone. Prove both directions of the flow reduction, including integrality. Explain what changes if worker 0 can take two jobs or the objective becomes minimum money cost.

A8. Transfer to a dependency planner​

Task durations are [3,2,4,1], and edges 0→2,1→2,2→3 mean prerequisite→dependent. Give a valid order, earliest starts/finishes and makespan under unlimited workers. State why this is not automatically an optimal one-worker schedule. Add edge 2→0: identify the cycle region and blocked downstream task, and define the planner's failure behavior. Explain what evidence a reviewer needs beyond a topological ordering or a screenshot of a schedule.

After submitting, consult Assessment Solutions and Scoring.