Paper 1

Fundamentals of Programming

189 questions in the guide, across 13 subtopics. More from this topic

1. Data types

   Describe the Boolean data type.

   Show the answer

   A type with exactly two possible values, True and False. It is what a relational or logical expression evaluates to, and it is used to control selection and iteration. Logically it needs only a single bit, although a language will usually reserve a whole byte for it.

2. Programming concepts and program structure

   Describe an iterative structure with the condition at the start, and say how many times its body can run.

   Show the answer

   The condition is tested before the body is entered, and the body runs only while the condition holds, as in WHILE...ENDWHILE. Because the test comes first, the body may run zero times: if the condition is already False when the loop is reached, the body is skipped entirely.

3. Relational Operations, Constants and Variables

   How do you test that a mark is at least 40 but no more than 69?

   Show the answer

   mark >= 40 AND mark <= 69. 'At least' maps to greater than or equal to, and 'no more than' maps to less than or equal to; using the strict < and > operators here would wrongly exclude the boundary values 40 and 69.

4. Boolean operations

   How would you write a condition that is True when a number n is NOT between 10 and 20 inclusive?

   Show the answer

   Either NOT (n >= 10 AND n <= 20), or the equivalent form n < 10 OR n > 20. Note that the negation turns the AND into an OR and reverses each comparison; writing n < 10 AND n > 20 is a common error and can never be True.

5. Random numbers and exception handling

   Why are the random numbers a program produces described as pseudo-random?

   Show the answer

   Because they are produced by a deterministic algorithm from a starting value called the seed, not by a genuinely unpredictable physical process. The sequence passes statistical tests for randomness and is unpredictable in practice, but it is entirely determined by the seed and will eventually repeat.

Paper 1

Fundamentals of Data Structures

136 questions in the guide, across 11 subtopics. More from this topic

1. Data Structures and Abstract Data Types

   Define an n-dimensional array.

   Show the answer

   An n-dimensional array holds elements that all share a single data type, and each element is picked out by a tuple of n integers — one index per dimension. A 2-dimensional array is therefore addressed by pairs such as (3, 5); adding a third dimension means every element needs a triple, and so on for higher n.

2. Static and Dynamic Data Structures

   What is a dynamic data structure?

   Show the answer

   A data structure that can grow and shrink while the program is running, requesting memory from the heap as new items are added and releasing it as items are removed, so its size is not fixed in advance. A linked list is the usual example.

3. Queues and Linear Queues

   Give four typical uses of a queue.

   Show the answer

   A print spooler holding documents waiting for a printer; a buffer holding keystrokes or data waiting to be processed; the ready queue of processes waiting for the processor in an operating system; and the queue of vertices still to be visited in a breadth-first search.

4. Circular and Priority Queues

   Describe how an item is added to a circular queue.

   Show the answer

   First test whether the queue is full; if it is, report overflow. Otherwise set rear = (rear + 1) MOD maxSize, store the new item at that position, and increase the size counter by one. The MOD operation makes the rear pointer wrap round to 0 after the last index.

5. Stacks

   Describe the pop operation.

   Show the answer

   Pop removes the item at the top of the stack and returns it. First test whether the stack is empty; if it is, report stack underflow and do not remove. Otherwise take the item at the position given by the top pointer, then decrease the top pointer by one so that it points at the item beneath.

Paper 1

Fundamentals of Algorithms

82 questions in the guide, across 6 subtopics. More from this topic

1. Graph traversal

   Using the same graph — vertices A to F with edges A-B, A-C, B-D, C-E, D-F and E-F — give the depth-first traversal from A, taking neighbours in alphabetical order.

   Show the answer

   A, B, D, F, E, C. From A the first unvisited neighbour is B, from B it is D, from D it is F, from F the unvisited neighbour is E, and from E it is C. C has no unvisited neighbours, so the search backtracks all the way, popping E, F, D, B and A in turn, and finishes.

