Algorithms and Programming
Algorithms and Programming
This domain tests whether you can design, trace, and evaluate code: control structures, functions and scope, standard searching and sorting algorithms, recursion, and basic complexity. Items often give pseudocode and ask for output, a bug fix, or the efficiency class.
Core rules
- Algorithm properties: a finite number of unambiguous steps, with defined inputs and outputs, each step effectively executable.
- Control structures: sequence, selection (if/else, switch), and iteration (for, while). A while loop may execute zero times; a do-while executes at least once.
- Searching: linear search is O(n) and works on unsorted data; binary search is O(log n) but requires a sorted array.
- Sorting: bubble, selection, and insertion are O(n^2) worst case; merge sort and heapsort are O(n log n). Merge sort uses O(n) extra space.
- Scope: a local variable shadows a global one; parameters are passed by value in languages such as Java and Python for immutable types, while mutable objects can be modified through a reference.
Worked example
Binary search for 25 in [3, 7, 12, 19, 25, 31, 40]. Use indices 0-6. Mid = 3, value 19 < 25, so low = 4. Mid = 5, value 31 > 25, so high = 4. Mid = 4, value 25, found in three probes. A linear search would have needed five comparisons. The sorted order is what makes the halving valid.
Traps
Running binary search on unsorted data; off-by-one errors in low/high updates (use mid +/- 1, not mid); assuming recursion is faster than iteration; and labeling an O(n log n) sort as O(n^2).