2025 Cambridge IAL Computer Science (9618) Practice Paper with Answers

Convert the denary value \(-11.625\) into an 8-bit signed two's complement fixed-point binary format, where 5 bits are allocated for the integer part (including the sign bit) and 3 bits are allocated for the fractional part. Show your working.

An unnormalised database table `UNNORMALISED_ATHLETE` is defined as follows:
`UNNORMALISED_ATHLETE(AthleteID, AthleteName, HouseColor, EventID, EventName, EventCategory, Score)`
with a composite primary key of `(AthleteID, EventID)`.

1. Explain why this table is not in Second Normal Form (2NF).
2. Design a set of Third Normal Form (3NF) relational schemas for this database. Use the notation: `TableName(Attribute1, Attribute2, ...)` and underline the primary keys.

An assembly language program consists of the following consecutive instructions:
```
LDD 200
ADD 201
STO 202
LDI 202
```

Describe the complete execution sequence of these four instructions, including how addressing modes (Direct and Indirect) affect the operands and the Accumulator (ACC). The memory currently contains:
- Address 200: Value 15
- Address 201: Value 32
- Address 202: Value 200

An IPv4 address is specified using Classless Inter-Domain Routing (CIDR) notation as `192.168.4.135/26`.

1. Represent the subnet mask in dotted decimal notation.
2. Calculate the network address for this subnet. Show your binary working for the final octet.

State three differences between the way a compiler and an interpreter translate and execute program code. Explain which of these language translators is more suitable during the development phase of a software application.

A secure file transfer system must send a sensitive document over an insecure network. Describe how asymmetric encryption and digital signatures are applied together to guarantee both data confidentiality and authenticity of the sender.

Compare the licensing conditions of open-source software and shareware. In your answer, address access to the source code, pricing structures, and rights of modification.

A student has written the following pseudocode algorithm to sort a small list of numbers.

```pseudocode
PROCEDURE ProcessArray(BYREF Arr : ARRAY OF INTEGER, Size : INTEGER)
DECLARE i, Temp : INTEGER
i <- 1
WHILE i < Size
IF Arr[i] > Arr[i+1] THEN
Temp <- Arr[i]
Arr[i] <- Arr[i+1]
Arr[i+1] <- Temp
IF i > 1 THEN
i <- i - 1
ELSE
i <- i + 1
ENDIF
ELSE
i <- i + 1
ENDIF
ENDWHILE
ENDPROCEDURE
```

Trace the execution of this procedure when called as follows:

```pseudocode
DECLARE TestArray : ARRAY[1:4] OF INTEGER
TestArray[1] <- 4
TestArray[2] <- 2
TestArray[3] <- 7
TestArray[4] <- 1
ProcessArray(TestArray, 4)
```

Complete the trace table showing how the values of the variables and array elements change during execution. Enter a new row whenever a variable or array element is modified.

Write pseudocode for a function `ExtractDomain() RETURNS INTEGER` that reads email addresses from an existing text file named `emails.txt`.

Each line of the file contains a single email address. The function must extract the domain name (the part of the email address following the `'@'` symbol) for each valid email.

An email address is considered valid for extraction only if:
1. It contains exactly one `'@'` character.
2. The `'@'` character is neither the first nor the last character of the email address.

The function must write unique valid domain names to a new text file named `domains.txt`. To do this, use a local 1D array `UniqueDomains` of size 100 of type `STRING` to keep track of domain names already written to `domains.txt`.

The function must:
- Open both files with appropriate modes.
- Process the input file line-by-line until the end of the file is reached.
- Perform validation checks on each email address.
- Ensure that no duplicate domain names are written to `domains.txt`.
- Count the total number of unique valid domains found and written.
- Close both files and return the count.

You can assume standard string functions are available:
- `LENGTH(StringVal : STRING) RETURNS INTEGER`
- `MID(StringVal : STRING, Start : INTEGER, Length : INTEGER) RETURNS STRING`