2. Graph traversal

   Give the typical application of breadth-first search.

   Show the answer

   Finding the shortest path in an unweighted graph. Because breadth-first search explores outwards in layers, the first time it reaches a vertex it has done so using the fewest possible edges, so the path it found is the shortest one.

3. Tree traversal

   Describe the post-order traversal algorithm.

   Show the answer

   Starting at the root: apply the procedure recursively to the left subtree, then apply it recursively to the right subtree, and only then output the value at the current node. If a subtree is empty, nothing is done for it and the algorithm returns.

4. Tree traversal

   For the same tree — root A, children B and C; B has children D and E; C has right child F — give the post-order traversal.

   Show the answer

   D, E, B, F, C, A. The left subtree rooted at B gives D, E, B; the right subtree rooted at C gives F, C; and the root A is output last.

5. Reverse Polish notation

   Convert (3 + 4) * 5 to Reverse Polish notation.

   Show the answer

   3 4 + 5 *. The bracketed subexpression 3 + 4 becomes 3 4 +, and that result is then multiplied by 5, so the operands 3 4 + and 5 are followed by the operator *.

Paper 1

Theory of Computation

195 questions in the guide, across 16 subtopics. More from this topic

1. 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.

2. 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.

3. 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.

4. 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.

5. 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.

Paper 2

Fundamentals of Data Representation

240 questions in the guide, across 16 subtopics. More from this topic

1. Number systems and the sets of numbers

   Explain why every integer is also a rational number.

   Show the answer

   Any integer can be written as a fraction with a denominator of 1. For example 7 = 7/1 and −3 = −3/1. Since both parts are integers and the denominator is not zero, the number satisfies the definition of a rational number, so ℤ is a subset of ℚ.

2. Number bases: decimal, binary and hexadecimal

   Describe the repeated division method for converting a decimal number to binary.

   Show the answer

   Divide the number by 2 and write down the remainder, which is 0 or 1. Divide the quotient by 2 and write down the next remainder. Keep going until the quotient is 0, then read the remainders from the last one written back to the first — that string of remainders is the binary number.

3. Unsigned binary and binary arithmetic

   Convert 181₁₀ to an 8-bit unsigned binary number.

   Show the answer

   10110101₂. Work down the place values: 181 − 128 = 53, 53 − 32 = 21, 21 − 16 = 5, 5 − 4 = 1, 1 − 1 = 0, so there is a 1 in the 128, 32, 16, 4 and 1 columns and a 0 in the 64, 8 and 2 columns.

4. Signed binary using two's complement

   Write −1 and −128 as 8-bit two's complement numbers.

   Show the answer

   −1 is 11111111: inverting 00000001 gives 11111110 and adding 1 gives 11111111, and the place values sum to −128 + 127 = −1. −128 is 10000000, the most negative value, whose only set bit carries the weight −128.

5. Normalisation of floating point numbers

   State the test for whether a mantissa is normalised, for both signs.

   Show the answer

   The first two bits of the mantissa must differ. A positive normalised mantissa begins 0.1, and a negative normalised mantissa begins 1.0. If the first two bits are the same — 0.0 or 1.1 — the number is not normalised and the mantissa can be shifted further left.

Paper 2

Fundamentals of Computer Systems

114 questions in the guide, across 9 subtopics. More from this topic

1. Hardware, Software and Its Classification

   Is firmware hardware or software, and why is it easy to confuse the two?

   Show the answer

   Firmware is software: it is a program, held permanently in read-only or flash memory on a hardware component. It is confused with hardware because it is supplied inside the physical device and is not normally changed by the user, but it is still a set of instructions rather than a physical part.

2. Hardware, Software and Its Classification

   Classify each of these as system or application software: a spreadsheet, a disk defragmenter, a compiler, a web browser, an operating system, a graphics library.

   Show the answer

   Application: the spreadsheet and the web browser. System: the disk defragmenter (a utility), the compiler (a translator), the operating system and the graphics library.

