Algorithms
Algorithms tests your ability to design, represent, trace, and compare step-by-step solutions. The exam expects pseudocode or flowcharts using sequence, selection, and iteration, plus standard searching and sorting methods.
Core rules and concepts
- An algorithm is a finite sequence of unambiguous steps that solves a problem. It must terminate and produce a result.
- Pseudocode uses assignment (← or =), INPUT/OUTPUT, IF–THEN–ELSE, and loops such as WHILE and FOR. Flowcharts use terminals, processes, decisions, and arrows.
- A trace table records each variable’s value after every step; this is the safest way to show reasoning.
- Linear search checks items in order and works on unsorted data. Binary search repeatedly halves a sorted list and is much faster for large lists.
- Bubble sort repeatedly compares adjacent items and swaps them; after each pass the largest remaining item is in place.
Worked example
Binary search for 19 in [3, 7, 11, 15, 19, 23, 27], using 0-based indices.
- low = 0, high = 6, mid = 3; value 15 < 19, so low = 4.
- low = 4, high = 6, mid = 5; value 23 > 19, so high = 4.
- low = 4, high = 4, mid = 4; value 19 matches. Found after 3 comparisons. Reasoning: each comparison discards the half that cannot contain the target because the list is sorted.
Traps
- Applying binary search to an unsorted list.
- Comparing the target with the index rather than the value at that index.
- Losing track of whether indices are 0-based or 1-based.
- Forgetting that bubble sort needs multiple passes, not one swap.