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. Keep a mistake log with tags such as loose big-O instead of Theta, wrong Master Theorem case, bad loop invariant, missing base case, greedy without exchange, wrong DP state, state leakage in backtracking, or integer overflow.

Lane 1: Asymptotic Analysis and Recurrences​

Use this lane when the issue is bound-proving, summation manipulation, or recurrence solving.

Target outcomes:

  • 8 tight Theta bounds proved from explicit summations
  • 10 recurrences solved (mix of master-theorem-applicable and recursion-tree)
  • 2 amortized arguments (aggregate + accounting or aggregate + potential)
  • 2 written "this bound is not tight because ..." diagnoses

Lane 2: Correctness and Termination​

Use this lane when the algorithm runs but you cannot say why it works.

Target outcomes:

  • 6 loop-invariant proofs covering at least three distinct algorithms (search, sort, partition)
  • 6 recursive correctness proofs by strong induction
  • 4 termination arguments with explicit variants (at least one lexicographic)
  • 2 written "why my original proof was wrong" corrections

Lane 3: Paradigm Design - D&C, Greedy, Backtracking, DP​

Use this lane when you can analyze but cannot choose the right paradigm or cannot justify correctness of the one you picked.

Target outcomes:

  • 4 D&C problems with recurrence and solution
  • 4 greedy problems, each with exchange argument or written counterexample
  • 4 DP problems with state, recurrence, and both top-down / bottom-up code
  • 2 backtracking problems including pruning analysis
  • 1 written paradigm triage for a new problem you had never seen

Lane 4: Practice and Analysis Application​

Use this lane when you understand the theory but need contest-grade volume on paradigm application, testing, and debugging.

Target outcomes:

  • 6 problems solved end-to-end (triage, implement, test, verify complexity)
  • 3 problems where your first paradigm was wrong and you switched after a counterexample
  • 2 stress-testing harnesses built (brute-force oracle + generator + comparison)
  • 2 written debugging narratives explaining how an invariant check found the bug

Self-Curated Problem Set​

Build a custom set with these minimums:

  • 5 complexity-analysis and recurrence problems (mix of iterative and recursive)
  • 5 correctness proofs (mix of loop-invariant and induction)
  • 5 paradigm triage exercises on problems you have not solved before
  • 5 implementation problems (at least one per paradigm)
  • 3 stress-testing exercises with a brute-force oracle

Completion Checklist​

  • Completed at least one lane in full
  • Logged at least 12 real mistakes and corrections
  • Wrote at least 10 full paradigm-triage justifications
  • Reattempted at least 4 failed problems after review
  • Solved at least 3 problems whose correctness depends on an exchange argument, loop invariant, or strong induction you wrote