Numbers
AQA A-Level Computer Science 7517
Fundamentals of Programming
Topic overviewData typesProgramming concepts and program structureArithmetic operationsRelational Operations, Constants and VariablesBoolean operationsString-handling operationsRandom numbers and exception handlingSubroutines, parameters and return valuesVariable scope and stack framesRecursive techniquesProgramming paradigms and the procedural approachClasses, Objects, Inheritance and PolymorphismAggregation, Composition, Class Diagrams and Design Principles
Fundamentals of Data Structures
Fundamentals of Algorithms
Theory of Computation
Topic overviewLogic Problems and Algorithm ConstructsPseudo-Code, Hand-Tracing and Program CorrectnessRepresentational Abstraction, Generalisation and Information HidingProcedural and Functional AbstractionData Abstraction and Problem ReductionDecomposition and CompositionAutomation and Finite State MachinesSets and Set NotationSubsets and Set OperationsRegular expressions and regular languagesBackus-Naur Form and syntax diagramsComparing Algorithms and FunctionsOrder of complexity and Big-O notationLimits of computation, tractability and heuristicsComputable problems and the Halting problemTuring machines
Fundamentals of Data Representation
Topic overviewNumber systems and the sets of numbersNumber bases: decimal, binary and hexadecimalBits, bytes and units of informationUnsigned binary and binary arithmeticSigned binary using two's complementFixed point and floating point representationNormalisation of floating point numbersRounding errors, accuracy, range and precisionCharacter coding systemsError checking and correctionBit patterns, analogue and digitalBitmapped graphicsVector graphicsDigital representation of soundMIDI and Data CompressionEncryption
Fundamentals of Computer Systems
Topic overviewHardware, Software and Its ClassificationSystem Software and the Operating SystemTranslators and the Role of the Operating SystemClassification of programming languagesTypes of program translatorLogic Gates and Their Truth TablesLogic Circuits and D-Type Flip-FlopsHalf-Adders and Full AddersBoolean algebra
Fundamentals of Computer Organisation and Architecture
Topic overviewInternal components, buses and von Neumann and Harvard architecturesThe Stored Program Concept and the ProcessorThe Fetch-Execute cycleThe processor instruction setAddressing modesMachine-Code OperationsShifts, Halting and Assembly Language ProgramsInterruptsFactors affecting processor performanceInput and output devicesSecondary storage devices
Fundamentals of Communication and Networking
Topic overviewCommunication methodsCommunication basicsNetwork Topology and Types of NetworkingWireless networkingThe Internet and Packet SwitchingRouting, URLs and Domain NamesFirewalls, Worms, Trojans and VirusesEncryption, Digital Signatures and CertificatesTCP/IPStandard application layer protocolsIP Address Structure and Subnet MaskingIP Standards and Public and Private AddressesDHCP and Network Address TranslationClient server modelThin- versus thick-client computing
Consequences of Uses of Computing
Systematic Approach to Problem Solving
Fundamentals of Databases
Big Data
Theory of Computation
- 16 subtopics
- 33 things to know
- Paper 1
What Theory of Computation covers
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.
Where it is assessed
Paper 1
The on-screen programming exam, 2 hours 30 minutes and 40% of the A-level.
Check the AQA specification ↗The 16 subtopics
Each one has its own page.
- Logic Problems and Algorithm ConstructsRecall questions on solving logic problems with Boolean expressions and checking them exhaustively, the definition of an algorithm, and sequence, assignment, selection and iteration.Open →
- Pseudo-Code, Hand-Tracing and Program CorrectnessRecall 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.Open →
- Representational Abstraction, Generalisation and Information HidingRecall questions on abstraction in computing, representational abstraction, abstraction by generalisation and its 'is a kind of' hierarchy, and information hiding with its benefits.Open →
- Procedural and Functional AbstractionRecall questions on what procedural abstraction is, worked examples of values being abstracted away, and why the result is a procedure.Open →
- Data Abstraction and Problem ReductionRecall questions on what data abstraction is, the stack as a worked example and how new data objects are built from existing ones.Open →
- Decomposition and CompositionRecall questions on what procedural decomposition is, how a problem is broken down, its benefits and what distinguishes a good decomposition.Open →
- Automation and Finite State MachinesRecall questions on what automation is and the four steps by which it is achieved, and on finite state machines with and without output.Open →
- Sets and Set NotationRecall questions on what a set is, the two notations for specifying one, and the meaning of the symbols in a set comprehension.Open →
- Subsets and Set OperationsRecall questions on the difference between a subset and a proper subset, membership tests, and the four set operations.Open →
- Regular expressions and regular languagesRecall questions on the metacharacters *, + , ? and |, the difference between ab* and (ab)*, and writing expressions for given sets of strings.Open →
- Backus-Naur Form and syntax diagramsRecall questions on production rules, terminals against non-terminals, recursion in a rule, and why BNF describes languages regular expressions cannot.Open →
- Comparing Algorithms and FunctionsRecall questions on how algorithms are compared, why problem size is the key issue, why timing is unreliable, and on functions and permutations.Open →
- Order of complexity and Big-O notationRecall questions on constant, logarithmic, linear, polynomial and exponential growth, and on deriving an algorithm's complexity from its code.Open →
- Limits of computation, tractability and heuristicsRecall questions on tractable and intractable problems, why intractable does not mean impossible, and why heuristics are used when no efficient algorithm exists.Open →
- Computable problems and the Halting problemRecall questions on the Halting problem, why it cannot be settled by simply running the program, and the difference between non-computable and merely intractable.Open →
- Turing machinesRecall questions on the tape, start and halting states, the transition function and its diagram, and hand-tracing a machine over a given input.Open →
What you need to know
Answer each one before you reveal it.
Your recallNot started
Process
Define the term algorithm.
Numbers
Why can testing never prove that a program is correct, and what does that mean for the argument you make?
Key term
Give a worked example of representational abstraction and say exactly what was removed and what was kept.
Process
Distinguish representational abstraction from abstraction by generalisation.
Key term
How is information hiding related to abstraction?
Key term
What is procedural abstraction?
Key term
Why is a function easier to reason about than a procedure?
Evaluation
Why does data abstraction let a stack's representation be changed safely?
Process
Give a worked example of a real problem being reduced to one that is already solved.
Evaluation
State three benefits of decomposing a problem before writing any code.
Key term
Give three examples of compound data objects built from previously defined types.
Process
Why is creating algorithms the first step in automating a model?
Key term
Describe how a state transition diagram is drawn, so that someone could reconstruct one on paper.
Key term
Describe a Mealy machine that outputs a 1 each time it has just read two 1s in a row, and 0 otherwise.
Key term
Is {Ø} the same as Ø?
Key term
Is the set of real numbers countable? Explain the significance of the answer.
Key term
Give the formal definition of the set difference A \ B.
Key term
Write a regular expression that matches both 'color' and 'colour' and nothing else, and explain the metacharacter you used.
Key term
Describe the relationship between regular expressions and finite state machines.
Key term
Using the rule <unsigned integer> ::= <digit> | <digit><unsigned integer>, check whether 407 is a valid unsigned integer, showing each step.
Key term
Describe how a syntax diagram is drawn and how you use it to check a string.
Evaluation
Why is the size of the problem the key issue when comparing algorithms?
Key term
Distinguish clearly between the domain and the co-domain of a function.
Process
What is the crucial difference between y = 2x² and y = 2ˣ?
Key term
What does constant time mean, and give two examples?
Process
Derive the complexity of this algorithm. count ← 0 WHILE n > 1 n ← n DIV 2 count ← count + 1 ENDWHILE.
Process
Why does a faster computer not solve the problem of intractability?
Key term
Why are heuristic methods often used when tackling intractable problems?
Process
Distinguish a non-computable problem from an intractable one.
Process
A student says 'the Halting problem just means the test would take too long'. Correct them.
Process
How does a transition function relate to a state transition diagram?
Key term
What happens if a Turing machine is in a state and reads a symbol for which the transition function has no rule?
Take Theory of Computation further
The same content, four other ways.
Commonly confused
Pairs that lose marks when they are blurred together.
Terminal symbol vs Non-terminal symbol
Terminal symbol: a grammar symbol that can appear in the finished string. Non-terminal symbol: a grammar symbol replaced by production rules.
Finite state automaton vs Mealy machine
Finite state automaton: a state machine that only accepts or rejects input. Mealy machine: a state machine producing output on transitions.
Polynomial time vs Exponential time
Polynomial time: growth bounded by a fixed power of input size. Exponential time: growth multiplying by a fixed factor when input size increases.
Questions from this topic
Each one with the model answer underneath.
- 1
A door lock must open only when at least two of its three sensors A, B and C are triggered. Develop a Boolean expression for the OPEN signal and explain how you arrived at it.
Model answer
OPEN = (A AND B) OR (A AND C) OR (B AND C). Work through the cases: 'at least two of three' is satisfied by exactly the three possible pairs, so write one AND term for each pair and OR the terms together. The all-three case needs no extra term because if A, B and C are all triggered then (A AND B) is already true, which makes the whole OR true.
- 2
How would you check that door-lock expression is correct, and why is trying one set of inputs not enough?
Model answer
Build a truth table with a row for every combination of inputs. Three inputs give 2³ = 8 rows. Evaluate the expression in each row and compare the result with what the problem demands: it must be 0 for the four rows 000, 100, 010 and 001 (fewer than two sensors triggered) and 1 for the four rows 110, 101, 011 and 111. One test is not enough because a mistake in a single AND term still leaves most rows correct; only checking every case, or giving a logical argument that covers every case, shows the solution is right.
- 3
An alarm should sound when the window sensor W reports open AND the system is armed R, but never while the engineer's override O is on. Give the Boolean expression and say what happens when W = 1, R = 1 and O = 1.
Model answer
ALARM = W AND R AND NOT O. With W = 1, R = 1 and O = 1, NOT O = 0, so the three-way AND evaluates to 0 and the alarm stays silent. The override wins, which is exactly what the problem asked for. Note that 'but never while' in the English statement becomes AND NOT, not OR NOT.
- 4
A student claims that NOT (A AND B) is the same as (NOT A) AND (NOT B). Show that this is wrong.
Model answer
Take A = 1 and B = 0. NOT (A AND B) = NOT 0 = 1, but (NOT A) AND (NOT B) = 0 AND 1 = 0. The two sides differ, so the claim is false. A single counter-example is enough to disprove a claim that two expressions are equivalent. The correct equivalent is NOT (A AND B) = (NOT A) OR (NOT B).
- 5
Solve this logic problem and justify your answer: 'If a file is compressed then it is not encrypted. This file is encrypted.'
Model 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.
- 6
Why is it worth rewriting a logic problem using single letters and Boolean operators before trying to solve it?
Model answer
Ordinary English is ambiguous about logic. 'Or' may mean one or the other or both, or it may mean exactly one; 'unless' can mean AND NOT; 'and' in a list can hide an implied OR. Replacing each condition with a named variable and writing the requirement with AND, OR and NOT fixes one meaning, makes the number of input combinations obvious (n conditions give 2ⁿ cases to check), and lets you test the solution mechanically with a truth table instead of by re-reading the prose.
What is inside Levo
Six ways to work the same material.
Theory of Computation revision questions
- What does Theory of Computation cover in AQA A-Level Computer Science?
- 16 subtopics: logic problems and algorithm constructs, pseudo-code, hand-tracing and program correctness, representational abstraction, generalisation and information hiding, procedural and functional abstraction, data abstraction and problem reduction, decomposition and composition, automation and finite state machines, sets and set notation, subsets and set operations, regular expressions and regular languages, backus-naur form and syntax diagrams, comparing algorithms and functions, order of complexity and big-o notation, limits of computation, tractability and heuristics, computable problems and the halting problem and turing machines. Each one has its own page with questions and model answers.
- How is Theory of Computation organised?
- By the AQA 7517 specification, subtopic by subtopic, so it matches the order you are taught it in.
Every question in Theory of Computation, on a schedule.
Attempt a question from memory, write the correct version, then attempt it again. Levo records the jump between your first attempt and your last, and brings each question back on the day you are due to forget it.
Or £46 a year, about £3.83 a month. Cancel anytime.