Theory of Computation | AQA A-Level Computer Science (7517)

Theory of Computation

195 questions
16 subtopics
Paper 1: the on-screen exam
Paper 1

Abstraction and decomposition, finite state machines, regular expressions, Backus-Naur Form, Big-O complexity, tractability, the Halting problem and Turing machines.

Examined on Paper 1.

Sample questions from Theory of Computation

Answer each one closed book first, then open the answer.

Logic Problems and Algorithm Constructs

Solve this logic problem and justify your answer: 'If a file is compressed then it is not encrypted. This file is encrypted.'

Show the answer
The file is not compressed. If it were compressed, the first statement would force it to be unencrypted, which contradicts the fact that it is encrypted. Ruling out the only alternative leaves 'not compressed' as the conclusion.
Pseudo-Code, Hand-Tracing and Program Correctness

Hand-trace this algorithm and give the output. total ← 0 FOR i ← 1 TO 4 total ← total + i * i ENDFOR OUTPUT total

Show the answer
The trace table runs: before the loop: total = 0 i = 1: total = 0 + 1 = 1 i = 2: total = 1 + 4 = 5 i = 3: total = 5 + 9 = 14 i = 4: total = 14 + 16 = 30 The output is 30, the sum of the squares 1 + 4 + 9 + 16.
Data Abstraction and Problem Reduction

What is data abstraction?

Show the answer
Data abstraction separates the way a compound data object is used from the way it is built. The details of how the data are actually represented are hidden, so fresh kinds of data object can be assembled out of ones already defined.
Automation and Finite State Machines

What is a Mealy machine?

Show the answer
A Mealy machine is a finite state machine with output in which each transition produces an output. The output depends on both the current state and the input symbol, so it is attached to the transition rather than to a state, and is written on the arrow as input/output.
Sets and Set Notation

Is the set of real numbers countable? Explain the significance of the answer.

Show the answer
No. The set of real numbers is not countable. However you try to list the reals, there will always be reals missing from the list, so they cannot be counted off by the natural numbers. This matters because it shows that not all infinite sets are the same size, and that there are more real numbers than there are natural numbers.
Subsets and Set Operations

Give the formal definition of the set difference A \ B.

Show the answer
A \ B = {x : x ∈ A and x ∉ B} — the set of all x such that x is a member of A and x is not a member of B. It is also written A − B.
Regular expressions and regular languages

Write a regular expression that matches both 'color' and 'colour' and nothing else, and explain the metacharacter you used.

Show the answer
colou?r. The ? applies to the u immediately before it and means 0 or 1 repetitions, so the u is optional: with it you get colour, without it color. No other string matches, because every other character is fixed.
Comparing Algorithms and Functions

What is an exponential function? Give an example with a table of values.

Show the answer
An exponential function has the variable in the exponent, for example y = 2ˣ. Values for y = 2ˣ: x = 1 gives 2, x = 2 gives 4, x = 3 gives 8, x = 4 gives 16, x = 5 gives 32. Each increase of 1 in x multiplies y by 2, so growth is by a constant factor per step rather than a constant amount.

The 16 subtopics

One subtopic is one session. Work down the list.

Subtopic	What it covers	Questions
Logic Problems and Algorithm Constructs	Recall questions on solving logic problems with Boolean expressions and checking them exhaustively, the definition of an algorithm, and sequence, assignment, selection and iteration.	13
Pseudo-Code, Hand-Tracing and Program Correctness	Recall questions on writing pseudo-code, hand-tracing algorithms and finding bugs, converting pseudo-code into program code, and arguing that a program is correct and efficient.	12
Representational Abstraction, Generalisation and Information Hiding	Recall questions on abstraction in computing, representational abstraction, abstraction by generalisation and its 'is a kind of' hierarchy, and information hiding with its benefits.	11
Procedural and Functional Abstraction	Recall questions on what procedural abstraction is, worked examples of values being abstracted away, and why the result is a procedure.	9
Data Abstraction and Problem Reduction	Recall questions on what data abstraction is, the stack as a worked example and how new data objects are built from existing ones.	8
Decomposition and Composition	Recall questions on what procedural decomposition is, how a problem is broken down, its benefits and what distinguishes a good decomposition.	8
Automation and Finite State Machines	Recall questions on what automation is and the four steps by which it is achieved, and on finite state machines with and without output.	18
Sets and Set Notation	Recall questions on what a set is, the two notations for specifying one, and the meaning of the symbols in a set comprehension.	16
Subsets and Set Operations	Recall questions on the difference between a subset and a proper subset, membership tests, and the four set operations.	8
Regular expressions and regular languages	Recall questions on the metacharacters , + , ? and \|, the difference between ab and (ab)*, and writing expressions for given sets of strings.	14
Backus-Naur Form and syntax diagrams	Recall questions on production rules, terminals against non-terminals, recursion in a rule, and why BNF describes languages regular expressions cannot.	12
Comparing Algorithms and Functions	Recall questions on how algorithms are compared, why problem size is the key issue, why timing is unreliable, and on functions and permutations.	20
Order of complexity and Big-O notation	Recall questions on constant, logarithmic, linear, polynomial and exponential growth, and on deriving an algorithm's complexity from its code.	15
Limits of computation, tractability and heuristics	Recall questions on tractable and intractable problems, why intractable does not mean impossible, and why heuristics are used when no efficient algorithm exists.	9
Computable problems and the Halting problem	Recall questions on the Halting problem, why it cannot be settled by simply running the program, and the difference between non-computable and merely intractable.	8
Turing machines	Recall questions on the tape, start and halting states, the transition function and its diagram, and hand-tracing a machine over a given input.	14

Theory of Computation is 195 of the 1,516 questions in the guide.Get the guide, £9

How the guide is worked

Answering a question from memory stores it far better than reading the answer again. The guide runs that as a fixed procedure on one subtopic at a time, about twenty minutes a session.

Step 1 · Closed book
Cover the answers. Work through one subtopic and write down what you can. Leave blanks where you have nothing.
Step 2 · Open book
Go back to the top. Read each printed answer and write it out in full, including the ones you had right.
Step 3 · Closed book again
Same questions, same order, from memory. The gap between pass one and pass three is the session result.

Read the full method, the return schedule and the research behind it.