Computational Thinking and Algorithms
Core concepts
Computational thinking means decomposing a problem, spotting patterns, abstracting away irrelevant detail, and designing a step-by-step algorithm. Candidates should be fluent with algorithm representations (pseudocode, flowcharts, structured English) and with control constructs: sequence, selection, iteration. Know the standard algorithm classes: linear and binary search, bubble/insertion/selection/merge/quick sort, and simple recursion. Be able to trace an algorithm on given input, count comparisons, and state best/average/worst-case complexity using Big-O.
Traps
- Binary search requires a sorted list; questions often present an unsorted array and expect you to notice the precondition fails.
- Distinguish a definite loop (count-controlled) from an indefinite loop (condition-controlled); off-by-one errors are the most common trace mistake.
- Big-O describes growth, not speed: an O(n log n) sort can lose to O(n²) on tiny inputs.
- Recursion needs a base case; questions ask what happens without one (stack overflow, not an infinite loop that terminates).
- "Decomposition" and "abstraction" are not synonyms: decomposition splits, abstraction hides.
Worked example
Trace binary search for 23 in [2, 5, 9, 14, 23, 30, 41]. Low=0, high=6, mid=3 (value 14) → 23>14, low=4. Mid=(4+6)//2=5 (value 30) → 23<30, high=4. Mid=4 (value 23) → found. Three comparisons; worst case for n=7 is ⌈log₂8⌉=3. Rule of thumb: for binary search, worst case = ⌈log₂(n+1)⌉ comparisons, and halving the data adds only one step.