3. System Software and the Operating System

   Understand the need for utility programs: what are they for?

   Show the answer

   Utility programs are needed to maintain, optimise, protect and repair the computer system: housekeeping jobs that the operating system does not do as part of ordinary running, but that keep the machine healthy and its data safe.

4. System Software and the Operating System

   What is a translator?

   Show the answer

   A translator is a program that converts a program written in one language into an equivalent program in another language, normally converting source code written by a human into machine code the processor can execute. The three kinds are the assembler, the compiler and the interpreter.

5. Translators and the Role of the Operating System

   Give the function of a compiler in one sentence.

   Show the answer

   A compiler translates a complete high-level language program into machine code (or an intermediate code) in one operation before it is run, producing a separate file that can then be executed on its own.

Paper 2

Fundamentals of Computer Organisation and Architecture

133 questions in the guide, across 11 subtopics. More from this topic

1. Internal components, buses and von Neumann and Harvard architectures

   Name the basic internal components of a computer system.

   Show the answer

   The processor, main memory, the address bus, the data bus, the control bus, and the input/output controllers that connect peripherals to the system. All of these are mounted on or attached to the motherboard, and the buses are the wires that carry signals between the rest.

2. The Stored Program Concept and the Processor

   Name the major components of a processor.

   Show the answer

   The arithmetic logic unit, the control unit, the clock, a set of general-purpose registers, and the dedicated registers: the program counter, the current instruction register, the memory address register, the memory buffer register and the status register. The buses inside the processor connect them.

3. The Fetch-Execute cycle

   Name the three stages of the Fetch-Execute cycle and say in one line what each does.

   Show the answer

   Fetch: the next instruction is copied from main memory into the processor. Decode: the control unit works out from the opcode what operation is required and in which addressing mode. Execute: the operation is carried out. The cycle then repeats, continuously, for as long as the processor is running.

4. The processor instruction set

   What are the two parts of a machine code instruction?

   Show the answer

   The opcode and one or more operands. The opcode says which operation is to be carried out. The operand supplies what it is to be carried out on, and may be a value, a memory address or a register.

5. Addressing modes

   Which two addressing modes are used here, and what does an addressing mode mean?

   Show the answer

   Immediate addressing and direct addressing. An addressing mode is the rule for how the operand of an instruction is to be interpreted, that is, how the processor works out from the operand bits where the actual datum it must use is to be found.

Paper 2

Fundamentals of Communication and Networking

204 questions in the guide, across 15 subtopics. More from this topic

1. Communication methods

   Define parallel transmission.

   Show the answer

   Parallel transmission sends several bits at the same time, each bit travelling down its own separate wire in a multi-wire link. A group of bits (for example eight) is therefore transmitted simultaneously rather than one after another.

2. Communication basics

   Define latency.

   Show the answer

   Latency is the time delay between the moment a signal or data is sent and the moment it arrives or is acted upon at the destination. It is measured in units of time, usually milliseconds.

3. Network Topology and Types of Networking

   What happens to performance on a logical bus as more devices are added, and why?

   Show the answer

   Performance falls. All the devices share one channel, so the available capacity is divided between them, and as more of them try to transmit the chance of two transmitting at the same time rises. More time is then spent waiting and retransmitting rather than sending useful data.

4. The Internet and Packet Switching

   Define router.

   Show the answer

   A router is a device that connects networks together and forwards packets between them, choosing the best route for each packet towards its destination using the destination IP address and its routing table. It joins networks that use the same protocol, for example connecting a home or office network to the Internet.

5. Encryption, Digital Signatures and Certificates

   Why can Ali not simply encrypt a confidential message with his own private key?

   Show the answer

   Because anything encrypted with his private key can be decrypted with his public key, and his public key is available to everyone. That would provide no confidentiality at all. Encrypting with the private key proves who sent the message; encrypting with the recipient's public key is what keeps it secret.

