A Level Paper 2: Programming Theory
Covers programming paradigms, the theory of computation, searching and sorting algorithms, writing and tracing programs, and algorithmic complexity.
Questions
Question 1 [2 marks]
Searching and Sorting Algorithms
The sorted list [3, 7, 12, 18, 24, 31, 40, 52] is searched using a binary search for the value 24. When a list has an even number of elements, take the lower of the two middle elements as the middle.
State the index (counting from 0) of the middle element checked first, and state whether the target is found on this first comparison.
Question 2 [2 marks]
Programming Paradigms
In object-oriented programming, abstraction means exposing only the essential features of an object while hiding the complex implementation details.
State what is meant by abstraction, and give one benefit it gives to a programmer using the object.
Question 3 [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 4 [3 marks]
Programming: Trace, Write and Explain
The following pseudocode is executed:
total = 0
FOR i = 1 TO 4
total = total + i * 2
NEXT i
OUTPUT total
Complete a trace of the value of total after each iteration of the loop, and state the value output.
Question 5 [3 marks]
Algorithmic Complexity
A program contains the following pseudocode, where n is the length of list:
FOR i = 1 TO n
FOR j = 1 TO n
total = total + list[i] * list[j]
NEXT j
NEXT i
State the time complexity of this code in Big O notation, and explain how the nested loops lead to this complexity.
Question 6 [3 marks]
Theory of Computation
A finite state machine has states S0 (start), S1 and S2 (accepting state). From S0, input a goes to S1 and input b goes to S0. From S1, input a goes to S1 and input b goes to S2. From S2, any input stays at S2.
Trace the machine for the input string aab, and state whether the string is accepted.
Question 7 [4 marks]
Searching and Sorting Algorithms
Merge sort divides a list into sublists, sorts them, then merges the sorted sublists back together.
Two sorted sublists, [2, 9, 11] and [4, 6, 15], are merged into a single sorted list by repeatedly comparing the front elements of each sublist and taking the smaller.
Show the merged list.
Question 8 [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 9 [5 marks]
Searching and Sorting Algorithms
A sorting algorithm is described as stable if two elements that compare as equal always keep their original relative order after sorting.
A list of exam entries is sorted by grade: (Alex, grade B), (Bo, grade A), (Casey, grade B). A stable sort by grade should keep Alex before Casey in the result, since they are both grade B and Alex appeared first.
Explain why a stable sort matters in this scenario, and state whether a standard bubble sort, which only swaps adjacent elements that are strictly out of order, is stable.
Question 10 [5 marks]
Theory of Computation
A decision problem is in class P if an algorithm exists that can solve any instance of it in polynomial time. A decision problem is in class NP if, given a proposed solution, that solution can be checked (verified) in polynomial time, even if no polynomial-time algorithm is known to find a solution from scratch.
Explain the difference between a problem being in P and a problem being in NP, and state one fact about the relationship between the two classes that is not yet known to be proven either way.
Question 11 [5 marks]
Searching and Sorting Algorithms
A sorted list contains 15 elements, and a binary search is used to find a target value.
State the maximum number of comparisons a binary search could need for this list, and explain your reasoning using the fact that each comparison at most halves the number of elements still to be searched.
Question 12 [4 marks]
Algorithmic Complexity
Four algorithms have time complexities O(log n), O(n), O(n log n) and O(n^2).
Order these four complexities from most efficient to least efficient for large values of n, and identify which of the four would be the best choice for sorting a very large list, given that general comparison-based sorting needs at least a constant multiple of n log n comparisons in the worst case.
Question 13 [6 marks]
Theory of Computation
A simple Turing machine has a tape of cells, each holding a 0, 1 or blank symbol, and a read/write head that can move left or right one cell at a time.
The machine starts in state A, positioned on the leftmost cell of the tape 1 0 1 blank.
Its rules are: in state A, if it reads 1, write 1, move right, stay in state A; if it reads 0, write 1, move right, go to state B. In state B, if it reads any symbol, write 0, move right, halt.
Trace the machine's execution and state the final contents of the tape.
Question 14 [6 marks]
Algorithmic Complexity
An algorithm is timed on inputs of different sizes: n = 10 takes 1 ms, n = 100 takes 100 ms, and n = 1000 takes 10000 ms.
Using this pattern, identify which of O(n), O(n log n) and O(n^2) best matches the algorithm's growth, showing your reasoning, and state one limitation of judging time complexity from timings like these rather than from the algorithm's structure.
Question 15 [6 marks]
Programming Paradigms
A developer needs to find every customer in a large customer database whose total orders exceed 500 pounds. One option is to write a SQL query stating this condition directly. Another option is to write a Python loop that manually reads each record, adds up their orders, and checks the condition.
Explain the difference between the declarative and imperative approaches here, and recommend which is generally more suitable when working directly with a large database, justifying your answer.
Model solutions
| Question 1[2 marks] | |
|---|---|
| Answer or working | Marks |
| identifying the first middle element checked as index 3, value 18 | M1 |
| stating 24 is not found on this first comparison, since 24 is greater than 18 Award all 2 marks for a complete correct answer to the requested task. Accept equivalent valid explanations and notation. Method details not explicitly requested may be inferred from the correct requested results. The first index and whether it finds the target are requested. Naming the value 18 is optional evidence. | A1 |
| Final answer: First middle index is 3 (value 18); 24 is not found on this comparison. | |
| Question 2[2 marks] | |
|---|---|
| Answer or working | Marks |
| a definition such as: abstraction presents a simplified view of an object, showing only what it does rather than how it does it internally | B1 |
| a benefit such as: the programmer using the object can work with a simple, high-level interface without needing to understand or manage its internal complexity | B1 |
| Final answer: Abstraction hides internal complexity, showing only what an object does; it lets a programmer use it via a simple interface without needing to understand the implementation | |
| Question 3[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 4[3 marks] | |
|---|---|
| Answer or working | Marks |
| total values 2 and 6 after iterations 1 and 2 | M1 |
| total values 12 and 20 after iterations 3 and 4 | M1 |
| output 20 | A1 |
| Final answer: total after iterations: 2, 6, 12, 20; output 20. | |
| Question 5[3 marks] | |
|---|---|
| Answer or working | Marks |
| recognising the inner loop runs n times for each iteration of the outer loop | M1 |
| recognising the total number of iterations is n multiplied by n | M1 |
| O(n^2) | A1 |
| Question 6[3 marks] | |
|---|---|
| Answer or working | Marks |
| correctly moving S0 to S1 to S1 on the two a inputs | M1 |
| moving S1 to S2 on the final b input | A1 |
| stating the string is accepted, since S2 is an accepting state | A1 |
| Final answer: Accepted - the machine ends in accepting state S2 | |
| Question 7[4 marks] | |
|---|---|
| Answer or working | Marks |
| correctly comparing the front elements at each step (2 then 4, then 6, then 9, then 11) | M1 |
| taking the smaller element each time until one sublist is empty | M1 |
| appending the remaining element from the non-empty sublist | A1 |
| the complete merged list 2, 4, 6, 9, 11, 15 Award all 4 marks for the complete correct requested answer: [2,4,6,9,11,15]. 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: [2,4,6,9,11,15]. | |
| Question 8[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 9[5 marks] | |
|---|---|
| Answer or working | Marks |
| identifying equal-grade entries as the relevant group | B1 |
| explaining that stability preserves their original relative order. Accept any equivalent valid explanation, without inventing a submission-order context. | B1 |
| applying that preservation to Alex and Casey | B1 |
| keeping Alex before Casey. Award both marks for Alex stays before Casey, or an equivalent contextual explanation. A separate account of what an unstable sort might do is optional. | B1 |
| stating that standard bubble sort is stable. Explaining why bubble sort is stable is optional. Award all 5 marks for preserving the original order of equal-grade entries, keeping Alex before Casey, and stating that standard bubble sort is stable. | B1 |
| Final answer: Stability preserves the original order of equal-grade entries, keeping Alex before Casey. Standard bubble sort is stable. | |
| Question 10[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that P requires existence of a polynomial-time decision algorithm, not necessarily one currently known | B1 |
| explaining that NP requires polynomial-time verification of polynomial-size yes-instance certificates | B1 |
| explaining the solving-versus-checking distinction, for example that every P problem is in NP but NP membership alone does not establish a polynomial-time solver | B1 |
| stating that whether P equals NP remains unproved: B1 for identifying the equality question and B1 for its unresolved status; no separate explanation or claim about researchers beliefs is required 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 |
| Final answer: P: solvable in polynomial time; NP: a proposed solution can be checked in polynomial time. Every P problem is in NP, but whether P = NP is a famous unsolved question | |
| Question 11[5 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that each unsuccessful comparison removes about half the candidates | M1 |
| a valid shrinking sequence such as 15,7,3,1. | M1 |
| accounting for a final comparison on the last candidate | A1 |
| maximum 4 comparisons. | A1 |
| a coherent link between repeated halving and that bound, including equivalent reasoning or floor(log2(15))+1=4. A logarithm expression is not required. | B1 |
| Final answer: Maximum 4 comparisons. The largest remaining candidate counts after unsuccessful comparisons are 15 -> 7 -> 3 -> 1 -> 0. A deepest successful search also uses 4 comparisons. | |
| Question 12[4 marks] | |
|---|---|
| Answer or working | Marks |
| placing O(log n) before O(n) in increasing growth order | M1 |
| the complete order O(log n), O(n), O(n log n), O(n^2), from most to least efficient | A1 |
| identifying O(n log n) as the best listed choice for general comparison-based sorting; no separate reason is required 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 |
| Final answer: Most to least efficient: O(log n), O(n), O(n log n), O(n^2); O(n log n) is the best achievable for sorting a large list | |
| Question 13[6 marks] | |
|---|---|
| Answer or working | Marks |
| reading the first cell (1) in state A, writing 1 (no change) and moving right, remaining in state A | M1 |
| reading the second cell (0) in state A, writing 1 and moving right | M1 |
| transitioning to state B at this point | A1 |
| reading the third cell (1) in state B and writing 0 | M1 |
| moving right and halting | A1 |
| the final tape contents 1, 1, 0, blank | A1 |
| Final answer: Final tape: 1, 1, 0, blank | |
| Question 14[6 marks] | |
|---|---|
| Answer or working | Marks |
| explaining the quadratic timing pattern, either by the factor-10 input and factor-100 time changes or by showing that t/n^2 is constant (0.01 ms) across all samples. Either complete method earns all three marks; separate ratio statements are not required when using the constant-quotient method. Award up to M2 for correct incomplete pattern reasoning. This row begins a shared allocation of 3 marks for the same requested result or explanation. | M1 |
| 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. | M1 |
| 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. | M1 |
| selecting O(n^2) as the best fit | A1 |
| stating one valid limitation, such as timings depending on hardware or particular inputs; no second limitation or separate explanation is required 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 |
| Final answer: O(n^2): a 10x increase in n gives a 100x increase in time, matching (10n)^2 = 100n^2. Limitation: timings depend on hardware/inputs and are not a guaranteed bound | |
| Question 15[6 marks] | |
|---|---|
| Answer or working | Marks |
| explaining that SQL states the desired customer condition and leaves execution to the database | B1 |
| explaining that the Python loop specifies the reading, summing and testing steps | B1 |
| a scenario-linked recommendation, generally SQL directly on the database; accept a sound alternative | B1 |
| a sound developed justification linking the recommendation to the large database, such as engine-managed optimisation of filtering and aggregation near the stored data. One sufficiently developed reason earns all three marks; no separate second benefit or per-customer aggregation explanation is required. Award up to B2 for correct incomplete justification. 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: SQL is declarative (states the condition, leaves the how to the database); the Python loop is imperative (states the steps). SQL is generally preferable here since the database can use indexes to search efficiently, and the query is shorter and less error-prone | |