Computational Thinking, Problem-Solving and Programming
What the exam tests
This domain tests computational thinking and program design: decomposition, abstraction, pattern recognition, algorithm construction, pseudocode, trace tables and testing. HL candidates must also reason about efficiency and recursive solutions.
Core rules
- Decomposition breaks a problem into sub-problems; abstraction removes irrelevant detail; pattern recognition reuses known structures; algorithm design expresses a precise sequence of steps.
- Standard algorithms include linear search, binary search (sorted data only), bubble sort, selection sort and insertion sort.
- Validation checks input against rules; verification checks data matches its source. Testing can be black-box (inputs/outputs) or white-box (internal paths).
- A trace table records variable values after each statement; it is evidence of dry-running, not a substitute for testing.
- Recursion needs a base case and a recursive case that moves toward it.
Worked example
Binary search for 19 in [3, 7, 11, 15, 19, 23, 27]. Set low=0, high=6. Mid=3 gives 15; 19 is higher, so low=4. Mid=5 gives 23; 19 is lower, so high=4. Mid=4 gives 19: found after three comparisons. Reasoning: each comparison halves the remaining search space, so the algorithm is O(log n), but only because the array is sorted.
Traps
Running binary search on unsorted data; off-by-one errors in loop bounds; updating a trace table only at the end; confusing validation with verification; writing recursion with no base case; claiming a sort is efficient without stating its complexity.