Skip to main content

Module 4: Dynamic Programming & Optimization: Mistake Clinic

This clinic turns wrong moves into reusable judgment. Use it after each practice page and again before the quiz or checkpoint.

Module-Specific Mistake Radar​

Start with these traps. Replace or extend them with real mistakes from your own work.

Mistake to look forWhere it shows upSymptomRepair evidence
Finishing DP Foundations and State Design Lab with only a final answerDP Foundations and State Design LabThe work has no failed case, trace, test, proof gap, or design stress point.Add the smallest broken example and show the repair that changes the result.
Finishing Sequence and Grid DP Workshop with only a final answerSequence and Grid DP WorkshopThe work has no failed case, trace, test, proof gap, or design stress point.Add the smallest broken example and show the repair that changes the result.
Finishing Advanced DP and Optimization Clinic with only a final answerAdvanced DP and Optimization ClinicThe work has no failed case, trace, test, proof gap, or design stress point.Add the smallest broken example and show the repair that changes the result.
Finishing Code Katas with only a final answerCode KatasThe work has no failed case, trace, test, proof gap, or design stress point.Add the smallest broken example and show the repair that changes the result.
Treating Optimal Substructure: When a Problem Admits DP as vocabulary instead of a toolOptimal Substructure: When a Problem Admits DPThe explanation names the concept but cannot decide between two cases.Write one example, one non-example, and the rule that separates them.
Treating Overlapping Subproblems: Why Naive Recursion Wastes Work as vocabulary instead of a toolOverlapping Subproblems: Why Naive Recursion Wastes WorkThe explanation names the concept but cannot decide between two cases.Write one example, one non-example, and the rule that separates them.

Practice Mistake Checks​

Pull any miss from these checks into your mistake log.

DP Foundations and State Design Lab​

Source: practice/01-dp-foundations-and-state-design-lab.md

For each statement, identify the error:

  1. "Merge sort is a DP because it is recursive."
  2. "I memoized my recursion and it got much faster, so DP applies to this problem."
  3. "The DP table stores the answer value, so reconstruction is trivial."
  4. "Tabulation is always faster than memoization."
  5. "My greedy got the right answer on the examples, so the problem admits greedy."

Sequence and Grid DP Workshop​

Source: practice/02-sequence-and-grid-dp-workshop.md

For each statement, identify the error:

  1. "In O(n log n) LIS, tails at the end is one valid LIS."
  2. "For 0/1 knapsack with a rolled array, you can iterate capacity in ascending order."
  3. "Edit distance base case is dp[0][j] = 0 because the empty string matches anything."
  4. "For strictly increasing LIS the binary search uses >, and for non-decreasing it uses >=." (hint: double-check both halves)
  5. "Rolling-array space reduction works even when you need reconstruction."

Advanced DP and Optimization Clinic​

Source: practice/03-advanced-dp-and-optimization-clinic.md

For each statement, identify the error:

  1. "Matrix chain DP can be filled in row-major order because dp[i][j] only reads dp[i'][j'] for i' <= i and j' <= j."
  2. "For balloon burst, recursing on the first balloon burst in the range is natural and clean."
  3. "In tree DP, always pick the root at vertex 0; anything else complicates the recurrence."
  4. "For TSP with n = 25, bitmask DP is fast enough."
  5. "Greedy works for 0/1 knapsack because the greedy 'largest value-per-weight ratio first' is a provable exchange argument."
  6. "Longest path in any graph can be computed by topological DP."

Repair Protocol​

For each real mistake:

  1. Reproduce the failure on the smallest example, trace, proof, query, command, or design sketch.
  2. Name the hidden assumption.
  3. Repair the artifact.
  4. Save evidence that changed: failing then passing test, corrected proof step, revised diagram, safer command, benchmark, or review note.
  5. Add one retrieval card beginning with Check... before... or Do not use... when....

Mistake Log​

DateMistakeSymptomRoot causeRepair evidenceRetrieval card
StarterPick one radar row aboveExplain how it would fail in this moduleName the assumptionAdd a counterexample or corrected artifactWrite the card before closing the page

Completion Standard​

  • At least five real mistakes are logged.
  • At least two mistakes include a counterexample or failing test.
  • At least one mistake connects to an older semester skill.
  • At least one correction changes code, a proof, a diagram, a command transcript, a query, or a design decision.