Paper 2

Consequences of Uses of Computing

26 questions in the guide, across 2 subtopics. More from this topic

Non-exam assessment

Systematic Approach to Problem Solving

24 questions in the guide, across 2 subtopics. More from this topic

1. Analysis, Design and Implementation

   Name the five stages of a systematic approach to solving a problem with software, in order.

   Show the answer

   Analysis, design, implementation, testing and evaluation. They are presented in that order, but in practice work often returns to an earlier stage — particularly design and implementation, which may be repeated in cycles.

Paper 2

Fundamentals of Databases

69 questions in the guide, across 5 subtopics. More from this topic

1. Conceptual data models and entity relationship modelling

   In what form is an entity description written?

   Show the answer

   As the entity name followed by its attributes in brackets, separated by commas: Entity1(Attribute1, Attribute2, ...). For example Book(ISBN, Title, AuthorID, Publisher, YearPublished).

2. Relational databases

   Define the term attribute.

   Show the answer

   An attribute is a named characteristic or property of an entity — one item of data recorded about it, such as Surname or DateOfBirth. In an implemented relational database an attribute corresponds to a column of a table, and every row has one atomic value for it.

3. Database design and normalisation techniques

   What must be true for a relation to be in third normal form?

   Show the answer

   It must already be in second normal form, and it must contain no transitive dependencies — no non-key attribute may depend on another non-key attribute. Every non-key attribute must be determined by the primary key directly, and not by way of some other ordinary attribute.

4. Structured Query Language (SQL)

   Write SQL to delete all loan records that were returned before 1 January 2020, from Loan(LoanID, BookID, MemberID, DateOut, DateReturned).

   Show the answer

   DELETE FROM Loan WHERE DateReturned < '2020-01-01'; DELETE FROM names the table and WHERE selects which records go. Note that DELETE removes whole records only — there is no way to delete a single attribute value with it; setting one attribute to nothing is an UPDATE.

5. Client server databases

   Name the four methods used to manage the problem of concurrent access.

   Show the answer

   Record locks, serialisation, timestamp ordering and commitment ordering.

Paper 2

Big Data

42 questions in the guide, across 4 subtopics. More from this topic

Paper 2

Fundamentals of Functional Programming

62 questions in the guide, across 4 subtopics. More from this topic

1. Function Types, First-Class Objects and Function Application

   Give the function type of a function that takes a character and returns whether it is a vowel, and identify the domain and co-domain.

   Show the answer

   isVowel: character → boolean. The domain is the set of characters, or a stated subset such as the lower-case letters; the co-domain is the set {True, False}. Here both members of the co-domain do occur as outputs, but that is a fact about this particular function and not a requirement of the notation.

2. Partial Function Application and Composition

   With f(x) = x + 2 and g(y) = y³ as before, what is f ○ g, and what does the comparison show?

   Show the answer

   f ○ g = x³ + 2, because g is applied first, cubing the input, and then f adds 2 to that result. It is not the same function as g ○ f = (x + 2)³: with an input of 1, f ○ g gives 3 while g ○ f gives 27. This shows that composition of functions is not commutative in general, so the order in which the functions are written matters.

3. Writing functional programs

   Give an example of filter applied to a list, showing the result.

   Show the answer

   Filtering the list [4, 7, 10, 13, 16] with the condition 'is even' gives [4, 10, 16]. In Haskell this is written filter even [4, 7, 10, 13, 16], which evaluates to [4, 10, 16]. The elements kept are unchanged and remain in their original order; only the ones failing the condition are absent.

4. Lists in functional programming

   Can a list be empty, and how is the empty list written?

   Show the answer

   Yes, a list can be empty. In Haskell the empty list is written []. It is a perfectly good list; it simply has no elements, so it has no head and no tail. It is what remains after the last element has been removed, and it is the value a construction of a list starts from.