A circular queue is implemented using a 1D array and three global variables:
- `QueueArray : ARRAY[1:8] OF STRING`
- `FrontPointer : INTEGER` (points to the index of the first element in the queue)
- `RearPointer : INTEGER` (points to the index of the last element in the queue)
- `QueueLength : INTEGER` (stores the current number of elements in the queue)

Initially, the queue is empty. `FrontPointer` is initialized to 1, `RearPointer` is initialized to 0, and `QueueLength` is initialized to 0.

Write the pseudocode for a function `Enqueue(NewItem : STRING) RETURNS BOOLEAN` which:
- Checks if the queue is full. If the queue is full, it must not add the item and must return `FALSE`.
- Updates `RearPointer` to the next logical index in the circular array.
- Inserts `NewItem` at the new `RearPointer` position.
- Increments `QueueLength`.
- Returns `TRUE` to indicate a successful insertion.

Do not use any other global variables. Ensure that the circular nature of the queue is correctly handled.

The recursive function `Mystery` is defined as follows:

```pseudocode
FUNCTION Mystery(n : INTEGER, k : INTEGER) RETURNS INTEGER
IF k = 0 OR k = n THEN
RETURN 1
ELSE
IF k > n THEN
RETURN 0
ELSE
RETURN Mystery(n - 1, k - 1) + Mystery(n - 1, k)
ENDIF
ENDIF
ENDFUNCTION
```

Show the recursive trace or tree of function calls that occurs when `Mystery(4, 2)` is called, state the final return value, and identify the mathematical purpose of this function.

An integer grid is represented by a 2D array `Grid : ARRAY[1:10, 1:10] OF INTEGER`.
The array is sorted as follows:
- Each row is sorted in ascending order from left to right.
- Each column is sorted in ascending order from top to bottom.

An efficient search algorithm begins at the top-right corner of the grid (Row 1, Column 10):
- If the current cell value matches the target value `Target`, the search succeeds.
- If the current cell value is greater than `Target`, move left (decrement the column index).
- If the current cell value is less than `Target`, move down (increment the row index).

Write pseudocode for a function `SearchGrid(Target : INTEGER) RETURNS BOOLEAN` that implements this search algorithm. If the target is found, it must output a message containing the row and column and return `TRUE`. If not found, it must output a "Not Found" message and return `FALSE`.

A programmer defines a user-defined record type `Book` as follows:

```pseudocode
TYPE Book
DECLARE ISBN : STRING
DECLARE Title : STRING
DECLARE BorrowCount : INTEGER
ENDTYPE
```

An array of these records is declared as:
`DECLARE BookList : ARRAY[1:50] OF Book`

Write pseudocode for a procedure `SortBooks()` that sorts the array `BookList` in descending order of `BorrowCount` using a bubble sort algorithm. If two books have the same `BorrowCount`, the procedure must sort them in alphabetical (ascending) order of their `Title` field. Use standard bubble sort optimizations where appropriate.

An identifier is valid if it starts with a lowercase letter (`'a'`-`'z'`), followed by zero or more characters that are either lowercase letters or digits (`'0'`-`'9'`), and terminates with a single full stop (`'.'`).

The function `ReadChar() RETURNS CHARACTER` returns the next character from an input buffer.

Write pseudocode for a state-machine function `ValidateIdentifier() RETURNS BOOLEAN` to check if the stream of characters forms a valid identifier. Use four states:
- `"START"` (the initial state)
- `"VALID_CHARS"` (when processing valid alphanumeric characters)
- `"END_STATE"` (when a terminal full stop is found)
- `"ERROR"` (when an unexpected character or transition occurs)

The loop must terminate when the state is either `"END_STATE"` or `"ERROR"`. The function must return `TRUE` if the state machine terminates in the `"END_STATE"` and `FALSE` otherwise.

A computer system represents floating-point numbers using a 12-bit format: an 8-bit mantissa and a 4-bit exponent, both stored in two's complement. Convert the denary value \(-7.375\) into this normalized floating-point format. Show all working, including how you achieved normalization, and write down the final mantissa and exponent.

