Skip to main content

Book Exercise Lanes

This module's exercise system is book-driven. Use these local chunks for targeted volume after you have already learned the concept from the guide.

How To Use This Page​

  1. Finish the relevant concept page first.
  2. Solve at least one problem of your own from memory.
  3. Only then open the matching exercise lane.
  4. Implement every non-trivial algorithm from scratch once before relying on a library.
  5. Keep a mistake log with tags such as bad model, wrong representation, ran Dijkstra on negative edges, missed residual edge, confused SCC with CC, forgot path compression, or min cut double counted.

Lane 1: Representations and Traversals​

Use this lane when your main gap is modeling, representation, BFS, DFS, SCC, or topological sort.

Target outcomes:

  • 6 problems translating a verbal description into an explicit (V, E, directed?, weighted?) model
  • 4 BFS or DFS implementations on new data shapes (grids, implicit graphs, etc.)
  • 2 SCC computations with the condensation drawn explicitly
  • 2 topological-sort applications (build order, course scheduling, cycle detection)

Lane 2: Shortest Paths​

Use this lane when you can draw the graph but keep picking the wrong shortest-path algorithm or getting running times wrong.

Target outcomes:

  • 6 Dijkstra runs by hand with PQ state written out at each step
  • 3 Bellman-Ford runs, one of which detects a negative cycle
  • 2 Floyd-Warshall runs on small graphs with hand-written dist matrices
  • 2 algorithm-choice exercises where you justify the pick with a one-paragraph argument

Lane 3: Minimum Spanning Trees​

Use this lane when you can run Kruskal and Prim but cannot prove why they are correct on a specific example.

Target outcomes:

  • 4 Kruskal runs by hand, with cut-property argument for each added edge
  • 3 Prim runs by hand, starting from different roots to confirm the MST is invariant
  • 1 second-best MST computation
  • 1 single-linkage clustering run on a small 2D dataset using Kruskal with early stopping

Lane 4: Network Flow and Matching​

Use this lane when the problem is modeling - turning a non-flow-looking problem into a flow network.

Target outcomes:

  • 3 Ford-Fulkerson or Edmonds-Karp runs by hand, including residual graph state
  • 3 modeling problems turned into explicit flow networks (matching, project selection, disjoint paths)
  • 2 min-cut recoveries after a max-flow computation
  • 1 bipartite-matching implementation built on top of your Edmonds-Karp solver

Self-Curated Problem Set​

Build a custom set with these minimums:

  • 5 modeling problems (real scenario -> explicit graph)
  • 5 traversal-family problems (BFS, DFS, SCC, topological sort)
  • 5 shortest-path problems across at least three algorithm choices
  • 3 MST problems including at least one variant (bottleneck, second-best, clustering)
  • 3 flow/matching problems at least one of which is not obviously flow-shaped

Completion Checklist​

  • Completed at least one lane in full
  • Implemented BFS, DFS, Kosaraju, Dijkstra (heap), Bellman-Ford, Floyd-Warshall, Kruskal (union-find), Prim (heap), and Ford-Fulkerson at least once each, tested, and committed to your algorithms repo
  • Logged at least 10 real mistakes and their corrections
  • Wrote at least 6 sentence-form modeling justifications before coding
  • Solved at least 3 problems by recognizing a non-obvious reduction (e.g., "this is really min-cut")
  • Benchmarked at least 2 implementations against a reference and reconciled any discrepancy