A-Level Computer Science: Computational Thinking and Theory

This is the part of the course about limits — what a particular model of computation can do, what no amount of engineering will get you, and what a growth rate does and does not promise. It is also the part most often revised as a list of definitions, which is why almost every question here makes you use one.

The state machine is written out in words rather than drawn, three states and six transitions listed in full, and traced across five symbols to a state and a verdict. Then the thing it cannot do: recognising a string with equal numbers of zeros and ones, where the interesting wrong answer is that a bigger machine would eventually manage it. It would not, and the reason is worth being able to say — a fixed number of states is a fixed amount of memory, and the count has no bound.

A regular expression is given as a, then a choice of b or c, then d, and matched against four strings. Each of the three failures fails for a different reason: one takes nothing from the choice when the expression requires exactly one, one takes both alternatives, and one is missing the leading character.

Three questions are about reading an order of growth honestly. Order n log n beats order n squared eventually, and "eventually" is doing real work in that sentence — so there is also a case where the algorithm with the worse order finishes sooner on the data the firm actually has, and the right answer is about constants and input ranges rather than about the classification being wrong. Then the space-time trade-off with its failure case named: a table of remembered results pays for itself when keys repeat and fills memory for nothing when they do not.

The last three are the hard limits. An exponential running time is not defeated by a faster processor, which is what intractable means and why the hardware answer is offered. A heuristic gives you a workable answer within the time available and promises no more — neither a guess nor a guarantee, and both of those are available as options. And the halting problem is stated so the answer has to be that no such general program can exist, rather than that one would be difficult to write: a proof about what is possible, not a note about effort.

Every machine, expression and program described is invented, and every trace has been checked by hand. Nothing is reproduced from any exam board specification, past paper or mark scheme.

Zestly is an independent study tool. It is not affiliated with any exam board and it is not an exam centre.

• Trace a finite state machine through a string and say whether it is accepted
• Say why no finite state machine can count without bound, and why more states do not help
• Match a regular expression against a string and name the position at which a non-match fails
• Tell decomposition from abstraction in a described piece of work
• Compare algorithms by order of growth without ignoring constants and actual input size
• Name what a space-time trade-off spends and when it stops paying
• Explain why faster hardware does not make an intractable problem tractable
• State what a heuristic offers and what it does not, and state the halting problem as an impossibility

Ten invented machines and cases: a three-state machine traced across one, zero, one, zero, one, a string with equal zeros and ones that no finite machine recognises, the expression a(b|c)d against four candidate strings, a project split into modules beside a network model with the latency left out, order n squared against order n log n at two different input sizes, a table of remembered results, an exponential running time meeting a faster processor, a heuristic under a deadline, and a program that inspects programs. Twelve flashcards carry the vocabulary — abstraction, decomposition, accepting state, regular expression, order of growth, worst case, space-time trade-off, tractable and intractable, heuristic, the halting problem.