Using Karnaugh Maps (K-maps) or Boolean algebraic laws, simplify the following Boolean expression to its minimum Sum-of-Products (SoP) form: \(X = A\cdot\bar{B}\cdot\bar{C} + \bar{A}\cdot\bar{B}\cdot C + A\cdot B\cdot C + A\cdot\bar{B}\cdot C + \bar{A}\cdot\bar{B}\cdot\bar{C}\). Show your simplification steps.

a) Convert the following infix expression to Reverse Polish Notation (RPN): \((P + Q) * (R - S / T)\).
b) Evaluate the following RPN expression using a stack: `8 4 2 / * 3 +`. Show the trace of the stack at each step and state the final evaluated value.

A processor has an instruction execution pipeline consisting of 5 stages: Instruction Fetch (IF), Instruction Decode (ID), Operand Fetch (OF), Instruction Execute (EX), and Write Back (WB). Each stage takes exactly 1 clock cycle to complete.
Calculate how many clock cycles are saved when executing a block of 6 independent instructions on this pipelined processor compared to a non-pipelined processor. Show your calculations for both processors.

In an RSA cryptography key-generation setup, a user chooses two prime numbers: \(p = 3\) and \(q = 11\).
a) Calculate the public modulus \(n\) and Totient function \(\phi(n)\).
b) Given that the public exponent \(e = 3\), verify mathematically that the private key exponent \(d\) is \(7\).
c) Encrypt the integer message \(M = 5\) using the public key \((e, n)\).

A Deterministic Finite Automaton (DFA) recognizes strings defined by the regular expression: `a(b|c)*d`.
Define the state transitions for the states:
- \(S_0\): Start state
- \(S_1\): Intermediary state after reading 'a'
- \(S_2\): Accepting/final state
- \(S_e\): Sink/error state

Describe the state transition table by listing all target states from \(S_0\) and \(S_1\) for inputs `a`, `b`, `c`, and `d`.

A programming language syntax is defined by the following Backus-Naur Form (BNF) rules:
` ::= 0 | 1 | 2 | 3`
` ::= X | Y`
` ::= | `

Determine whether each of the following three strings is valid or invalid according to these BNF rules. Provide a step-by-step syntactic derivation or justification for each:
1) `X01`
2) `0Y`
3) `Y`

Analyze the following algorithm and determine its time complexity in Big O notation. Show your mathematical derivation step-by-step:

```
FUNCTION process(n)
DECLARE total : INTEGER
total <- 0
FOR i <- 1 TO n
j <- 1
WHILE j < n
total <- total + 1
j <- j * 2
ENDWHILE
ENDFOR
RETURN total
ENDFUNCTION
```

A 12-bit floating-point system uses a 2's complement representation for both the mantissa and the exponent. The mantissa is represented by 8 bits (including 1 sign bit). The exponent is represented by 4 bits (including 1 sign bit). Convert the denary value \(-3.25\) into this normalized 12-bit floating-point format. Show all your working steps clearly.

A digital logic circuit is described by the Boolean expression: \(F(A, B, C, D) = \sum(0, 2, 5, 7, 8, 10, 13, 15)\). Using a 4-variable Karnaugh Map (K-map), simplify this expression to its minimum sum-of-products (SOP) form. Show the grouping of terms on the K-map and state the final simplified Boolean expression.

Alice wishes to securely send a sensitive document to Bob. The system must guarantee data confidentiality, integrity, and non-repudiation. Describe the step-by-step cryptographic protocol using asymmetric encryption and digital signatures to achieve this. Explicitly identify which keys (Alice's public key, Alice's private key, Bob's public key, Bob's private key) are used at each stage by both the sender and receiver.

A RISC processor uses a 5-stage instruction pipeline: Instruction Fetch (IF), Instruction Decode (ID), Execute (EX), Memory Access (MEM), and Write Back (WB). Consider the execution of the following three assembly instructions:
1. `ADD R1, R2, R3` (writes to R1)
2. `SUB R4, R1, R5` (reads from R1)
3. `AND R6, R7, R8`

Assume that register writes happen in the first half of a clock cycle and register reads happen in the second half. Calculate the total number of clock cycles required to execute these three instructions:
(a) Without operand forwarding (stalls must be inserted to resolve data hazards).
(b) With operand forwarding (the result of the EX stage can be directly routed to the next EX stage).

