Skip to main content

Implementation and Transfer Studio

Complete the five runnable labs after P1–P20. Timed recall is optional after correctness, proof and edge-case reasoning are reliable.

Core implementation checklist​

  • A: BFS with parent edge IDs; iterative Kosaraju; topological order or cycle failure.
  • B: lazy Dijkstra; Bellman–Ford with finite/unreachable/unbounded classifications.
  • C: Kruskal minimum spanning forest with original edge identities.
  • D: Edmonds–Karp with feasible per-edge flows and residual cut certificate.
  • E: maximum bipartite matching via an explicitly proved integral-flow reduction.

Choose a depth extension​

Implement one after the core passes: Prim with comparison to Kruskal; Floyd–Warshall with scoped negative-cycle statuses; a DFS cycle witness; 0–1 BFS; or an explicit Tarjan component-stack implementation. State its contract and proof, compare to an independent small-instance oracle, retain a counterexample and price memory.

For production transfer, use the dependency capstone. Changing direction, weights, resources or output semantics must trigger a new proof obligation. Do not silently keep an old algorithm's guarantee.

Use Practice Solutions after preserving your independent attempt. Equivalent valid witnesses are accepted.