Programming: Algorithms, Data Structures and Software Development
Domain 7 - Programming: algorithms, data structures and software development
Tests algorithm design, tracing, data structures, programming constructs and the software life cycle.
Core rules
- An algorithm has finite, unambiguous, effective steps with input and output.
- Constructs: sequence, selection (if/case), iteration (while/for); trace tables track variables.
- Array is fixed-size indexed collection; list is dynamic; stack is LIFO; queue is FIFO; tree is hierarchical.
- Linear search is O(n); binary search is O(log n) but needs sorted data; bubble sort is simple but O(n²).
- SDLC: requirements, analysis, design, implementation, testing, deployment, maintenance. Testing finds defects; it does not prove absence.
Worked example
Binary search for 24 in sorted [3, 7, 12, 19, 24, 31, 40]. Low=0, high=6, mid=3 → value 19; 24>19, so low=4. Mid=(4+6)//2=5 → 31; 24<31, so high=4. Mid=4 → 24 found. Reasoning: each comparison halves the search interval; indices must stay within bounds. A linear search would check up to five elements here; binary search took three comparisons because the list was sorted.
Traps
Do not use binary search on unsorted data. Watch off-by-one errors in loops and array indices. “=” assigns; “==” compares. Stack is LIFO, queue is FIFO. Validation checks input; verification checks translation to code.