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 2: Programming Theory

Covers programming paradigms, the theory of computation, searching and sorting algorithms, writing and tracing programs, and algorithmic complexity.

15 questions - 60 marks

Download PDF

Open A Level Computer Science workspace

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

Mark scheme for Question 1 [2 marks]
Question 1[2 marks]
Answer or workingMarks
identifying the first middle element checked as index 3, value 18M1
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.
Mark scheme for Question 2 [2 marks]
Question 2[2 marks]
Answer or workingMarks
a definition such as: abstraction presents a simplified view of an object, showing only what it does rather than how it does it internallyB1
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 complexityB1
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
Mark scheme for Question 3 [2 marks]
Question 3[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 4 [3 marks]
Question 4[3 marks]
Answer or workingMarks
total values 2 and 6 after iterations 1 and 2M1
total values 12 and 20 after iterations 3 and 4M1
output 20A1
Final answer: total after iterations: 2, 6, 12, 20; output 20.
Mark scheme for Question 5 [3 marks]
Question 5[3 marks]
Answer or workingMarks
recognising the inner loop runs n times for each iteration of the outer loopM1
recognising the total number of iterations is n multiplied by nM1
O(n^2)A1
Mark scheme for Question 6 [3 marks]
Question 6[3 marks]
Answer or workingMarks
correctly moving S0 to S1 to S1 on the two a inputsM1
moving S1 to S2 on the final b inputA1
stating the string is accepted, since S2 is an accepting stateA1
Final answer: Accepted - the machine ends in accepting state S2
Mark scheme for Question 7 [4 marks]
Question 7[4 marks]
Answer or workingMarks
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 emptyM1
appending the remaining element from the non-empty sublistA1
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].
Mark scheme for Question 8 [4 marks]
Question 8[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 9 [5 marks]
Question 9[5 marks]
Answer or workingMarks
identifying equal-grade entries as the relevant groupB1
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 CaseyB1
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.
Mark scheme for Question 10 [5 marks]
Question 10[5 marks]
Answer or workingMarks
explaining that P requires existence of a polynomial-time decision algorithm, not necessarily one currently knownB1
explaining that NP requires polynomial-time verification of polynomial-size yes-instance certificatesB1
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 solverB1
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
Mark scheme for Question 11 [5 marks]
Question 11[5 marks]
Answer or workingMarks
explaining that each unsuccessful comparison removes about half the candidatesM1
a valid shrinking sequence such as 15,7,3,1.M1
accounting for a final comparison on the last candidateA1
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.
Mark scheme for Question 12 [4 marks]
Question 12[4 marks]
Answer or workingMarks
placing O(log n) before O(n) in increasing growth orderM1
the complete order O(log n), O(n), O(n log n), O(n^2), from most to least efficientA1
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
Mark scheme for Question 13 [6 marks]
Question 13[6 marks]
Answer or workingMarks
reading the first cell (1) in state A, writing 1 (no change) and moving right, remaining in state AM1
reading the second cell (0) in state A, writing 1 and moving rightM1
transitioning to state B at this pointA1
reading the third cell (1) in state B and writing 0M1
moving right and haltingA1
the final tape contents 1, 1, 0, blankA1
Final answer: Final tape: 1, 1, 0, blank
Mark scheme for Question 14 [6 marks]
Question 14[6 marks]
Answer or workingMarks
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 fitA1
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
Mark scheme for Question 15 [6 marks]
Question 15[6 marks]
Answer or workingMarks
explaining that SQL states the desired customer condition and leaves execution to the databaseB1
explaining that the Python loop specifies the reading, summing and testing stepsB1
a scenario-linked recommendation, generally SQL directly on the database; accept a sound alternativeB1
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

Build a free practice pack.

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