A Level Computer Science Essentials includes Structure and Function of the Processor (Component 1: Computer Systems); Types of Software and Development Methodologies (Component 1: Computer Systems); Exchanging Data: Databases, Networks and Web Technologies (Component 1: Computer Systems); Data Types, Data Structures and Boolean Algebra (Component 1: Computer Systems); Legal, Moral, Cultural and Ethical Issues (Component 1: Computer Systems); Computer Architecture, Assembly and the LMC (Component 1: Computer Systems); Boolean Algebra, Logic Gates and Karnaugh Maps (Component 1: Computer Systems); Databases, SQL and Normalisation (Component 1: Computer Systems); Databases and SQL (Component 1: Computer Systems); Networking and the Internet (Component 1: Computer Systems); Object-Oriented Programming (Component 2: Algorithms and Programming); Recursion and Advanced Algorithms (Component 2: Algorithms and Programming); Elements of Computational Thinking (Component 2: Algorithms and Programming); Problem Solving and Programming (Component 2: Algorithms and Programming); Algorithms: Complexity, Searching and Sorting (Component 2: Algorithms and Programming); Programming Paradigms and OOP (Component 2: Algorithms and Programming); Data Structures and Their Operations (Component 2: Algorithms and Programming); Advanced Algorithms: Searching, Sorting and Path-Finding (Component 2: Algorithms and Programming); Data Representation and Theory of Computation (Component 2: Algorithms and Programming).
Method recap - Data Representation and Theory of Computation
- Recall that all data, including negative numbers via two's complement and real numbers via a normalised mantissa and exponent, is ultimately stored as binary patterns, then extend this to how text and symbols are represented.
- Distinguish ASCII, a fixed 7-bit code giving 128 characters stored one byte each, from Unicode, a much larger set of code points intended to cover every written language; recall that UTF-8 stores each Unicode code point using between 1 and 4 bytes, and stays backward compatible with ASCII for the first 128 code points.
- Reason about the range/precision trade-off in a floating point representation: for a fixed total number of bits, allocating more bits to the exponent widens the range of representable magnitudes, while allocating more bits to the mantissa improves precision.
- For a finite state machine (FSM) question, identify the states, the start state, any accepting (final) states, and the transition for every state/input pair, then trace the given input string one symbol at a time to find which state the machine finishes in.
Worked example - Data Representation and Theory of Computation
A text file contains the string 'CAT' followed by a single Euro sign character (Unicode code point U+20AC). Standard ASCII characters are stored using 1 byte each in UTF-8, and the Euro sign requires 3 bytes in UTF-8. Calculate the total file size in bytes for this string, ignoring any file header.
- Identify that 'CAT' consists of 3 characters, each within the basic ASCII range, so each takes 1 byte in UTF-8: 3 x 1 = 3 bytes.
- Identify that the Euro sign (U+20AC) falls outside the ASCII range, so UTF-8 encodes it using 3 bytes, as given.
- Add the two parts together: 3 bytes (for CAT) + 3 bytes (for the Euro sign).
- Calculate the result: 3 + 3 = 6.
- Final answer: the string requires 6 bytes in total when stored using UTF-8.
Question 11 - Data Representation and Theory of Computation
9 marks
Discuss the statement 'any problem that can be described precisely can be solved by a computer program', with reference to the halting problem and the idea of an undecidable problem.
Answer and mark scheme
Mark scheme for Question 11 [9 marks]| Question 11[9 marks] |
|---|
| Answer or working | Marks |
|---|
| A well-structured discussion that explains the general idea of computability, uses the halting problem accurately as a specific example of an undecidable problem, and reaches a supported conclusion about the statement. | Level 37-9 marks |
| Explains relevant ideas about computability and/or the halting problem with some accuracy, but the discussion is less developed, or the link between the example and the general statement is not fully made. | Level 24-6 marks |
| Basic, undeveloped statements about computers, algorithms or problems, with limited or no reference to computability. | Level 11-3 marks |
| No creditable content. | 0 |
| the statement is false, because not every precisely described problem is decidable; a decidable problem is one for which an algorithm exists that is guaranteed to halt and give a correct answer for every input; | |
| the halting problem is a well known example: given an arbitrary program and its input, decide whether that program will eventually halt or run forever; | |
| it has been proven, by Alan Turing, that no general algorithm can exist that correctly solves the halting problem for every possible program and input, which makes it undecidable; | |
| this shows that a precise, well-defined description of a problem is not enough on its own to guarantee it is solvable by a computer program, since some precisely defined problems are provably undecidable; | |
| a candidate might note that most everyday programming problems are decidable, and undecidability mainly affects certain classes of self-referential or general questions about program behaviour; | |
| judgement: the statement is false as a general claim; computability theory shows there exist precisely defined problems, such as the halting problem, for which no algorithm can ever exist. | |
Question 9 - Data Representation and Theory of Computation
4 marks
A short message consists of 10 ASCII characters and 2 Chinese characters. Each ASCII character is stored using 1 byte in UTF-8, and each Chinese character requires 3 bytes in UTF-8. Calculate the total number of bytes needed to store this message.
Answer and mark scheme
Mark scheme for Question 9 [4 marks]| Question 9[4 marks] |
|---|
| Answer or working | Marks |
|---|
| Calculates the bytes needed for the ASCII characters: 10 x 1 = 10 bytes. | 1 |
| Calculates the bytes needed for the Chinese characters: 2 x 3 = 6 bytes. | 1 |
| Uses the correct method of adding the two parts together. | 1 |
| Final answer: 16 bytes. | 1 |
Method recap - Structure and Function of the Processor
- Learn the roles of the control unit (CU), arithmetic logic unit (ALU) and registers (PC, MAR, MDR, CIR, ACC) before trying to trace any cycle.
- Write out the fetch stage in register transfer notation: MAR <- [PC], PC <- [PC]+1, MDR <- [[MAR]], CIR <- [MDR].
- Apply the decode stage: the CU interprets the opcode held in the CIR and generates the control signals needed for execute.
- Work through the execute stage for the specific instruction (e.g. LDD, ADD, STO), updating the ACC or memory as required.
Question 9 - Structure and Function of the Processor
5 marks
Describe what is meant by cache memory, and explain how the principle of temporal locality helps a cache improve processor performance.
Answer and mark scheme
Mark scheme for Question 9 [5 marks]| Question 9[5 marks] |
|---|
| Answer or working | Marks |
|---|
| States that cache is a small block of very fast memory located closer to (or within) the CPU than main memory (RAM). | 1 |
| States that cache stores copies of frequently or recently used instructions/data so they do not need to be re-fetched from slower RAM. | 1 |
| Defines temporal locality as the tendency for a recently accessed memory location to be accessed again soon. | 1 |
| Explains that because of this, keeping a fetched value in cache means later repeat accesses can be served much faster than fetching from RAM again. | 1 |
| Final answer: this reduces the average time the processor spends waiting for data, improving overall performance. | 1 |
Question 7 - Structure and Function of the Processor
3 marks
Explain what is meant by the 'fetch-decode-execute cycle', referring to the role of the Program Counter in your answer.
Answer and mark scheme
Mark scheme for Question 7 [3 marks]| Question 7[3 marks] |
|---|
| Answer or working | Marks |
|---|
| States that the processor repeatedly fetches an instruction from memory, decodes it, then executes it. | 1 |
| States that the Program Counter (PC) holds the address of the next instruction to be fetched. | 1 |
| States that the PC is normally incremented after each fetch so it points to the next instruction in sequence. | 1 |