Revision Library
Choose a subject
Menu
Computer Science
Need a new topic?
Missing a topic, found a bug, or want something added?

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.

19 questions - 80 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
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 neededB1
Final answer: O(1) - a key's hash maps directly to its storage location
Mark scheme for Question 2 [3 marks]
Question 2[3 marks]
Answer or workingMarks
recognising each of the 2 positions in the string can independently be either of the 2 symbolsM1
the 4 strings: aa, ab, ba, bbA1
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
Mark scheme for Question 3 [3 marks]
Question 3[3 marks]
Answer or workingMarks
stating the best case is 1 comparisonB1
describing this occurring when the target is the first element checked, at index 0B1
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)
Mark scheme for Question 4 [4 marks]
Question 4[4 marks]
Answer or workingMarks
SumEvens with the numbers parameter and a zero accumulatorM1
iterating through all valuesM1
adding each even value and excluding odd valuesM1
returning the resulting sum; equivalent valid algorithms receive creditA1
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
Mark scheme for Question 5 [4 marks]
Question 5[4 marks]
Answer or workingMarks
the 1-dimensional array having space complexity O(n)B1
a reason such as it storing exactly one value per readingB1
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 pairsB1
Final answer: 1D array: O(n); 2D array: O(n^2), because it stores a value for every pair of the n readings
Mark scheme for Question 6 [4 marks]
Question 6[4 marks]
Answer or workingMarks
correctly identifying the incoming count as the in-degreeB1
its value 1. Award both marks for in-degree 1 alone.B1
correctly identifying the outgoing count as the out-degreeB1
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.
Mark scheme for Question 7 [4 marks]
Question 7[4 marks]
Answer or workingMarks
pass one making 3 swaps: swapping 5 and 1, then 5 and 4, then 5 and 2 as 5 moves towards the endM1
the list reading 1, 4, 2, 5 after pass oneA1
pass two making 1 swap (4 and 2), giving 1, 2, 4, 5, and pass three making no swapsM1
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.
Mark scheme for Question 8 [3 marks]
Question 8[3 marks]
Answer or workingMarks
explaining a class is a template or blueprint defining the attributes and methods that its objects will have, such as Student defining name and yearGroupB1
explaining an object is a specific instance created from a class, with its own actual values for those attributes, such as one particular studentB1
explaining instantiation is the process of creating a new object from a classB1
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
Mark scheme for Question 9 [4 marks]
Question 9[4 marks]
Answer or workingMarks
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
Mark scheme for Question 10 [4 marks]
Question 10[4 marks]
Answer or workingMarks
explaining overriding: a subclass redefines a method it inherits from its superclass, keeping the same method signatureB1
identifying Cat's speak() as overriding, since it replaces Animal's version when called on a Cat objectB1
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 passedB1
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
Mark scheme for Question 11 [4 marks]
Question 11[4 marks]
Answer or workingMarks
IsPalindrome with parameter sM1
comparing mirrored characters, or an equivalent comparison with the reversed stringM1
returning FALSE when any corresponding characters differA1
returning TRUE when all corresponding characters match; accept equivalent algorithms without requiring early return or a midpoint boundA1
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
Mark scheme for Question 12 [3 marks]
Question 12[3 marks]
Answer or workingMarks
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 requiredB1
Final answer: A side effect is a change made outside the function's return value, e.g. modifying a global variable
Mark scheme for Question 13 [5 marks]
Question 13[5 marks]
Answer or workingMarks
recognising approximately n/2 iterations, or an equivalent exact countM1
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
Mark scheme for Question 14 [5 marks]
Question 14[5 marks]
Answer or workingMarks
accepting another function as an argument or returning a functionB1
a valid list-traversal higher-order operation such as mapB1
identifying the operation function passed to itB1
applying that function to every elementB1
describing correct transformed results or a clear generic transformation; a second higher-order function is not requiredB1
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
Mark scheme for Question 15 [6 marks]
Question 15[6 marks]
Answer or workingMarks
2 shiftsA1
a count consistent with moving 14 and 9 past 8A1
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 shiftsB1
best-case O(n) on already sorted inputB1
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.
Mark scheme for Question 16 [4 marks]
Question 16[4 marks]
Answer or workingMarks
explaining that index 0 is omittedB1
explaining that index 6 is out of boundsB1
starting the corrected loop at index 0M1
ending the corrected loop at LEN(values) - 1, or an equivalent length-dependent boundA1
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.
Mark scheme for Question 17 [6 marks]
Question 17[6 marks]
Answer or workingMarks
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 pivotB1
explaining this gives sublists of size (n-1) and 0 at every level, meaning n levels of recursion instead of log nB1
concluding n levels each doing O(n) work partitioning gives O(n^2) overall in the worst caseB1
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
Mark scheme for Question 18 [6 marks]
Question 18[6 marks]
Answer or workingMarks
FindIndex with items and target parametersM1
examining items within valid zero-based bounds, or an equivalent lookup; ascending traversal is one valid method, not a requirementM1
testing equality with targetM1
returning the first matching indexA1
returning -1 only if there was no matchA1
explaining -1 distinguishes not-found from the valid index 0; accept other correct implementationsB1
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.
Mark scheme for Question 19 [6 marks]
Question 19[6 marks]
Answer or workingMarks
comparing each remaining element with the pivot 6 in turnM1
identifying the elements smaller than 6, in original order, as 2, 1, 3M1
identifying the elements larger than or equal to 6, in original order, as 9, 8A1
placing the smaller elements before the pivot and the larger elements after itM1
the pivot 6 ending at index 3A1
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.

Build a free practice pack.

Pick the topics, add the student's name and print one PDF.