VCE Algorithmics (HESS) common mistakes
VCE Algorithmics (HESS) · Understand the traps and how to avoid them.
When asked to prove an algorithm correct, the candidate tests it on two or three sample inputs and concludes it is correct, instead of stating an invariant and arguing initialisation, maintenance and termination.
School mathematics trains students to verify by example, and the exam's pseudocode looks like a program to be run rather than a claim to be argued. Students also conflate 'it gave the right answer on my trace' with a proof of correctness for all inputs.
What to do instead
Practise writing a three-part proof for every algorithm in the course: state the loop invariant precisely (what is true before and after each iteration), show it holds before the loop, show the body preserves it, and show the exit condition plus the invariant yields the postcondition. Do this for linear search, binary search, insertion sort and graph traversal until the structure is automatic.
The candidate analyses running time by counting lines of pseudocode or by describing the algorithm in prose ('it splits the list, so it is fast') rather than setting up and solving a recurrence or summation.
Students memorise complexity results for familiar algorithms and then try to pattern-match a new algorithm to a memorised answer. Without practice deriving recurrences from the recursive structure, they cannot handle unseen divide-and-conquer or nested-loop code.
What to do instead
For every algorithm, write the recurrence explicitly: T(n) = aT(n/b) + f(n) for divide-and-conquer, or a summation for loops. Then solve it by expansion or by the master theorem and state the resulting class. Train on unfamiliar pseudocode so pattern-matching is unavailable.
The candidate claims binary search is O(1) or O(log n) 'because it halves the list' without accounting for the cost of accessing the middle element, or claims an algorithm is O(n log n) when the recursion tree has depth n rather than log n.
Students learn the headline result without the derivation, so they cannot adapt when the recursive call sizes differ (for example T(n) = T(n-1) + n) and they misapply the halving intuition to unbalanced splits.
What to do instead
Always draw the recursion tree and label each level with its total work and the number of levels. Check whether the subproblem size shrinks by a constant factor (logarithmic depth) or by a constant amount (linear depth). Compare the sum of level costs with the base-case cost.
The candidate confuses the problem of deciding whether a solution is verifiable in polynomial time with the problem of finding a solution in polynomial time, and so writes that a problem is in NP 'because we can solve it quickly'.
The names P and NP invite the reading 'NP means not polynomial'. Students also conflate NP with NP-complete and NP-hard, and treat the classes as a hierarchy of difficulty rather than as sets of decision problems with specific definitions.
What to do instead
Write the definitions verbatim: P is the set of decision problems solvable in polynomial time; NP is the set of decision problems for which a proposed certificate can be verified in polynomial time. Test every claim against a certificate: 'given this candidate answer, can I check it in polynomial time?' Then separately state whether a polynomial-time algorithm is known.
To show a new problem is NP-complete, the candidate shows it is in NP and then reduces the new problem to a known NP-complete problem, reversing the direction of the reduction.
The reduction direction is counter-intuitive because students think of 'solving' the new problem using the known one. The exam rewards a precise chain, and a reversed reduction proves only that the known problem is at least as hard, which is already known.
What to do instead
Memorise the template as a sentence: 'To show X is NP-complete, show X is in NP, then give a polynomial-time reduction from a known NP-complete problem Y to X.' Practise writing the reduction function explicitly and proving both directions (a solution of Y maps to a solution of X, and vice versa).
The candidate describes a greedy strategy for an optimisation problem and asserts it is optimal because it 'seems to make the best local choice', without an exchange argument or a counterexample search.
Greedy algorithms are easy to state and often give the right answer on small examples, so students generalise from a few successful traces. They have not internalised that greedy correctness requires a proof that a locally optimal choice extends to a globally optimal solution.
What to do instead
For every greedy algorithm, either construct an exchange argument (show any optimal solution can be transformed to include the greedy choice without loss) or find a small counterexample. If a counterexample exists, state that the problem needs dynamic programming or another method. Practise on coin change, interval scheduling and knapsack.
When asked to design a dynamic programming solution, the candidate writes a recursive function with memoisation but cannot state the subproblem, the recurrence, the base cases and the order of evaluation as four distinct items.
Students see memoisation and tabulation as alternative tricks rather than as two implementations of the same recurrence. Without a clear subproblem definition, they double-count or miss overlapping subproblems and cannot justify the time complexity.
What to do instead
Answer in four labelled parts: (1) define the subproblem in words and as a table index, (2) write the recurrence, (3) state base cases, (4) state the evaluation order and the final answer's location. Then derive the complexity from the number of table entries times the work per entry.
The candidate draws a graph or tree and describes an algorithm's behaviour on that one instance, but does not connect the instance to a general property such as connectivity, acyclicity, bipartiteness or shortest-path correctness.
Graph questions are often presented with a small diagram, and students answer the diagram rather than the question. They also confuse breadth-first and depth-first traversal properties, such as which one finds shortest paths in unweighted graphs.
What to do instead
After any traversal, state the property being established and the invariant that guarantees it: BFS visits vertices in non-decreasing distance from the source in unweighted graphs; DFS on an undirected graph finds a back edge exactly when a cycle exists. Practise writing these justifications for arbitrary graphs, not only the one drawn.
The candidate writes pseudocode that is not a valid algorithm: variables are used before assignment, loop bounds depend on values changed inside the loop, or the return value is missing on some paths.
Students write pseudocode as informal notes rather than as a specification that a marker or a compiler could follow. Under time pressure, they omit initialisation and edge cases such as empty input or a single element.
What to do instead
Adopt a fixed template: name inputs and outputs, initialise all variables, write loops with explicit bounds, and end with an explicit return on every path. Trace the pseudocode by hand on the empty input, a one-element input and a two-element input before moving on.
The candidate states a complexity bound without specifying the model or the variable, for example writing 'O(n^2)' for a graph algorithm where n is the number of vertices but the algorithm iterates over edges, or ignoring the cost of an adjacency-matrix scan.
Students treat big-O as a label attached to an algorithm name rather than a statement about a function of a defined input size. In graph problems, the choice of adjacency list versus adjacency matrix changes the bound, and students do not say which representation they assume.
What to do instead
Always define the variables first ('let V be the number of vertices and E the number of edges'), state the data representation assumed, and derive the bound from the actual operations. For graph algorithms, give bounds in terms of both V and E, and note where a matrix representation forces a V^2 term.