A Level Paper 5: Algorithms and Theory
Covers trees and graphs, algorithmic complexity, programming paradigms, the theory of computation, searching and sorting algorithms, and writing and tracing programs.
Questions
Question 1 [2 marks]
Algorithmic Complexity
A hash table allows a value to be looked up directly by its key.
State the average-case time complexity of a lookup in a hash table, using Big O notation, and give a brief reason.
Question 2 [3 marks]
Theory of Computation
In formal language theory, an alphabet is a finite set of symbols, a string is a finite sequence of symbols from an alphabet, and a language is a set of strings over an alphabet.
For the alphabet {a, b}, state how many different strings of length 2 exist over this alphabet, listing them, and explain how this count would change for an alphabet of 3 symbols.
Question 3 [3 marks]
Searching and Sorting Algorithms
A linear search checks each element of a list in turn, starting from index 0, until the target is found or the list is exhausted.
State the best-case number of comparisons for a linear search on a list of n elements, describe the circumstance in which this best case occurs, and state the best-case time complexity in Big O notation.
Question 4 [4 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called SumEvens that takes a list of integers, numbers, as its parameter, and returns the sum of only the even values in the list.
Question 5 [4 marks]
Algorithmic Complexity
A program stores n readings in a 1-dimensional array, and separately stores the pairwise differences between every two readings in an n by n 2-dimensional array.
State the space complexity of each array, in terms of n, using Big O notation, and briefly explain the difference.
Question 6 [4 marks]
Trees and Graphs
A directed graph has vertices P, Q, R, S with directed edges P->Q, Q->R, R->P, R->S.
State the in-degree and out-degree of vertex R, where in-degree is the number of edges pointing into a vertex and out-degree is the number of edges pointing out of it.
Question 7 [4 marks]
Searching and Sorting Algorithms
The list [5, 1, 4, 2] is sorted using a bubble sort, comparing and swapping adjacent elements from the start of the list to the end on each pass, stopping once a complete pass makes no swaps.
State the number of swaps made during the first pass and the contents of the list after the first pass, and state the total number of passes performed, including the final pass that confirms the list is sorted by making no swaps.
Question 8 [3 marks]
Programming Paradigms
A class called Student defines attributes such as name and yearGroup, plus methods that act on them.
Explain the difference between a class and an object, using Student as an example, and state what is meant by instantiation.
Question 9 [4 marks]
Algorithmic Complexity
A binary search on a sorted list repeatedly compares the target with the middle element and discards half the remaining list.
A sorted list holds exactly 64 items.
State the maximum number of comparisons a binary search would need to find (or fail to find) a target in this list, and explain how you arrived at this figure.
Question 10 [4 marks]
Programming Paradigms
A subclass Cat overrides a speak() method inherited from a superclass Animal, giving its own implementation.
A separate class Calculator has two methods both named add: one taking two integer parameters, and one taking three integer parameters.
Explain the difference between method overriding and method overloading, using these two examples.
Question 11 [4 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called IsPalindrome that takes a string, s, as its parameter, and returns TRUE if s reads the same forwards and backwards, and FALSE otherwise. You may assume a function LEN(s) returns the length of s, and that individual characters of s can be accessed using s[i], indexed from 0.
Question 12 [3 marks]
Programming Paradigms
In functional programming, a pure function always returns the same output for the same input and has no side effects.
Explain what is meant by a side effect, and give one example of a side effect a function might have.
Question 13 [5 marks]
Algorithmic Complexity
A program contains the following pseudocode, where n is a positive integer:
count = 0
FOR i = 1 TO n STEP 2
count = count + 1
NEXT i
State the time complexity of this loop in Big O notation, in terms of n, and explain whether incrementing i by 2 each time, rather than 1, changes the complexity class.
Question 14 [5 marks]
Programming Paradigms
In functional programming, functions can be treated as first-class values: they can be assigned to variables, passed as arguments to other functions, and returned from other functions.
Explain what is meant by a higher-order function, and give one example of how a higher-order function might be used to apply an operation to every item in a list.
Question 15 [6 marks]
Searching and Sorting Algorithms
Insertion sort builds a sorted section at the start of a list by inserting each new element into its correct position, shifting larger elements along to make room.
The nearly-sorted list [2, 5, 9, 14, 8, 20] is sorted using insertion sort.
State how many shifts are needed to insert 8 into its correct position within the already-sorted section 2, 5, 9, 14, and explain why insertion sort performs much better on a nearly-sorted list like this than on a list in reverse order, referring to its best-case and worst-case time complexities.
Question 16 [4 marks]
Programming: Trace, Write and Explain
A student writes the following pseudocode, intended to output every element of a list, values, which has 6 elements (indices 0 to 5):
FOR i = 1 TO 6: OUTPUT values[i] ; NEXT i
Explain why this code either misses an element or causes an error, and rewrite the FOR line so the code works correctly for a list of any length.
Question 17 [6 marks]
Searching and Sorting Algorithms
Quicksort partitions a list around a pivot, then recursively sorts the sublist before the pivot and the sublist after the pivot.
The list [7, 3, 9, 1, 5] is partitioned using the last element, 5, as the pivot, giving the sublist [3, 1] before the pivot and [7, 9] after it, with 5 at index 2.
State the two recursive calls made next, and explain why quicksort's worst-case time complexity is O(n^2) even though its average case is O(n log n).
Question 18 [6 marks]
Programming: Trace, Write and Explain
Write pseudocode for a function called FindIndex that takes a list, items, and a target value, target, as parameters, and returns the index (counting from 0) of the first occurrence of target in items, or -1 if target does not appear in the list.
Explain why the function should return -1 rather than, for example, 0, when the target is not found.
Question 19 [6 marks]
Searching and Sorting Algorithms
The list [6, 2, 9, 1, 8, 3] is partitioned using quicksort, taking the first element, 6, as the pivot. Elements smaller than the pivot are moved before it, and elements larger than or equal to it are moved after it, preserving their relative order within each group.
State the two sublists formed either side of the pivot after partitioning, and the pivot's final index (counting from 0).
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| O(1) | B1 |
| a reason such as a key's hash value maps directly to a storage location, so no searching through other elements is normally needed | B1 |
| Final answer: O(1) - a key's hash maps directly to its storage location | |
| Question 2[3 marks] | |
|---|---|
| Answer or working | Marks |
| recognising each of the 2 positions in the string can independently be either of the 2 symbols | M1 |
| the 4 strings: aa, ab, ba, bb | A1 |
| stating an alphabet of 3 symbols would give 3^2 = 9 strings of length 2, since the count is (alphabet size) to the power of (string length) | B1 |
| Final answer: 4 strings of length 2 (aa, ab, ba, bb); with 3 symbols this would become 3^2 = 9 | |
| Question 3[3 marks] | |
|---|---|
| Answer or working | Marks |
| stating the best case is 1 comparison | B1 |
| describing this occurring when the target is the first element checked, at index 0 | B1 |
| stating the best-case time complexity is O(1) | B1 |
| Final answer: Best case: 1 comparison, when the target is at index 0; best-case complexity O(1) | |
| Question 4[4 marks] | |
|---|---|
| Answer or working | Marks |
| SumEvens with the numbers parameter and a zero accumulator | M1 |
| iterating through all values | M1 |
| adding each even value and excluding odd values | M1 |
| returning the resulting sum; equivalent valid algorithms receive credit | A1 |
| Final answer: FUNCTION SumEvens(numbers) total = 0 FOR EACH v IN numbers IF v MOD 2 = 0 THEN total = total + v ENDIF NEXT v RETURN total ENDFUNCTION | |
| Question 5[4 marks] | |
|---|---|
| Answer or working | Marks |
| the 1-dimensional array having space complexity O(n) | B1 |
| a reason such as it storing exactly one value per reading | B1 |
| the 2-dimensional array having space complexity O(n^2) | B1 |
| a reason such as it storing one value for every pair of readings, and there are n multiplied by n such pairs | B1 |
| Final answer: 1D array: O(n); 2D array: O(n^2), because it stores a value for every pair of the n readings | |
| Question 6[4 marks] | |
|---|---|
| Answer or working | Marks |
| correctly identifying the incoming count as the in-degree | B1 |
| its value 1. Award both marks for in-degree 1 alone. | B1 |
| correctly identifying the outgoing count as the out-degree | B1 |
| its value 2. Award both marks for out-degree 2 alone. Award all 4 marks for in-degree 1 and out-degree 2 alone. Naming edges is optional evidence; accept equivalent valid notation. | B1 |
| Final answer: In-degree 1; out-degree 2. | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| pass one making 3 swaps: swapping 5 and 1, then 5 and 4, then 5 and 2 as 5 moves towards the end | M1 |
| the list reading 1, 4, 2, 5 after pass one | A1 |
| pass two making 1 swap (4 and 2), giving 1, 2, 4, 5, and pass three making no swaps | M1 |
| stating 3 passes are performed in total, since the third pass confirms the list is sorted by making no swaps Award all 4 marks for the complete correct requested answer: First pass makes 3 swaps, leaving [1,4,2,5]. Total 3 passes, including the third pass with no swaps. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: First pass makes 3 swaps, leaving [1,4,2,5]. Total 3 passes, including the third pass with no swaps. | |
| Question 8[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining a class is a template or blueprint defining the attributes and methods that its objects will have, such as Student defining name and yearGroup | B1 |
| explaining an object is a specific instance created from a class, with its own actual values for those attributes, such as one particular student | B1 |
| explaining instantiation is the process of creating a new object from a class | B1 |
| Final answer: Student is the class (a template); a particular student is an object (an instance of it) with real values; instantiation is creating that object from the class | |
| Question 9[4 marks] | |
|---|---|
| Answer or working | Marks |
| stating a maximum of 7 target-to-middle comparisons for 64 items. This row begins a shared allocation of 2 marks for the same requested result or explanation. | A1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | A1 |
| a valid explanation of the maximum for this list, such as six halvings leaving a singleton needing one final comparison, a correct seven-comparison worst-case trace with an explanation that it reaches the maximum, or an equivalent logarithmic calculation. Award M1 for correct but incomplete reasoning towards the maximum. No general logarithmic formula is required. This row begins a shared allocation of 2 marks for the same requested result or explanation. | M1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | M1 |
| Final answer: 7 comparisons maximum: log2(64) = 6 halvings, plus one final comparison with the last remaining item | |
| Question 10[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining overriding: a subclass redefines a method it inherits from its superclass, keeping the same method signature | B1 |
| identifying Cat's speak() as overriding, since it replaces Animal's version when called on a Cat object | B1 |
| explaining overloading: a class defines multiple methods with the same name but different parameters (a different signature) | B1 |
| identifying Calculator's two add methods as overloading, since the correct one is chosen based on how many arguments are passed | B1 |
| Final answer: Overriding (Cat's speak()) redefines an inherited method with the same signature; overloading (Calculator's two add methods) gives multiple methods the same name with different parameters | |
| Question 11[4 marks] | |
|---|---|
| Answer or working | Marks |
| IsPalindrome with parameter s | M1 |
| comparing mirrored characters, or an equivalent comparison with the reversed string | M1 |
| returning FALSE when any corresponding characters differ | A1 |
| returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint bound | A1 |
| Final answer: FUNCTION IsPalindrome(s) left = 0 right = LEN(s) - 1 WHILE left < right IF s[left] != s[right] THEN RETURN FALSE ENDIF left = left + 1 right = right - 1 ENDWHILE RETURN TRUE ENDFUNCTION | |
| Question 12[3 marks] | |
|---|---|
| Answer or working | Marks |
| explaining an observable effect outside the returned value: B1 for an observable change or effect and B1 for distinguishing it from merely returning a result This row begins a shared allocation of 2 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 2-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| giving one concrete example, such as changing a global variable, writing a file or printing output; no separate example explanation is required | B1 |
| Final answer: A side effect is a change made outside the function's return value, e.g. modifying a global variable | |
| Question 13[5 marks] | |
|---|---|
| Answer or working | Marks |
| recognising approximately n/2 iterations, or an equivalent exact count | M1 |
| stating O(n) | A1 |
| explaining that step 2 changes only a constant factor, which Big O ignores, so the complexity class remains the same as for step 1. Credit this complete explanation without a further independent point. Award up to B2 for correct incomplete reasoning. This row begins a shared allocation of 3 marks for the same requested result or explanation. | B1 |
| mark 2 of the same 3-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| mark 3 of the same 3-mark allocation above. A complete response meeting that allocation earns every mark in the group; this row adds no separate requirement. Retain the partial-credit guidance stated in the first row of the group. | B1 |
| Final answer: O(n) - halving the number of iterations is a constant factor, which Big O ignores, so the complexity class is unchanged | |
| Question 14[5 marks] | |
|---|---|
| Answer or working | Marks |
| accepting another function as an argument or returning a function | B1 |
| a valid list-traversal higher-order operation such as map | B1 |
| identifying the operation function passed to it | B1 |
| applying that function to every element | B1 |
| describing correct transformed results or a clear generic transformation; a second higher-order function is not required | B1 |
| Final answer: A higher-order function takes a function as a parameter or returns one, e.g. a map function applying a given function to every item in a list | |
| Question 15[6 marks] | |
|---|---|
| Answer or working | Marks |
| 2 shifts | A1 |
| a count consistent with moving 14 and 9 past 8 | A1 |
| insertion after 5. The latter two may be inferred from the correct count for the printed section. | A1 |
| explaining that nearly sorted data needs few shifts | B1 |
| best-case O(n) on already sorted input | B1 |
| worst-case O(n^2) on reverse order because the shifts sum to 1+2+...+(n-1). Accept equivalent valid complexity explanations; an intermediate comparison trace is not required. | B1 |
| Final answer: Two shifts: 14, then 9; insert 8 after 5, producing [2,5,8,9,14,20]. Nearly sorted data needs few shifts. An already sorted list takes O(n) comparisons overall; reverse order requires 1+2+...+(n-1) shifts and O(n^2) time. | |
| Question 16[4 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that index 0 is omitted | B1 |
| explaining that index 6 is out of bounds | B1 |
| starting the corrected loop at index 0 | M1 |
| ending the corrected loop at LEN(values) - 1, or an equivalent length-dependent bound | A1 |
| Final answer: Index 0 is omitted and index 6 is outside 0..5. Replace the FOR line with FOR i = 0 TO LEN(values) - 1. | |
| Question 17[6 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the first recursive call as sorting the sublist before the pivot, [3, 1] | M1 |
| identifying the second recursive call as sorting the sublist after the pivot, [7, 9] | A1 |
| explaining the average case splits the list into two roughly equal halves each time, giving O(log n) levels of recursion with O(n) work partitioning at each level, hence O(n log n) | B1 |
| explaining the worst case occurs when a pivot is chosen that is the smallest or largest remaining value each time, for example on an already-sorted list with a fixed choice of pivot | B1 |
| explaining this gives sublists of size (n-1) and 0 at every level, meaning n levels of recursion instead of log n | B1 |
| concluding n levels each doing O(n) work partitioning gives O(n^2) overall in the worst case | B1 |
| Final answer: Recursive calls sort [3, 1] and [7, 9]; the worst case is O(n^2) because a poor pivot choice (e.g. smallest/largest each time) gives n levels of recursion instead of log n, each doing O(n) work | |
| Question 18[6 marks] | |
|---|---|
| Answer or working | Marks |
| FindIndex with items and target parameters | M1 |
| examining items within valid zero-based bounds, or an equivalent lookup; ascending traversal is one valid method, not a requirement | M1 |
| testing equality with target | M1 |
| returning the first matching index | A1 |
| returning -1 only if there was no match | A1 |
| explaining -1 distinguishes not-found from the valid index 0; accept other correct implementations | B1 |
| Final answer: FUNCTION FindIndex(items, target) FOR i = 0 TO LEN(items) - 1 IF items[i] = target THEN RETURN i ENDIF NEXT i RETURN -1 ENDFUNCTION -1 is outside the valid indices; 0 is a valid first-element index. | |
| Question 19[6 marks] | |
|---|---|
| Answer or working | Marks |
| comparing each remaining element with the pivot 6 in turn | M1 |
| identifying the elements smaller than 6, in original order, as 2, 1, 3 | M1 |
| identifying the elements larger than or equal to 6, in original order, as 9, 8 | A1 |
| placing the smaller elements before the pivot and the larger elements after it | M1 |
| the pivot 6 ending at index 3 | A1 |
| the two sublists: 2, 1, 3 before the pivot and 9, 8 after it Award all 6 marks for the complete correct requested answer: Before pivot: [2,1,3]; after pivot: [9,8]. Pivot 6 finishes at index 3. Accept equivalent valid notation and explanations. Intermediate method evidence below is optional and may be inferred from a correct requested result; do not require unasked states or extra explanations. | A1 |
| Final answer: Before pivot: [2,1,3]; after pivot: [9,8]. Pivot 6 finishes at index 3. | |