In a packet-switched network, a router uses Dijkstra's link-state routing algorithm to find the shortest paths from Node A to all other nodes. The network has 5 nodes (A, B, C, D, E) connected by the following bidirectional links with their respective transmission costs:
- A to B: cost 3
- A to C: cost 1
- B to C: cost 1
- B to D: cost 5
- C to D: cost 2
- C to E: cost 7
- D to E: cost 1

Trace the algorithm's execution step-by-step to find the shortest path and minimum transmission cost from Node A to Node E. Show the order of visited nodes and the final path.

An outpatient clinic manages patients using a priority-based queue. Patients with a higher priority (indicated by a lower triage level number, where 1 is the highest priority and 5 is the lowest) are treated first. If patients have the same triage level, the patient who arrived first (indicated by a lower arrival sequence number) is treated first.

You are required to write program code to implement this priority queue using an array of objects.

**Task 1.1**
Create a class named `Patient`.
The class must have the following private attributes:
- `PatientName` (String)
- `TriageLevel` (Integer)
- `SequenceNumber` (Integer)

Define a constructor that initializes these attributes using parameters.
Define public getter methods for all three attributes: `GetName()`, `GetTriageLevel()`, and `GetSequence()`. Save this code in your evidence file.

**Task 1.2**
Create a class named `TriageQueue`.
The class must have the following private attributes:
- `Queue` (An array of 10 items of type `Patient` initialized to null/None)
- `Size` (Integer, initialized to 0)

Define a constructor that initializes `Size` to 0 and the array to hold up to 10 elements. Save this code in your evidence file.

**Task 1.3**
Write a method `Enqueue` within the `TriageQueue` class that takes a `Patient` object as a parameter.
The method must:
- Check if the queue is full (size is 10). If full, return `False`.
- Insert the patient into the array at the correct position based on priority:
- Higher priority (lower `TriageLevel` value) must be closer to index 0.
- If triage levels are equal, the patient with the lower `SequenceNumber` must be closer to index 0.
- Shift existing patients down to make room for the new patient.
- Increment `Size` and return `True`.
Save this code in your evidence file.

**Task 1.4**
Write a method `Dequeue` within the `TriageQueue` class.
The method must:
- Check if the queue is empty. If empty, return null/None.
- Retrieve the patient at index 0.
- Shift all remaining patients up by one position.
- Decrement `Size`.
- Return the retrieved patient.
Save this code in your evidence file.

**Task 1.5**
Write a main program that:
1. Instantiates a `TriageQueue` object.
2. Enqueues the following 5 patients in this order:
- "Alice", Triage Level: 3, Sequence Number: 1
- "Bob", Triage Level: 1, Sequence Number: 2
- "Charlie", Triage Level: 3, Sequence Number: 3
- "David", Triage Level: 2, Sequence Number: 4
- "Eva", Triage Level: 1, Sequence Number: 5
3. Calls `Dequeue` twice and outputs the name of each dequeued patient.
4. Iterates through the remaining elements in the queue and outputs their names and triage levels.
Run your program, take a screenshot of the output, and save it in your evidence file.

A retail company uses a binary search tree (BST) to organize stock items based on alphabetical order of their stock codes. The BST is implemented using a static array of nodes to mimic a heap/pointers structure.

**Task 2.1**
Define a class `Node` with the following attributes:
- `StockCode` (String)
- `Quantity` (Integer)
- `LeftPointer` (Integer)
- `RightPointer` (Integer)

Define a constructor that initializes these attributes. Save this code in your evidence file.

**Task 2.2**
Write a program containing global variables:
- `Tree`: an array of 20 elements of type `Node`
- `RootPointer` (Integer)
- `FreePointer` (Integer)

Write a procedure `InitializeTree()` that:
- Configures the array to form a free list link. For index 0 to 18, `LeftPointer` must point to the next index (`index + 1`). Node 19's `LeftPointer` must be set to -1.
- Set `RightPointer` to -1, `StockCode` to `""` (empty string), and `Quantity` to -1 for all nodes.
- Set `RootPointer` to -1.
- Set `FreePointer` to 0.
Save this code in your evidence file.

