Matura Computer Science: Algorithms and Programming

Matura Computer Science tests algorithmic thinking in Algorithms and Programming: reading a specification, choosing a method, tracing it by hand and writing correct, efficient code, usually in Python or C++. Marks come from a justified complexity argument as much as from a working program.

Core rules

• An algorithm must terminate and return the required output for every admissible input.
• Efficiency is Big-O on the dominant term: two sequential loops over n are O(n), nested loops are O(n²).
• Binary search requires a sorted sequence and halves the range each step: at most ⌈log₂n⌉+1 comparisons.
• Recursion needs a base case and a step that strictly shrinks the problem; every call consumes stack memory.
• Dynamic programming fits overlapping subproblems with optimal substructure; greedy needs a proof (exchange argument) that a local choice is safe.
• Comparison sorting is Ω(n log n) worst case; merge sort is stable and O(n log n); quicksort averages O(n log n) but degrades to O(n²) on sorted data with a bad pivot.

Worked example

Find 23 in A = [2, 5, 8, 12, 16, 23, 38, 56, 72, 91], indices 0–9. low=0, high=9, mid=4 → A[4]=16 < 23, so low=5. mid=(5+9)//2=7 → A[7]=56 > 23, so high=6. mid=(5+6)//2=5 → A[5]=23, found in 3 comparisons. The bound ⌈log₂10⌉+1 = 5 confirms it.

Traps that cost marks

• mid = (low+high)/2 producing a float, or setting high = mid instead of mid-1 - infinite loop or missed element.
• A recursive function that calls itself on the same size (no progress) or lacks a base case.
• Claiming greedy is optimal without proof, or misreading “at most” as “exactly”.
• Ignoring that hash lookup is average O(1) but worst O(n).
• Off-by-one when the answer is 1-indexed but the array is 0-indexed.