Module 5: Advanced Data Structures & Amortized Analysis: 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 for	Where it shows up	Symptom	Repair evidence
Finishing Balanced Trees and Union-Find Lab with only a final answer	Balanced Trees and Union-Find Lab	The 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 Heaps and Amortized Analysis Workshop with only a final answer	Advanced Heaps and Amortized Analysis Workshop	The 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 Randomized and Range-Query Clinic with only a final answer	Randomized and Range-Query Clinic	The 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 answer	Code Katas	The 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 Binary Search Trees and the BST Property as vocabulary instead of a tool	Binary Search Trees and the BST Property	The explanation names the concept but cannot decide between two cases.	Write one example, one non-example, and the rule that separates them.
Treating Red-Black Trees: Invariants, Rotations, and O(log n) Guarantees as vocabulary instead of a tool	Red-Black Trees: Invariants, Rotations, and O(log n) Guarantees	The 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.

Balanced Trees and Union-Find Lab

Source: practice/01-balanced-trees-and-union-find-lab.md

For each statement, identify the error:

1. "A BST with the BST property is always balanced."
2. "Inserting a new node into a red-black tree and coloring it black preserves all invariants."
3. "Union-find supports deletion of an edge by calling split(u, v)."
4. "A skip list guarantees O(log n) worst-case per operation."
5. "Path compression reduces the stored rank of the root."

Advanced Heaps and Amortized Analysis Workshop

Source: practice/02-advanced-heaps-and-amortized-analysis-workshop.md

For each statement, identify the error:

1. "insert into a binomial heap is always O(1) because it just adds a B_0."
2. "Fibonacci heaps give Dijkstra an asymptotic improvement for every graph."
3. "An amortized O(1) operation is always fast; no single call can ever stall."
4. "Aggregate analysis is strictly weaker than potential analysis for every data structure."
5. "The Fibonacci-heap marked bit exists to speed up extract-min."

Randomized and Range-Query Clinic

Source: practice/03-randomized-and-range-query-clinic.md

For each statement, identify the error:

1. "A Bloom filter can return a false negative if two elements hash to the same slot."
2. "A segment tree uses exactly 2n nodes."
3. "A Fenwick tree supports arbitrary range-min queries."
4. "A persistent list must copy the entire list on every update."
5. "Adding more hash functions to a Bloom filter always reduces the false-positive rate."

---

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

Date	Mistake	Symptom	Root cause	Repair evidence	Retrieval card
Starter	Pick one radar row above	Explain how it would fail in this module	Name the assumption	Add a counterexample or corrected artifact	Write 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.