**Task 2.3**
Write a recursive function `InsertNode(CurrentPointer, NewNodePointer)` that inserts a node at `NewNodePointer` into the binary search tree starting from `CurrentPointer` index.

The function must:
- Base case: If root is empty, this logic should be handled before or within the method. Assuming `CurrentPointer` is the index to compare:
- If `StockCode` of the new node is less than current node's `StockCode`:
- If `LeftPointer` is -1, set `LeftPointer` of current node to `NewNodePointer`.
- Otherwise, recursively call `InsertNode` on the left child index.
- If `StockCode` of the new node is greater than current node's `StockCode`:
- If `RightPointer` is -1, set `RightPointer` of current node to `NewNodePointer`.
- Otherwise, recursively call `InsertNode` on the right child index.
Save this code in your evidence file.

**Task 2.4**
Write a recursive procedure `InOrder(CurrentPointer)` that outputs the `StockCode` and `Quantity` of all items in alphabetical order. Save this code in your evidence file.

**Task 2.5**
Write main program code that:
1. Calls `InitializeTree()`.
2. Writes a helper procedure `AddStock(Code, Qty)` that takes a free node, updates its attributes, and calls `InsertNode` to place it in the BST. (Handles RootPointer update if BST was empty).
3. Inserts the following stock items in this sequence:
- "PROD50", quantity: 100
- "PROD20", quantity: 50
- "PROD80", quantity: 200
- "PROD30", quantity: 75
- "PROD10", quantity: 30
4. Runs an `InOrder` traversal starting from `RootPointer` and prints the output.
Run your program, take a screenshot of the output, and save it in your evidence file.

A drawing tool needs to implement a recursive region-filling (flood fill) algorithm on an 8x8 character grid. Connected cells containing the character `.` (empty space) are filled with `*` (fill character). Diagonal cells are not connected.

**Task 3.1**
Initialize a global 2D array named `Grid` of size 8 rows by 8 columns with characters.
Initialize the grid precisely as follows:
- Row 0: `["#", "#", "#", "#", "#", "#", "#", "#"]`
- Row 1: `["#", ".", ".", ".", "#", ".", ".", "#"]`
- Row 2: `["#", ".", "#", ".", "#", ".", "#", "#"]`
- Row 3: `["#", ".", "#", ".", ".", ".", ".", "#"]`
- Row 4: `["#", ".", "#", "#", "#", "#", ".", "#"]`
- Row 5: `["#", ".", ".", ".", ".", "#", ".", "#"]`
- Row 6: `["#", "#", "#", "#", ".", ".", ".", "#"]`
- Row 7: `["#", "#", "#", "#", "#", "#", "#", "#"]`

Write a procedure `DisplayGrid()` to cleanly output the grid to the console. Save this code in your evidence file.

**Task 3.2**
Write a recursive function `FloodFill(Row, Col, TargetChar, ReplacementChar)` that:
- Checks if `Row` or `Col` is outside the bounds of the 8x8 array. If it is out of bounds, return 0.
- Checks if the character at `Grid[Row][Col]` is different from `TargetChar`. If it is different, return 0.
- Replaces the character at `Grid[Row][Col]` with `ReplacementChar`.
- Recursively calls `FloodFill` on the 4 surrounding cardinal positions: up, down, left, right.
- Computes and returns the total count of cells filled during this invocation (which is 1 for the current cell plus the sum of returns from the 4 recursive calls).
Save this code in your evidence file.

**Task 3.3**
Write main program code that:
1. Outputs "Grid before fill:" and displays the initial grid status using `DisplayGrid()`.
2. Calls `FloodFill(1, 1, ".", "*")` to fill the starting pocket.
3. Outputs "Total cells filled: " followed by the returned value from the function.
4. Outputs "Grid after fill:" and prints the updated grid using `DisplayGrid()`.
Run your program, take a screenshot of the output, and save it in your evidence file.