An original Thinka practice paper modelled on the structure and difficulty of the Nov 2023 (V1) Cambridge International A Level Computer Science (9618) paper. Not affiliated with or reproduced from Cambridge.
Paper 11 (Theory Fundamentals)
Answer all questions. Calculators must not be used. Write your answers in the spaces provided.
9 Question · 74.97 marks
Question 1 · Structured
8.33 marks
A computer system stores real numbers using floating-point representation with: - 8 bits for the mantissa (in two's complement) - 4 bits for the exponent (in two's complement)
(a) Convert the denary value \(-3.75\) into this normalised floating-point format. Show all your working. [4]
(b) Explain the term "underflow" in the context of floating-point representation and state one way to prevent it. [2]
(c) State the main trade-off when increasing the number of bits allocated to the exponent at the expense of the mantissa in a fixed-word length floating-point representation. [2]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) 1. Represent the positive version of the number in fixed-point binary first: \(3.75 = 2^1 + 2^0 + 2^{-1} + 2^{-2} = 11.11_2\) 2. For negative, represent it in two's complement. If we use 8 bits for fixed-point: \(0011.1100\) (for \(+3.75\)) One's complement: \(1100.0011\) Two's complement: \(1100.0100\) 3. To normalise this negative binary number, the binary point must be placed so that the first two bits are different (specifically '10' for a negative normalised number): \(1100.0100 \times 2^0 = 1.0001000 \times 2^2\) 4. The normalised mantissa is: `10001000` (8 bits) 5. The exponent is \(+2\), which in 4-bit two's complement is `0010`.
(b) Underflow occurs when a number is too small to be represented with the allocated bits (closer to zero than the smallest possible non-zero representation). It can be prevented by increasing the number of bits in the exponent, using arbitrary-precision arithmetic libraries, or scaling the numbers.
(c) Increasing the exponent bits increases the overall range of representable numbers, but decreases the precision/accuracy of the represented numbers because there are fewer bits for the mantissa.
Marking scheme
(a) [Total: 4 marks] - 1 mark: Correct conversion of 3.75 into binary fixed-point (e.g. 11.11 or 0011.11). - 1 mark: Correct Two's complement conversion for negative value (e.g. 1100.0100). - 1 mark: Correct normalised mantissa (10001000). - 1 mark: Correct exponent in binary (0010).
(b) [Total: 2 marks] - 1 mark: Definition of underflow (number is too small to be represented/closer to zero than minimum value). - 1 mark: Appropriate prevention method (e.g. allocate more bits to exponent / use float-point libraries).
(c) [Total: 2 marks] - 1 mark: Identification that the range of numbers increases. - 1 mark: Identification that precision/accuracy decreases.
Question 2 · Structured
8.33 marks
An assembly language program is run on a processor. The processor has an Accumulator (ACC) and an Index Register (IX).
The table below shows a subset of the assembly language instruction set: - `LDD `: Direct addressing. Load contents of `` to ACC. - `LDX `: Indexed addressing. Load contents of ` + IX` to ACC. - `LDR `: Immediate addressing. Load `` to IX. - `ADD `: Add contents of `` to ACC. - `INC `: Increment the content of the register (ACC or IX). - `STO `: Store the content of ACC at the specified ``.
The initial memory state is as follows: - Address `100`: `12` - Address `101`: `25` - Address `102`: `40` - Address `103`: `15` - Address `104`: `0`
(a) Trace the following assembly program. Complete the trace table showing the values of ACC, IX, and memory location `104` after each instruction is executed. [5]
```text LDR 2 LDX 100 ADD 101 INC IX STO 104 ```
(b) Describe how the physical address is calculated when using indexed addressing. [2]
(c) Identify the instruction from the program above that uses immediate addressing. [1]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Trace table values: 1. After `LDR 2`: ACC: (unchanged/undefined), IX: 2, Memory 104: 0 2. After `LDX 100`: Address calculated: 100 + IX = 100 + 2 = 102. Value at 102 is 40. ACC: 40, IX: 2, Memory 104: 0 3. After `ADD 101`: Value at 101 is 25. ACC: 40 + 25 = 65, IX: 2, Memory 104: 0 4. After `INC IX`: ACC: 65, IX: 3, Memory 104: 0 5. After `STO 104`: ACC: 65, IX: 3, Memory 104: 65
(b) The physical address is calculated by taking the base address specified in the instruction and adding the current contents of the Index Register (IX) to it.
(c) `LDR 2`
Marking scheme
(a) [Total: 5 marks] - 1 mark: Correct IX value after LDR 2 (IX = 2). - 1 mark: Correct address indexing calculation and loading 40 into ACC after LDX 100. - 1 mark: Correct addition of 25 to get 65 in ACC. - 1 mark: Correct increment of IX to 3. - 1 mark: Correct final store of 65 in memory location 104.
(b) [Total: 2 marks] - 1 mark: Mentions using the base address from the instruction. - 1 mark: Mentions adding the value of the Index Register (IX) to form the actual address.
(c) [Total: 1 mark] - 1 mark: Identifies `LDR 2`.
Question 3 · Structured
8.33 marks
An integer linked list is implemented using a 1D array of records. Each record contains a `data` field and a `pointer` field.
The pointer `startPointer` stores the index of the first node of the list. The pointer `freePointer` stores the index of the first node in the free list (empty nodes).
The array `List` is currently configured as follows:
(a) Draw a logical representation of the active linked list (excluding the free list), showing the data values and how they point to each other. [2]
(b) The value `12` is to be inserted into the list so that the list remains sorted in ascending order.
(i) Describe the steps needed to find the correct insertion position and link the new node containing `12` into the list. [3]
(ii) Update the array, `startPointer`, and `freePointer` to show the state after `12` has been successfully inserted. [3]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) The active linked list starts at index 0 (data 45) -> points to index 2 (data 78) -> points to -1 (null). Logical representation: `[45] -> [78] -> null`
(b)(i) Steps to insert `12`: 1. Check the first item in the list (`45`). Since `12` is smaller than the first item, it must be inserted at the beginning of the list. 2. Obtain the index of the next available free node from `freePointer` (which is index 1). 3. Set `freePointer` to the pointer value stored in node 1 (which is 3). 4. Store the data value `12` in `List[1].Data`. 5. Set `List[1].Pointer` to point to the current start of the list (`0`). 6. Update `startPointer` to point to the newly added node (`1`).
(a) [Total: 2 marks] - 1 mark: Showing node with 45 pointing to node with 78. - 1 mark: Showing node with 78 pointing to null / ground.
(b)(i) [Total: 3 marks] - 1 mark: Identify that 12 is less than 45, meaning insertion at the start. - 1 mark: Describe taking node from free list and updating `freePointer` (to 3). - 1 mark: Describe adjusting pointers so new node points to index 0, and `startPointer` points to 1.
(b)(ii) [Total: 3 marks] - 1 mark: Correctly updating `startPointer` to 1 and `freePointer` to 3. - 1 mark: Correctly writing 12 into `List[1].Data`. - 1 mark: Correctly setting `List[1].Pointer` to 0.
Question 4 · Structured
8.33 marks
A school uses a relational database to store information about students and their clubs. The following unnormalised table structure, `tblStudentClubs`, is used: `StudentID`, `StudentName`, `ClubID`, `ClubName`, `ClubFee`, `DateJoined`
Each student can join multiple clubs. Each club has a unique ID, a name, and a standard monthly fee.
(a) Explain why this table is not in Second Normal Form (2NF). [2]
(b) Normalise this relation into Third Normal Form (3NF). State the primary keys (PK) and foreign keys (FK) for each of your proposed tables. [4]
(c) Write an SQL query to display the `StudentName` and `ClubName` for all students who joined a club before '2023-01-01'. [2]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) The primary key of the unnormalised table is a composite key: `(StudentID, ClubID)`. Partial dependencies exist because non-key attributes depend on only part of the primary key. Specifically, `StudentName` depends only on `StudentID`, and `ClubName` and `ClubFee` depend only on `ClubID`.
(c) SQL Query: ```sql SELECT tblStudent.StudentName, tblClub.ClubName FROM tblStudent INNER JOIN tblStudentClub ON tblStudent.StudentID = tblStudentClub.StudentID INNER JOIN tblClub ON tblStudentClub.ClubID = tblClub.ClubID WHERE tblStudentClub.DateJoined < '2023-01-01'; ```
Marking scheme
(a) [Total: 2 marks] - 1 mark: Explains that the primary key must be composite (StudentID, ClubID). - 1 mark: Explains that partial dependencies exist / non-key fields (StudentName or ClubName) depend on only part of the composite key.
(b) [Total: 4 marks] - 1 mark: Creation of a student table with correct primary key. - 1 mark: Creation of a club table with correct primary key. - 1 mark: Creation of a link/junction table (tblStudentClub) to resolve many-to-many relationship. - 1 mark: Correctly identifies all PKs and FKs across tables.
(c) [Total: 2 marks] - 1 mark: Correct SELECT and JOIN statements linking all three tables. - 1 mark: Correct WHERE clause with the date comparison filter.
Question 5 · Structured
8.33 marks
(a) An IPv4 address is represented in CIDR notation as: `192.168.4.115/26`.
(i) State the subnet mask of this address in dotted decimal format. [2]
(ii) Calculate the network address for this subnet. Show all your working. [2]
(b) Describe how Carrier Sense Multiple Access with Collision Detection (CSMA/CD) handles data collisions on a shared bus network. [4]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a)(i) A prefix length of /26 means 26 bits set to 1. First three octets: `255.255.255` (24 bits). Fourth octet has remaining 2 bits set: `11000000` in binary, which is 192 in denary. Subnet mask: `255.255.255.192`.
(a)(ii) Perform a bitwise AND between the IP address and the subnet mask: IP address 4th octet: 115 = `01110011` in binary. Subnet mask 4th octet: 192 = `11000000` in binary. AND result: `01000000` in binary, which is 64 in denary. Network address: `192.168.4.64`.
(b) How CSMA/CD works: 1. A device listens to the communication medium (carrier) before transmitting to see if it is idle. 2. If the medium is idle, the device starts transmitting its data. 3. While transmitting, the device continues to monitor the medium to detect if another device's signal collides with its own. 4. If a collision is detected, transmitting devices stop sending data immediately and send a 'jam signal' to ensure all devices know a collision occurred. 5. Devices then wait a random period of time (using a backoff algorithm) before trying to retransmit.
Marking scheme
(a)(i) [Total: 2 marks] - 1 mark: Recognises that /26 means 26 network bits. - 1 mark: Correctly gives the mask 255.255.255.192.
(a)(ii) [Total: 2 marks] - 1 mark: Demonstrates bitwise AND process (e.g., converting 115 and 192 to binary). - 1 mark: Correctly states network address 192.168.4.64.
(b) [Total: 4 marks] (Any 4 of the following): - 1 mark: Device monitors/listens to line before sending (carrier sense). - 1 mark: Device starts transmission only if line is idle. - 1 mark: Device continues to monitor during transmission. - 1 mark: If collision is detected, transmission halts and a jam signal is sent. - 1 mark: Devices wait a random amount of time before retransmitting.
Question 6 · Structured
8.33 marks
(a) During the compilation of a high-level language program, lexical analysis is performed. Describe what happens during lexical analysis. [3]
(b) State the role of the linker after compilation is complete. [2]
(c) State the role of the loader. [1]
(d) Explain one advantage of using an interpreter instead of a compiler during the development phase of a program. [2]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) During lexical analysis: - Source code is analysed character by character. - Unnecessary characters such as white spaces, tabs, and comments are removed. - Groups of characters forming keywords, operators, identifiers, and literals are grouped into standardized tokens. - Identifiers are added to the symbol table.
(b) The role of the linker: - It combines different compiled object files and compiled external libraries into a single executable file. - It resolves external references / addresses between different code files.
(c) The role of the loader: - It copies the executable code from secondary storage into primary memory (RAM) so that the CPU can execute it.
(d) Advantage of an interpreter: - It allows easier and faster debugging because execution stops immediately on the line where an error occurs, allowing the programmer to inspect current variable values without needing to rebuild or recompile the entire program.
Marking scheme
(a) [Total: 3 marks] - 1 mark: Elimination of whitespace/comments. - 1 mark: Grouping of characters into tokens. - 1 mark: Entry of identifiers into a symbol table.
(b) [Total: 2 marks] - 1 mark: Combines object codes/libraries into a single file. - 1 mark: Resolves external references/linking addresses.
(c) [Total: 1 mark] - 1 mark: Copies executable program from disk into main memory (RAM).
(d) [Total: 2 marks] - 1 mark: Identifies that execution stops immediately at an error / no compile cycle needed. - 1 mark: Explains that this makes debugging faster/easier to trace variables.
Question 7 · Structured
8.33 marks
(a) Draw a logic circuit for the following Boolean expression: \(X = (A \cdot \overline{B}) + (B \cdot C)\) Do not simplify the expression. [3]
(b) Using Boolean algebra laws, simplify the following Boolean expression: \(Y = \overline{A \cdot B} \cdot (\overline{A} + B)\) Show all intermediate steps and state the laws used. [5]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) The logic circuit consists of: - A NOT gate on input \(B\) to yield \(\overline{B}\). - An AND gate with inputs \(A\) and \(\overline{B}\). - An AND gate with inputs \(B\) and \(C\). - An OR gate combining the outputs of the two AND gates to produce \(X\).
(b) Simplification steps: 1. Apply De Morgan's Law to \(\overline{A \cdot B}\): \(\overline{A \cdot B} = \overline{A} + \overline{B}\) This gives: \(Y = (\overline{A} + \overline{B}) \cdot (\overline{A} + B)\) 2. Apply the Distributive Law (factoring out \(\overline{A}\)): \(Y = \overline{A} + (\overline{B} \cdot B)\) 3. Apply the Complement Law (since \(\overline{B} \cdot B = 0\)): \(Y = \overline{A} + 0\) 4. Apply the Identity Law: \(Y = \overline{A}\)
(a) [Total: 3 marks] - 1 mark: Correct representation of NOT B gate. - 1 mark: Two correct AND gates (A AND NOT B) and (B AND C). - 1 mark: Correct final OR gate combining both inputs.
(b) [Total: 5 marks] - 1 mark: Correct application of De Morgan's Law to get \((\overline{A} + \overline{B})\). - 1 mark: Correct expansion or factoring process. - 1 mark: Correct application of Complement law (e.g. \(B \cdot \overline{B} = 0\) or equivalent). - 1 mark: Correct application of Identity/Idempotent laws during simplification. - 1 mark: Correct final simplified expression: \(Y = \overline{A}\) (or `NOT A`).
Question 8 · Structured
8.33 marks
A software development company is designing a new stock control system for a large retail outlet.
(a) Distinguish between alpha testing and beta testing. [4]
(b) Explain the difference between black-box testing and white-box testing. [2]
(c) State what is meant by "stub testing" and describe when it would be used. [2]
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Distinctions between alpha and beta testing: - Alpha testing is conducted in-house by the development team's testers before the software is released to anyone external, whereas beta testing is performed by a select group of real end-users in their own live operating environments. - Alpha testing focuses on finding major bugs and can involve both white-box and black-box methods, whereas beta testing focuses on real-world usability and is strictly black-box testing.
(b) Difference: - Black-box testing tests the functionality of the program against specifications without any knowledge or visibility of the underlying source code. White-box testing examines the internal logical paths, code structures, and algorithms of the software using the source code.
(c) Stub testing: - Stub testing uses a dummy or simplified module (called a stub) to simulate the behavior of a software component that has not yet been written or integrated. It is typically used during top-down integration testing to allow high-level modules to be tested before their child/dependent modules are completed.
Marking scheme
(a) [Total: 4 marks] - 1 mark: Mentions alpha is done in-house/by developers. - 1 mark: Mentions beta is done by external/potential end-users in their own environments. - 1 mark: Identifies that alpha uses a controlled environment / can use white-box testing. - 1 mark: Identifies that beta uses real-world conditions / is strictly black-box testing.
(b) [Total: 2 marks] - 1 mark: Correct definition of black-box testing (focused on input/output compliance with no access to code). - 1 mark: Correct definition of white-box testing (focused on logic paths/structural paths using source code access).
(c) [Total: 2 marks] - 1 mark: States what a stub is (a dummy/placeholder module simulating incomplete code). - 1 mark: Describes its usage (during top-down integration testing to test parents/calling modules before children are ready).
Question 9 · Structured Theory Questions
8.33 marks
An assembly language programmer uses a set of instructions to manipulate data stored in memory. The following table shows the current contents of a section of primary memory:
The programmer's processor includes an Accumulator (ACC) and an Index Register (IX). The initial values for these registers are: * ACC: 0 * IX: 2
The instruction set includes the following operations: * `LDD `: Load the contents of the specified address into the ACC. * `LDI `: Load the contents of the address found at the specified address into the ACC. * `LDX `: Load the contents of the address (specified address + IX) into the ACC. * `ADD `: Add the contents of the specified address to the value currently in the ACC. * `INC `: Increment the value of the specified register (ACC or IX) by 1.
**(a)** State the difference between direct addressing and indirect addressing. [2 marks]
**(b)** Trace the execution of the assembly program below. Complete the trace by determining the contents of the ACC and IX registers after each instruction is executed. [6 marks]
Show answer & marking schemeHide answer & marking scheme
Worked solution
Step-by-step trace calculation:
1. **`LDD 101`**: - This is direct addressing. We look up the contents at address 101 directly. - Memory[101] contains 20. - So, ACC becomes 20. IX remains 2.
2. **`ADD 103`**: - Adds the contents of address 103 to the ACC. - Memory[103] contains 15. - Current ACC is 20, so 20 + 15 = 35. - So, ACC becomes 35. IX remains 2.
3. **`LDX 100`**: - This is indexed addressing. The effective address is computed as: address + IX = 100 + 2 = 102. - We load the contents of address 102 into the ACC. - Memory[102] contains 100. - So, ACC becomes 100. IX remains 2.
4. **`LDI 102`**: - This is indirect addressing. We look at address 102 to find the target address, then load the data from that target address. - Memory[102] contains 100. So the target address is 100. - Memory[100] contains 105. - So, ACC becomes 105. IX remains 2.
5. **`INC IX`**: - Increments the Index Register (IX) by 1. - Current IX is 2, so 2 + 1 = 3. - So, ACC remains 105. IX becomes 3.
6. **`LDX 101`**: - Indexed addressing. The effective address is computed as: address + IX = 101 + 3 = 104. - We load the contents of address 104 into the ACC. - Memory[104] contains 3. - So, ACC becomes 3. IX remains 3.
Marking scheme
Part (a) [Max 2 marks]: - 1 mark for explaining Direct Addressing (e.g., the instruction operand is the actual memory address where the data value is stored). - 1 mark for explaining Indirect Addressing (e.g., the instruction operand is a memory address pointing to another memory location that contains the final address of the data).
Part (b) [Max 6 marks]: - 1 mark for each correctly traced row: - `LDD 101` row: ACC = 20, IX = 2 [1 mark] - `ADD 103` row: ACC = 35, IX = 2 [1 mark] - `LDX 100` row: ACC = 100, IX = 2 [1 mark] - `LDI 102` row: ACC = 105, IX = 2 [1 mark] - `INC IX` row: ACC = 105, IX = 3 [1 mark] - `LDX 101` row: ACC = 3, IX = 3 [1 mark]
Paper 21 (AS Programming Skills)
Answer all questions. Show your pseudocode implementations clearly where required.
8 Question · 74.96 marks
Question 1 · Pseudocode & Algorithmic Problem Solving
9.37 marks
Write a pseudocode function `ExtractDomain(Email : STRING) RETURNS STRING`. The function checks if `Email` is valid: it must contain exactly one '@' character, and at least one '.' character after the '@' character. If the email format is valid, the function returns the domain part of the email (everything after the '@' character). If the format is invalid, the function must return the string "INVALID".
Show answer & marking schemeHide answer & marking scheme
Worked solution
The function first determines the length of the input string and iterates through it to count the occurrences of '@' and record the index of its position. If the number of '@' symbols is not exactly 1, or if it is at the very end of the string, it returns "INVALID". It then loops through the substring following the '@' character to count occurrences of '.'. If no dot is found, it returns "INVALID"; otherwise, it extracts and returns the domain part of the string.
Marking scheme
- 1 mark: Correct function signature with standard parameter and return type. - 1 mark: Loop through the entire string using LENGTH. - 2 marks: Counting '@' characters and storing the index of the '@' character. - 2 marks: Correctly validating that there is exactly one '@' and it is not at the end. - 2 marks: Correctly counting '.' characters exclusively after the '@' index. - 1.37 marks: Returning "INVALID" on error, and returning the correct substring domain on success.
Question 2 · Pseudocode & Algorithmic Problem Solving
9.37 marks
Write a pseudocode procedure `FindLowStock(Threshold : INTEGER)` that processes two global 1D arrays: `ProductCodes` (array [1:100] of STRING) and `StockLevels` (array [1:100] of INTEGER). The procedure must loop through the arrays and, for any product whose stock level is strictly below the `Threshold`, output the product code and its stock level in the format: "Product [code] has [stock] items". It must also calculate and output the percentage of total products that are low on stock, formatted as: "Percentage low: [value]%".
Show answer & marking schemeHide answer & marking scheme
Worked solution
The procedure initializes a counter `LowCount` to 0. It iterates from index 1 to 100. Inside the loop, it checks if `StockLevels[i]` is less than `Threshold`. If it is, it outputs the required string using values from both arrays and increments `LowCount`. After the loop, it calculates the percentage of low stock products by dividing `LowCount` by 100 (and multiplying by 100, which mathematically simplifies to `LowCount` itself, though explicitly writing the formula is preferred) and outputs the percentage.
Marking scheme
- 1.37 marks: Correct procedure header taking an integer parameter. - 2 marks: Correct loop structure running from 1 to 100. - 2 marks: Correct conditional check comparing array element with threshold. - 2 marks: Outputting the product code and stock level in the exact/logical format within the IF block. - 2 marks: Correct calculation and output of the percentage.
Question 3 · Pseudocode & Algorithmic Problem Solving
9.37 marks
A text file named `ClassLog.txt` contains records of students. The file is structured with student names (STRING) and scores (INTEGER) on alternating lines (i.e., line 1: name, line 2: score, line 3: name, line 4: score, etc.). Write a pseudocode procedure `FindHighest()` that reads this file to find the student with the highest score. The procedure must output "Highest: [Name] with [Score]". If the file contains no data, the procedure must output "File Empty". Ensure files are properly opened and closed.
Show answer & marking schemeHide answer & marking scheme
Worked solution
This procedure opens `ClassLog.txt` for reading and initializes tracking variables (`BestScore` to a low number and `FileEmpty` to true). It uses a loop controlled by `EOF()` to read name-score pairs sequentially. If any pair is read, `FileEmpty` becomes false. A comparison updates the highest score tracking variables. Finally, the file is closed, and the output is selected based on whether any data was processed.
Marking scheme
- 1 mark: Correct OPENFILE and CLOSEFILE syntax with proper read modes. - 2 marks: Loop control using `NOT EOF` to read the entire file properly. - 2 marks: Consecutive READFILE operations to alternate reading a string and an integer. - 2 marks: Proper conditional comparison to track and update the maximum score and matching name. - 2.37 marks: Correct handling of the empty file scenario and outputting the exact required text.
Question 4 · Pseudocode & Algorithmic Problem Solving
9.37 marks
A 2D array `Grid` of size 8 rows by 8 columns (indices 1 to 8) contains characters representing a map. Write a pseudocode function `CountAdjacent(Row : INTEGER, Col : INTEGER) RETURNS INTEGER` that calculates and returns the number of cells adjacent (including diagonals) to the cell `(Row, Col)` containing the character 'X'. Your function must not check cells outside the boundary of the array, nor should it check the starting cell itself.
Show answer & marking schemeHide answer & marking scheme
Worked solution
The function uses nested loops running from `Row - 1` to `Row + 1` and `Col - 1` to `Col + 1` respectively. Within these loops, an check ensures that indices `r` and `c` are between 1 and 8 (inclusive). An additional check prevents the coordinate `(Row, Col)` itself from being counted. If the valid adjacent cell contains "X", the count is incremented. Finally, the count is returned.
Marking scheme
- 1.37 marks: Correct function header with appropriate parameters and return type. - 2 marks: Nested loop setup to iterate through offsets -1 to +1. - 2 marks: Boundary verification ensuring row and column indices stay within the 1 to 8 range. - 2 marks: Excluding the center cell `(Row, Col)` from comparison. - 2 marks: Successfully tracking the count of "X" and returning it.
Question 5 · Pseudocode & Algorithmic Problem Solving
9.37 marks
Write a pseudocode procedure `SortDescending(BYREF Scores : ARRAY)` to sort a 1D array of integers `Scores` containing `N` elements (indexed 1 to `N`) in descending order. You must implement a Bubble Sort algorithm optimized with a boolean flag `Swapped` so that execution terminates as soon as a pass completes without making any swaps. You can assume `N` is a global constant representing the size of the array.
Show answer & marking schemeHide answer & marking scheme
Worked solution
The procedure implements an optimized bubble sort. The outer loop (`REPEAT...UNTIL`) terminates if `Swapped` remains `FALSE` after an entire inner loop pass, or if the maximum possible passes (`N`) have occurred. The inner loop compares adjacent elements and swaps them if the first element is less than the second, ensuring a descending order sequence.
Marking scheme
- 1 mark: Correct procedure header specifying passing by reference (`BYREF`). - 2 marks: Outer loop control utilizing a `Swapped` flag. - 2 marks: Inner loop using the bounds appropriately (avoiding index out of bounds up to `N - Pass` or `N - 1`). - 2 marks: Correct logic to swap elements using a temporary variable. - 2.37 marks: Comparing with `<` for descending order and properly setting/resetting the boolean flag.
Question 6 · Pseudocode & Algorithmic Problem Solving
9.37 marks
Write a pseudocode procedure `GetValidPassword()` that repeatedly prompts a user to enter a password until it matches three validation requirements: 1. It must be at least 8 characters long. 2. It must contain at least one uppercase letter ('A' to 'Z'). 3. It must contain at least one numeric digit ('0' to '9'). Once a valid password is entered, the procedure must output "Password set successfully".
Show answer & marking schemeHide answer & marking scheme
Worked solution
The procedure uses a REPEAT loop to prompt for input. Inside the loop, it checks the length of the string. If the length is at least 8, it iterates over each character of the string, checking if any character is in the range 'A' to 'Z' (uppercase check) or '0' to '9' (digit check). If both conditions are satisfied, `Valid` is set to TRUE, ending the loop and showing a success message.
Marking scheme
- 1.37 marks: Loop structure (REPEAT...UNTIL or WHILE) used to continuously request password entry. - 2 marks: Checking string length is 8 or more. - 2 marks: Loop to extract and examine each individual character using SUBSTRING. - 2 marks: Correct conditions matching character ranges 'A' to 'Z' and '0' to '9'. - 2 marks: Outputting instructions/errors and success messages dynamically based on validation success.
Question 7 · Pseudocode & Algorithmic Problem Solving
9.37 marks
A circular queue is implemented as a 1D array `Queue` of size 10 (indices 1 to 10) with three integer variables: `HeadPointer` (index of first item), `TailPointer` (index of last item), and `NumItems` (the count of items currently in the queue). Write a pseudocode function `Enqueue(NewItem : STRING) RETURNS BOOLEAN` that inserts an item into the queue. If the queue is full, return `FALSE`. Otherwise, insert the item at the correct position, update the pointer(s) and element count, and return `TRUE`. Note that pointers wrap around to index 1 when incremented past 10.
Show answer & marking schemeHide answer & marking scheme
Worked solution
First, the function checks if `NumItems` is equal to 10 (which means the queue is full); if so, it returns FALSE. Otherwise, if the queue is currently empty (`NumItems = 0`), both `HeadPointer` and `TailPointer` are set to 1. If it is not empty, `TailPointer` is incremented. If `TailPointer` exceeds 10, it wraps around to 1. The new item is stored in the array at the position indicated by `TailPointer`, `NumItems` is incremented, and the function returns TRUE.
Marking scheme
- 1.37 marks: Correct function declaration returning a BOOLEAN and accepting a STRING parameter. - 2 marks: Identifying and returning FALSE when the queue is full (using NumItems). - 2 marks: Initializing head and tail pointers to 1 if the queue is empty. - 2 marks: Correctly incrementing and wrapping TailPointer (e.g., using IF check or modulo arithmetic). - 2 marks: Writing the value to Queue array and incrementing NumItems count successfully.
Question 8 · Pseudocode & Algorithmic Problem Solving
9.37 marks
Write a pseudocode function `RunLengthEncode(InputStr : STRING) RETURNS STRING` that takes a non-empty string consisting only of alphabetical characters (for example, "AAABBC") and returns a run-length encoded version. In run-length encoding, consecutive duplicate characters are compressed into the number of repetitions followed by the character itself (e.g., "3A2B1C"). Use standard functions such as `LENGTH`, `SUBSTRING`, and `NUM_TO_STR`.
Show answer & marking schemeHide answer & marking scheme
Worked solution
The algorithm tracks the current character and counts how many times it occurs consecutively. It loops from the second character to the end of the string. If a character matches the current one, it increments the counter. Otherwise, it appends the count (converted to a string) and the character to the accumulator string, resets the count to 1, and updates the tracking character. After the loop, it appends the final run details to the result string and returns it.
Marking scheme
- 1.37 marks: Function header and variable declarations correctly typed. - 2 marks: Initializing variables properly (e.g., tracking first character and starting loop from 2). - 2 marks: Loop setup navigating through the length of the string correctly. - 2 marks: Conditional logic to increment count on duplicate characters or format and append on difference. - 2 marks: Appending final sequence block after the loop concludes and returning result.
Paper 31 (Advanced Theory)
Answer all questions. Calculations and circuit layout operations must show working.
12 Question · 75 marks
Question 1 · Advanced Theory
6.25 marks
Explain the concept of Virtual Machines in the context of intermediate code execution. Compare the execution of intermediate code using an interpreter versus Just-In-Time (JIT) compilation.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. Intermediate Code (Bytecode): The compiler first translates source code into intermediate bytecode, which is platform-independent. 2. Virtual Machine (VM): The VM acts as an abstraction layer, executing bytecode on different physical hardware architectures. 3. Interpreter: Executes bytecode line-by-line. Advantage: No compilation startup delay. Disadvantage: Slower execution overall. 4. JIT Compiler: Compiles bytecode segments into native machine code at runtime. Advantage: Runs at native hardware speeds, compiles once and caches for subsequent executions. Disadvantage: Startup delay and higher memory overhead.
Marking scheme
1.0 mark: Explaining intermediate code as platform-independent. 1.0 mark: Defining VM as the emulator executing the bytecode. 1.5 marks: Detailing Interpreter execution (line-by-line translation). 1.5 marks: Detailing JIT compilation (compilation to native machine code at runtime). 1.25 marks: Accurate comparative analysis of performance/resource trade-offs.
Question 2 · Advanced Theory
6.25 marks
A floating-point representation uses a 12-bit normalized mantissa and a 4-bit exponent, both in two's complement. Convert the following real binary representation to denary: Mantissa: 101101000000, Exponent: 0110. Show your working. Explain why normalizing binary floating-point numbers is necessary.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. Convert Exponent: 0110 in two's complement is +6. 2. Convert Mantissa: 101101000000 has a sign bit of 1 (negative). Taking the two's complement yields 010011000000, which has a magnitude of 0.5 + 0.0625 + 0.03125 = 0.59375. So, the mantissa value is -0.59375. 3. Combine: -0.59375 * 2^6 = -0.59375 * 64 = -38. 4. Normalization reasons: (i) To maximize precision by avoiding leading redundant digits. (ii) To ensure a unique representation for every real number.
Marking scheme
1.0 mark: Exponent conversion to +6. 1.5 marks: Mantissa conversion to -0.59375. 1.25 marks: Multiplying mantissa by 2^6 to get final answer -38. 2.5 marks: Giving two distinct, valid reasons for normalization (maximizing precision and ensuring unique representation).
Question 3 · Advanced Theory
6.25 marks
An organization is assigned the IPv4 address block 192.168.4.0/22. (a) Determine the subnet mask in dotted-decimal format. (b) Calculate the total number of usable host IP addresses available in this block, showing your calculations. (c) State the network address and the broadcast address for this block.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) A /22 prefix means 22 network bits. In binary, the subnet mask is 11111111.11111111.11111100.00000000, which translates to 255.255.252.0. (b) The number of host bits is 32 - 22 = 10. The total number of IP addresses is 2^10 = 1024. The number of usable host addresses is 2^10 - 2 = 1022 (subtracting network and broadcast addresses). (c) The network address is 192.168.4.0. The broadcast address has all host bits set to 1, giving 192.168.7.255.
Given the Prolog database: parent(albert, bob). parent(albert, clara). parent(bob, david). parent(clara, emily). parent(clara, frank). ancestor(X, Y) :- parent(X, Y). ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y). (a) Trace the steps Prolog takes to evaluate the query: ?- ancestor(albert, emily). (b) Explain the difference between backtracking and recursion in a declarative programming context.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Trace: 1. Prolog targets ancestor(albert, emily). 2. Rule 1: checks parent(albert, emily) - no matching fact, fails. 3. Rule 2: matches parent(albert, Z). First match: Z = bob. 4. Recursive call: ancestor(bob, emily). 5. Under ancestor(bob, emily): Rule 1 checks parent(bob, emily) - fails. Rule 2 matches parent(bob, Z1) -> Z1 = david. Recursive call ancestor(david, emily) fails entirely because david has no parents. 6. Prolog backtracks to ancestor(bob, emily) Rule 2, which has no more options, failing ancestor(bob, emily). 7. Prolog backtracks to ancestor(albert, emily) Rule 2, finding alternative Z = clara. 8. Recursive call: ancestor(clara, emily). 9. Under ancestor(clara, emily): Rule 1 checks parent(clara, emily) - matches fact. Succeeds. 10. Query returns true. (b) Recursion is when a rule references itself (e.g., ancestor). Backtracking is the mechanism of reverting variable bindings to explore alternate paths when a goal fails.
Marking scheme
3.0 marks: Step-by-step trace showing initial try of Z=bob, failure, backtracking, and successful execution of Z=clara. 1.25 marks: Definition of recursion in declarative paradigm. 2.0 marks: Definition of backtracking as automatic alternative search.
Question 5 · Advanced Theory
6.25 marks
Consider the following recursive algorithm in pseudocode: FUNCTION Solve(n) RETURNS INTEGER IF n <= 1 THEN RETURN 1 ELSE RETURN Solve(n - 1) + Solve(n - 1) ENDIF ENDFUNCTION (a) Draw the recursion tree for Solve(4) and state the returned value. (b) Determine the time complexity of the Solve(n) algorithm using Big O notation, justifying your answer.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Solve(4) spawns two calls of Solve(3). Each Solve(3) spawns two Solve(2) calls. Each Solve(2) spawns two Solve(1) calls. Solve(1) returns 1. Computing upwards: Solve(2) = 1 + 1 = 2; Solve(3) = 2 + 2 = 4; Solve(4) = 4 + 4 = 8. (b) Since each increase in 'n' doubles the number of recursive calls, the total operations for size n is 2^n - 1. Thus, the time complexity is O(2^n) (exponential).
Marking scheme
2.25 marks: Constructing a clear recursive call hierarchy/tree. 1.0 mark: Stating the correct return value of 8. 1.5 marks: Stating the correct Big O complexity of O(2^n). 1.5 marks: Providing correct justification based on the branching factor of 2 at each recursive depth.
Question 6 · Advanced Theory
6.25 marks
The compilation process involves several phases. Explain the purpose of: (a) Lexical analysis, (b) Syntax analysis, and (c) Code optimization. For each phase, identify one typical error or output generated by that phase.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Lexical analysis: Group input characters into tokens, discarding whitespace and comments. Output: Stream of tokens and symbol table. Error: Unknown identifier or invalid character. (b) Syntax analysis: Check tokens against grammar rules. Output: Syntax/Parse tree. Error: Missing brackets or operator syntax errors. (c) Code optimization: Restructure code to reduce space or execution time (e.g., eliminating dead code). Output: Optimized intermediate/object code. No compiler errors are generally produced during this phase.
Marking scheme
2.0 marks: Lexical analysis explanation and valid output/error. 2.0 marks: Syntax analysis explanation and valid output/error. 2.25 marks: Code optimization explanation and typical optimization technique (e.g., constant folding).
Question 7 · Advanced Theory
6.25 marks
An artificial neural network contains a single neuron with two inputs, x1 = 0.6 and x2 = -0.4. The associated weights are w1 = 0.5 and w2 = 1.2, and the bias is b = -0.1. (a) Calculate the weighted sum of inputs (including bias) for this neuron. (b) The neuron uses a Step activation function defined as: f(z) = 1 if z >= 0, and f(z) = 0 if z < 0. Determine the output of the neuron. (c) Describe the role of 'Backpropagation' in training an artificial neural network.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Weighted sum z = (x1 * w1) + (x2 * w2) + b = (0.6 * 0.5) + (-0.4 * 1.2) - 0.1 = 0.3 - 0.48 - 0.1 = -0.28. (b) Since z = -0.28, which is less than 0, f(z) = 0. (c) Backpropagation calculates the error derivative/gradient at the output and propagates it backward through the layers to update weights and biases, minimizing error.
Marking scheme
2.25 marks: Showing calculation of weighted sum z = -0.28. 1.0 mark: Correct neuron output of 0 based on the condition. 3.0 marks: Explaining backpropagation (calculating output error, working backwards using the chain rule, adjusting weights/biases to train the network).
Question 8 · Advanced Theory
6.25 marks
Digital signatures are used to ensure secure communication over a network. (a) Explain the step-by-step process of creating and verifying a digital signature when Alice sends a message to Bob. (b) State the two security properties that are achieved by using a digital signature, explaining how each is ensured.
Show answer & marking schemeHide answer & marking scheme
Worked solution
(a) Step-by-step process: 1. Alice hashes the message to produce a message digest. 2. Alice encrypts the digest with her private key to produce the signature. 3. Alice transmits the signature and the message. 4. Bob decrypts the signature using Alice's public key to get the original digest. 5. Bob hashes the received message to produce a new digest. 6. Bob compares the two digests; if they match, the signature is verified. (b) Security properties: 1. Integrity: Ensured because any message alteration changes the computed hash, making it mismatch the decrypted digest. 2. Authenticity/Non-repudiation: Ensured because only Alice's private key could create a signature decryptable by her public key.
Marking scheme
3.0 marks: Explaining the creation and verification process including key usage (private key for encryption, public key for decryption). 1.5 marks: Explaining Integrity (matching digests to detect alteration). 1.75 marks: Explaining Authenticity (verifying sender's unique ownership of the private key).
Question 9 · Advanced Theory & Optimization Questions
6.25 marks
A computer system represents real numbers using a 12-bit normalized floating-point format: - 8 bits for the mantissa (in two's complement) - 4 bits for the exponent (in two's complement)
Show the normalized floating-point representation for the denary value \(-3.75\) in this format. Show all your working, including how you arrived at both the mantissa and the exponent.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. Convert the absolute denary value \(3.75\) into a binary fraction: \(3.75 = 2^1 + 2^0 + 2^{-1} + 2^{-2} = 11.11_2\).
2. Express this as a normalized positive floating-point number (where the mantissa must start with \(0.1\) to be normalized): \(11.11_2 = 0.1111_2 \times 2^2\). With an 8-bit mantissa, this positive representation is \(0.1111000\).
3. To represent the negative value \(-3.75\), take the two's complement of the positive mantissa: - One's complement of \(0.1111000\) is \(1.0000111\). - Add 1: \(1.0001000\). Since this starts with the bits \(10\) (specifically \(1.0...\)), it is a valid normalized negative mantissa.
4. The exponent is \(+2\). Express this in 4-bit two's complement binary: \(2_{10} = 0010_2\).
5. Combine the results: - Mantissa: \(10001000\) - Exponent: \(0010\)
Marking scheme
- 1.5 marks: Correctly converting \(3.75\) to binary or setting up the initial equation as \(0.1111000 \times 2^2\). - 1.5 marks: Showing the step-by-step process of finding the two's complement of the positive mantissa. - 1.5 marks: Identifying the correct exponent value as \(+2\) (or \(0010\) in binary). - 1.75 marks: Providing the correct final 8-bit mantissa (\(10001000\)) and 4-bit exponent (\(0010\)).
Question 10 · Advanced Theory & Optimization Questions
6.25 marks
Many high-level programming languages compile source code into an intermediate code (such as bytecode) rather than direct machine code. This intermediate code is then executed by a Virtual Machine (VM).
Explain how this approach achieves platform independence, and explain how a Just-In-Time (JIT) compiler optimizes execution performance compared to standard interpretation.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. **Platform Independence**: The compiler translates the source code into a standardized, hardware-independent intermediate code (e.g., bytecode). Any computer system can run this intermediate code as long as it has a Virtual Machine (VM) specifically built for that platform's hardware and operating system. The VM acts as an interpreter or runtime environment, translating the generic intermediate code into the host computer's specific machine instructions.
2. **JIT Compilation Optimization**: Standard interpretation translates intermediate code line-by-line during every execution, which is slow. A Just-In-Time (JIT) compiler monitors the execution of the code. When it detects frequently run sections of bytecode (known as 'hotspots' or loops), it compiles that intermediate code directly into native machine code at runtime. This native code is stored in memory and executed directly by the CPU in future calls, bypassing the slow interpretation phase and significantly improving execution speed.
Marking scheme
- 1.5 marks: Explain intermediate code as a standardized, platform-independent representation compiled once from source. - 1.5 marks: Explain the role of the VM in translating/interpreting intermediate code to platform-specific machine code. - 1.5 marks: Clearly link these to platform independence (one bytecode file runs on any OS/hardware with a compatible VM). - 1.75 marks: Explain how JIT compilation identifies 'hotspots' or repeated code, compiles them to native machine code at runtime, and executes them directly to eliminate interpreter overhead.
Question 11 · Advanced Theory & Optimization Questions
6.25 marks
During the code optimization phase of compilation, compilers transform code to make it execute faster or use fewer resources.
Consider the following pseudocode segment: ``` DECLARE x, y, z : INTEGER x <- 5 y <- 10 FOR i <- 1 TO 1000 z <- x * y + i NEXT i ```
1. Identify the sub-expression within the loop that can be optimized using 'loop-invariant code motion' (frequency reduction). Explain how this optimization is achieved and write the optimized pseudocode. 2. Explain the concept of 'constant folding' and state how it could be applied to further optimize this code segment.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. **Loop-Invariant Code Motion**: - The sub-expression is `x * y`. Because the values of `x` and `y` do not change inside the loop, computing `x * y` during each of the 1000 iterations is highly redundant. - The optimization is achieved by evaluating the expression once before the loop begins and storing the result in a temporary variable, then using that variable inside the loop. - Optimized pseudocode: ``` temp <- x * y FOR i <- 1 TO 1000 z <- temp + i NEXT i ```
2. **Constant Folding**: - Constant folding is an optimization where the compiler simplifies expressions containing constant values at compile time, rather than generating instructions to compute them at run time. - Here, since `x <- 5` and `y <- 10` are constants, the compiler can fold the multiplication `5 * 10` into the single constant `50` during compilation. This completely removes the multiplication operation from runtime execution. Combined with loop-invariant code motion, the code reduces to `FOR i <- 1 TO 1000; z <- 50 + i; NEXT i;`.
Marking scheme
Part 1 (3.25 marks): - 1.0 mark: Correctly identifying `x * y` as the loop-invariant expression. - 1.0 mark: Explaining that moving it outside the loop prevents calculating it 1000 times. - 1.25 marks: Providing valid optimized pseudocode showing the pre-calculation outside the loop.
Part 2 (3.0 marks): - 1.5 marks: Explaining that constant folding computes constant operations at compile time rather than run time. - 1.5 marks: Applying it to the scenario by showing `x * y` (or `5 * 10`) evaluates directly to `50` at compile time, saving CPU cycles at run time.
Question 12 · Advanced Theory & Optimization Questions
6.25 marks
Artificial Neural Networks (ANNs) are key components of modern machine learning architectures.
1. Explain the role of the activation function in an artificial neuron and explain why non-linear activation functions (such as ReLU or Sigmoid) are preferred over linear ones. 2. Describe the backpropagation algorithm, including the role of the loss function and how weights are adjusted during the training process.
Show answer & marking schemeHide answer & marking scheme
Worked solution
1. **Activation Function**: - **Role**: It is a mathematical function applied to the weighted sum of inputs plus bias of a neuron. It determines the output signal (activation level) of the neuron, mapping it to a set range (e.g., 0 to 1 for Sigmoid, or 0 to infinity for ReLU). - **Why non-linear is preferred**: A network using only linear activation functions acts as a single-layer linear model, regardless of how many hidden layers it has, because a linear combination of linear functions is always linear. Non-linear activation functions allow the network to model complex, multi-dimensional, non-linear boundaries and relationships in high-dimensional data.
2. **Backpropagation**: - **Role of Loss Function**: The loss (or cost) function measures the performance of the neural network by calculating the difference between the network's predicted output and the actual target output. - **Weight Adjustment**: During training, data is passed forward through the network (forward propagation) to produce a prediction. The loss function calculates the error. Backpropagation then calculates the gradient of the loss function with respect to each weight in the network by applying the chain rule of calculus, working backward from the output layer to the input layer. An optimization algorithm (like gradient descent) uses these gradients to adjust the weights in the direction that minimizes the loss, gradually improving model accuracy.
Marking scheme
Part 1 (3.0 marks): - 1.5 marks: Explain the role of the activation function (taking weighted inputs plus bias, transforming it to control output signal/range). - 1.5 marks: Explain the importance of non-linearity (allows deep networks to learn non-linear decision boundaries, preventing the network from collapsing into a simple linear system).
Part 2 (3.25 marks): - 1.0 mark: Describe the loss/cost function as the metric measuring the error between predictions and target labels. - 1.0 mark: Explain the backward flow of error gradients calculated using the chain rule. - 1.25 marks: Describe how weights are updated in the direction that minimizes loss, typically using gradient descent.
Paper 41 (Practical Exam)
Program your solutions using Python, Java, or Visual Basic. Save code files and output screenshots inside your evidence document.
3 Question · 75 marks
Question 1 · Interactive Practical Code Solutions
25 marks
An online library management system stores details of books. Standard books can be reserved by anyone, while premium books have membership constraints.
(a) Write class definitions in Python, Java, or Visual Basic for the parent class `Book` with the following private attributes: - `BookID` (String) - `Title` (String) - `Author` (String) - `IsReserved` (Boolean)
Include a constructor that takes `BookID`, `Title`, and `Author` as parameters, and sets `IsReserved` to `False`. Write getters for all four attributes, and a method `Reserve()` that sets `IsReserved` to `True`. [6 marks]
(b) Write a subclass definition for `PremiumBook` that inherits from `Book` and has an additional private attribute: - `MinimumMembershipDays` (Integer)
Write a constructor that takes `BookID`, `Title`, `Author`, and `MinimumMembershipDays` as parameters, and calls the parent constructor. Write a getter for `MinimumMembershipDays`. Write a method `ReservePremium(UserMembershipDays)` which checks if `UserMembershipDays` is greater than or equal to `MinimumMembershipDays`. If so, and the book is not yet reserved, call the parent `Reserve()` method and return `True`. Otherwise, return `False`. [6 marks]
(c) Write a main program where you: - Create a list or array `BookList` containing 3 instances: 1. A standard `Book` with ID "B01", Title "Python Basics", Author "A. Smith". 2. A `PremiumBook` with ID "P01", Title "Advanced AI", Author "B. Jones", MinimumMembershipDays 365. 3. A `PremiumBook` with ID "P02", Title "Deep Learning", Author "C. Ward", MinimumMembershipDays 730. - Write a search procedure `TryReserveBook(BookList, BookID, UserMembershipDays)` that searches for the book with `BookID`. If found and not reserved: - If it is a standard `Book`, call `Reserve()` and output "Standard book reserved successfully." - If it is a `PremiumBook`, call `ReservePremium(UserMembershipDays)`. If successful, output "Premium book reserved successfully."; else output "Reservation failed: insufficient membership days." - If the book is already reserved, display "Book is already reserved." [8 marks]
(d) Test your function in the main program by calling `TryReserveBook` twice: - Reserve "P01" with `UserMembershipDays` = 400. - Reserve "P02" with `UserMembershipDays` = 100. Show your output. [5 marks]
Show answer & marking schemeHide answer & marking scheme
Worked solution
The class definitions employ standard Object-Oriented paradigms (attributes, encapsulation, inheritance). In python, private attributes are declared with double underscores. The subclass `PremiumBook` utilizes `super().__init__` to instantiate base fields. Polymorphic and dynamic checking with `isinstance` allows the search routine to perform class-specific operations on `BookList` objects.
Marking scheme
Part (a): [6 marks total] - 1 mark: Class definition for Book. - 1 mark: Constructor initializing BookID, Title, Author with parameters and IsReserved to False. - 2 marks: Private attributes defined with correct naming/scoping. - 1 mark: All four getters implemented correctly. - 1 mark: Reserve() method updates IsReserved to True.
Part (b): [6 marks total] - 1 mark: Correct inheritance syntax from Book. - 1 mark: MinimumMembershipDays private attribute initialized in subclass constructor. - 1 mark: Parent constructor called via super() / Parent class name. - 1 mark: Getter for MinimumMembershipDays. - 2 marks: ReservePremium() logic checking days, checking reservations, calling parent Reserve(), and returning boolean.
Part (c): [8 marks total] - 1 mark: BookList created with specified instances of Book and PremiumBook. - 2 marks: Correct logic to search BookList by BookID. - 2 marks: Dynamic type check (e.g., isinstance / type cast check) to distinguish standard and premium books. - 2 marks: Correct calling of Reserve() or ReservePremium() and printing specified output strings. - 1 mark: Handling of already reserved books.
Part (d): [5 marks total] - 2 marks: Executing both test runs sequentially. - 3 marks: Correct output shown matching scenario details (P01 successfully reserved, P02 failed reservation).
Question 2 · Interactive Practical Code Solutions
25 marks
A binary search tree can be stored in a 2D global array named `BinaryTree` of dimensions `[0..19, 0..2]` representing 20 nodes. Each row represents a node: - Column 0: Left Pointer (Integer) - Column 1: Data Value (Integer) - Column 2: Right Pointer (Integer)
(a) Declare the 2D global array `BinaryTree` and the global integer variables `RootPointer` and `FreePointer`. Write a procedure `InitializeTree()` that: - Sets `RootPointer` to -1 (representing an empty tree). - Sets `FreePointer` to 0. - Links all nodes in the free list chain where each node's Left Pointer points to the index of the next node, and all other columns are initialized to -1. The last node's Left Pointer must be set to -1. [7 marks]
(b) Write a recursive function `InsertNode(CurrentPointer, NewValue)` that inserts a non-negative integer `NewValue` into the binary search tree. - If the node pointer is -1, allocate a node from the free list (updating `FreePointer`), write values, and return its pointer. - Recursively navigate to the left or right subtree based on binary search rules. - Return the pointer of the current subtree root. [10 marks]
(c) Write a recursive procedure `InOrder(CurrentPointer)` that prints the values of the binary search tree in ascending order. [5 marks]
(d) Write a main program to initialize the tree, insert values 15, 8, 24, 5, 12, 20, 30, and run an in-order traversal to show the sorted output. [3 marks]
Show answer & marking schemeHide answer & marking scheme
Worked solution
This implementation maps a binary tree search structure to a 2D matrix representing pointer-based links. In `InitializeTree()`, the free space uses Left Pointers as elements of a singly linked list pointing forward. `InsertNode` utilizes standard recursive logic where base case handling performs memory-allocation logic directly from `FreePointer`. Traversal is the standard left-root-right pattern.
Marking scheme
Part (a): [7 marks total] - 1 mark: Global array BinaryTree declared of size [0..19, 0..2] or appropriate list representation. - 1 mark: RootPointer and FreePointer declared. - 1 mark: InitializeTree() sets RootPointer to -1 and FreePointer to 0. - 3 marks: Loop links nodes in a chain utilizing Left Pointer (index + 1) and sets other values to -1. - 1 mark: Terminal node points to -1.
Part (b): [10 marks total] - 1 mark: Correct parameters (CurrentPointer, NewValue) defined. - 1 mark: Base case condition checking if CurrentPointer is -1. - 2 marks: Handling free list overflow and updating FreePointer correctly. - 2 marks: Setting correct values in BinaryTree at allocated index (Left = -1, Value = NewValue, Right = -1). - 2 marks: Logic for left navigation: recursive call passing Left pointer and updating current node's Left pointer if needed. - 2 marks: Logic for right navigation: recursive call passing Right pointer and updating current node's Right pointer if needed.
Part (c): [5 marks total] - 1 mark: recursive procedure checks if CurrentPointer is not -1. - 2 marks: First recursive call on left child. - 1 mark: Printing value at CurrentPointer. - 1 mark: Second recursive call on right child.
Part (d): [3 marks total] - 1 mark: Loop calling insert correctly, and updating RootPointer initially. - 1 mark: InOrder procedure called with RootPointer. - 1 mark: Program compiles and outputs: 5, 8, 12, 15, 20, 24, 30.
Question 3 · Interactive Practical Code Solutions
25 marks
A stack data structure can be implemented as a linked list inside an array of Node objects.
(a) Define a class `Node` that has two private properties: - `Data` (String) - `Next` (Integer) Write a constructor that accepts `Data` and `Next` to initialize the properties, and standard getter and setter methods for both. [6 marks]
(b) Define a class `LinkedStack` that has: - A private array `Stack` containing 10 `Node` objects. - A private integer `TopPointer` which points to the top node of the stack. - A private integer `FreePointer` which points to the first free node in the list. Write a constructor for `LinkedStack` that: - Instantiates all 10 `Node` objects inside the array. - Links them together to form a free list (where each node's `Next` points to the index of the next node, and the last node's `Next` is -1). - Sets `TopPointer` to -1. - Sets `FreePointer` to 0. [7 marks]
(c) Write the following public methods for the `LinkedStack` class: - `Push(NewData)`: Adds a node containing `NewData` to the top of the stack. It must check for overflow (if `FreePointer == -1`), output "Stack Overflow!", and return `False`. Otherwise, it updates pointers and returns `True`. - `Pop()`: Removes the top node, returns its string value, and recycles the node back to the free list. If the stack is empty, output "Stack Underflow!" and return an empty string `""`. [8 marks]
(d) Write a main program to: - Instantiate a `LinkedStack` object. - Push "Red", "Green", and "Blue" onto the stack in order. - Pop the top elements twice and display each popped value. [4 marks]
Show answer & marking schemeHide answer & marking scheme
Worked solution
The stack relies on a pre-allocated memory pool of Node objects. Push operations allocate index `FreePointer`, modify its parameters, update the head of the stack `TopPointer`, and shift `FreePointer` forward. Pop operations perform the exact mirror process: extraction of data, moving `TopPointer` down, and placing the node back onto the head of the free list.
Marking scheme
Part (a): [6 marks total] - 1 mark: Class Node defined with correct property scope. - 1 mark: Constructor taking Data and Next. - 2 marks: Getters for both fields implemented. - 2 marks: Setters for both fields implemented.
Part (b): [7 marks total] - 1 mark: Class LinkedStack defined. - 2 marks: LinkedStack constructor instantiating array of 10 nodes. - 2 marks: Free-list initialized correctly, pointing node sequential indices (0 to 9, where 9 -> -1). - 1 mark: TopPointer initialized to -1. - 1 mark: FreePointer initialized to 0.
Part (c): [8 marks total] - 1 mark: Push checks if FreePointer is -1 (overflow) and handles return. - 2 marks: Push takes node from FreePointer, updates FreePointer, sets value/next of new node, and updates TopPointer. - 1 mark: Push returns True if successful. - 1 mark: Pop checks if TopPointer is -1 (underflow) and returns empty string. - 2 marks: Pop reads node at TopPointer, updates TopPointer, and links popped node to FreePointer. - 1 mark: Pop returns string value.
Part (d): [4 marks total] - 1 mark: Stack instantiated. - 1 mark: Elements successfully pushed in order (Red, Green, Blue). - 1 mark: Pop method called twice. - 1 mark: Printed outputs correct (displays 'Blue' then 'Green').
Wondering how well you actually know this?
Thinka is an AI practice app for DSE students — unlimited questions, instant auto-marking, and detailed step-by-step solutions. 100,000+ students use it to confirm they actually know it, not just think they do.