Module 2: Sorting, Searching & Fundamental Structures: 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 Sorting Correctness and Analysis Lab with only a final answer	Sorting Correctness and Analysis 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 Searching and Selection Workshop with only a final answer	Searching and Selection 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 Hashing and Priority-Queue Clinic with only a final answer	Hashing and Priority-Queue 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 Insertion Sort Teaches Lessons That Survive as vocabulary instead of a tool	Insertion Sort Teaches Lessons That Survive	The explanation names the concept but cannot decide between two cases.	Write one example, one non-example, and the rule that separates them.
Treating Mergesort Is the Divide-and-Conquer Exemplar as vocabulary instead of a tool	Mergesort Is the Divide-and-Conquer Exemplar	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.

Sorting Correctness and Analysis Lab

Source: practice/01-sorting-correctness-and-analysis-lab.md

For each statement, identify the error:

1. "Randomized quicksort has worst-case O(n log n) because the pivot is random."
2. "Counting sort violates the Omega(n log n) lower bound."
3. "Since heapsort is O(n log n) in the worst case, it is faster than quicksort in practice."
4. "Mergesort is in-place because it sorts a single array."
5. "A sort is stable as long as it is deterministic."
6. "Radix sort is always linear."

Searching and Selection Workshop

Source: practice/02-searching-and-selection-workshop.md

For each statement, identify the error:

1. "Binary search on a linked list is O(log n)."
2. "mid = (lo + hi) / 2 is always safe."
3. "Quickselect is worst-case O(n) because the recurrence is T(n) = T(3n/4) + n."
4. "To find the median of n elements you must first sort them all."
5. "A predicate-based binary search works on any boolean function of the position."
6. "std::nth_element gives you a fully sorted array."

Hashing and Priority-Queue Clinic

Source: practice/03-hashing-and-priority-queue-clinic.md

For each statement, identify the error:

1. "A hash table is O(1) worst case."
2. "Open addressing is always faster than chaining."
3. "Deleting a key in linear probing just means marking the slot empty."
4. "A binary heap is fully sorted in its array representation."
5. "Heapsort is strictly faster than quicksort because of its better worst case."
6. "Dijkstra's algorithm requires Fibonacci heaps to be efficient."
7. "You can search for an arbitrary key in a heap in O(log n)."

---

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.