MetadataPastPaper.sampleTitle

For (a):
1. Number of samples per second per channel = 44,100
2. Duration = 10 seconds
3. Channels = 2 (stereo)
4. Bits per sample = 16
Total bits = \( 44,100 \times 10 \times 2 \times 16 = 14,112,000 \) bits.
Convert to bytes: \( 14,112,000 / 8 = 1,764,000 \) bytes.

For (b):
Lossless compression allows the original data to be perfectly reconstructed without any loss of quality. Lossy compression permanently discards less perceptible data to achieve higher compression ratios.
Run-Length Encoding (RLE) compresses data by replacing consecutive runs of identical values with a single data value and count. In a simple cartoon, there are large, contiguous areas of identical pixels, producing high redundancy suitable for RLE. Acoustic audio consists of continuously varying analogue waves; consecutive digital samples are rarely exactly identical, so RLE provides little to no compression and may even increase the file size.

(a) [5.0 Marks total]:
- 1 mark for multiplying by 2 (for stereo channels).
- 1 mark for calculating the total number of bits: 14,112,000 bits.
- 1 mark for dividing the bit count by 8 to convert to bytes.
- 2 marks for the correct final answer: 1,764,000 bytes.

(b) [5.7 Marks total]:
- 2 marks for distinguishing lossy (permanent data loss) and lossless (perfect reconstruction) compression.
- 1.7 marks for explaining that RLE requires runs of identical consecutive values.
- 2 marks for contrasting cartoons (large uniform pixel blocks) with sound (continuously varying wave amplitudes, rarely identical consecutively).

(a) A non-key dependency (transitive dependency) occurs when a non-key attribute determines another non-key attribute rather than depending directly on the primary key. In this table, Player1Name is dependent on Player1ID, and Player2Name is dependent on Player2ID. Since neither Player1ID nor Player2ID is the primary key of the MATCH table, this is a non-key dependency.

(b) To normalize to 3NF:
1. Identify and remove transitive dependencies by creating a new table for players: PLAYER(PlayerID, PlayerName) where PlayerID is the primary key.
2. Redefine the MATCH table to reference the player IDs as foreign keys, removing the redundant names: MATCH(MatchID, TournamentName, MatchDate, Player1ID, Player2ID, WinnerID).
3. Primary Key for MATCH is MatchID. Foreign Keys are Player1ID, Player2ID, and WinnerID, which reference the PlayerID in the PLAYER table.

(a) [4.0 Marks total]:
- 2 marks for defining transitive/non-key dependency (one non-key field determines another non-key field).
- 2 marks for identifying that Player1Name depends on Player1ID and Player2Name depends on Player2ID.

(b) [6.7 Marks total]:
- 2 marks for defining the PLAYER table structure with PlayerID as the primary key.
- 2 marks for updating the MATCH table structure to remove Player names while retaining ID fields.
- 2.7 marks for correctly identifying all Primary Keys (PK) and Foreign Keys (FK).

(a) Fetch stage RTN:
1. MAR <- [PC] (Copy Program Counter to Memory Address Register)
2. PC <- [PC] + 1 (Increment Program Counter)
3. MDR <- [[MAR]] (Load data from memory location in MAR into Memory Buffer Register/Memory Data Register)
4. CIR <- [MDR] (Copy instruction from MDR to Current Instruction Register)

(b) Execution of ADD 150:
1. The address portion of the instruction (150) is copied from the CIR to the MAR: MAR <- [CIR(address)].
2. The computer fetches the data stored in memory address 150 and copies it into the MDR: MDR <- [[MAR]].
3. The value inside the MDR is added to the value currently in the Accumulator (ACC) by the Arithmetic Logic Unit (ALU), and the final result is written back to the Accumulator: ACC <- [ACC] + [MDR].

(a) [5.0 Marks total]:
- 1 mark for MAR <- [PC].
- 1 mark for PC <- [PC] + 1.
- 1 mark for MDR <- [[MAR]] (accept memory access notation).
- 1 mark for CIR <- [MDR].
- 1 mark for correct usage of square brackets representing 'contents of'.

(b) [5.7 Marks total]:
- 2 marks for explaining copying the address operand (150) from CIR to MAR.
- 1.7 marks for fetching the contents of that address (150) into MDR.
- 2 marks for adding the MDR data to ACC and storing the result in ACC.

(a) A disk defragmenter utility reorganizes physical files stored on a hard disk drive. Over time, files become fragmented (stored in non-contiguous blocks across different tracks). The defragmenter moves these blocks so that all fragments of each file are stored contiguously, and groups all free space together. This improves performance because the drive read/write head does not have to move across multiple physical tracks to read a single file, thereby reducing seek and latency times.

(b) Distinctions:
- Static linking: The compiler/linker copies all the required library code directly into the final executable program file at compile-time.
- Dynamic linking: The executable contains only references to the library. The external Dynamic Link Library (DLL) file is loaded into memory only when the program runs.

Advantage of dynamic linking: Smaller executable files are produced, and multiple running applications can share a single copy of the library in memory, saving RAM.
Disadvantage of dynamic linking: If the required DLL file is missing, modified, or has version conflicts (often called DLL hell), the application will fail to run.

(a) [5.0 Marks total]:
- 2 marks for explaining that files are split over non-contiguous sectors and the defragmenter rearranges them contiguously.
- 1 mark for mentioning that free space is grouped together.
- 2 marks for relating contiguous storage to reduced movement of the mechanical read/write head, lowering seek times.

(b) [5.7 Marks total]:
- 2 marks for explaining static linking (compile-time, embedded code) vs dynamic linking (runtime loading, shared code).
- 1.7 marks for a valid advantage of dynamic linking (e.g., memory saving, smaller executables).
- 2 marks for a valid disadvantage (e.g., dependency issues, missing DLL errors).

(a) When a node detects a collision during transmission using CSMA/CD:
1. It immediately stops transmitting the current frame data.
2. It broadcasts a 'jam signal' across the medium to notify all other nodes of the collision.
3. The node generates a random time delay using a back-off algorithm.
4. It waits for this random period of time to elapse.
5. Once the timer expires, the node returns to carrier-sensing mode (listening to the line) before trying to retransmit.

(b) Role of a router:
1. A router receives a packet and reads the destination IP address from the packet's IP header.
2. It queries its internal routing table to determine the most efficient path or next hop for that destination.
3. It updates the packet header (e.g., decrementing the Time-to-Live (TTL) field) and encapsulates it into a new frame.
4. It forwards the packet through the selected physical interface toward the next router.

(a) [5.7 Marks total]:
- 1 mark for stopping data transmission.
- 1 mark for sending a jam signal.
- 2 marks for generating and waiting a random back-off time (must specify 'random' to prevent repeated immediate collisions).
- 1.7 marks for returning to listening/sensing the carrier before attempting retransmission.

(b) [5.0 Marks total]:
- 2 marks for extracting the destination IP address from the packet header.
- 1.5 marks for matching the address with entries in its routing table.
- 1.5 marks for updating headers (such as TTL) and forwarding the packet to the next hop interface.

(a) Working for 01011000 0011:
1. Mantissa: 0.1011000 (positive because the sign bit is 0). Value = \( 0.5 + 0.125 + 0.0625 = 0.6875 \) (or \( 11/16 \)).
2. Exponent: 0011 (positive). Value = \( +3 \).
3. Multiply: Shift the binary point in the mantissa 3 places to the right (equivalent to multiplying by \( 2^3 \)): 0101.1000.
4. Conversion: \( 2^2 + 2^0 + 2^{-1} = 4 + 1 + 0.5 = 5.5 \).

(b) Overflow:
Occurs when the result of a calculation is too large (positive or negative) to be represented in the format. This happens because the positive exponent required exceeds the maximum possible exponent value. Scenario: Multiplying two very large numbers together.
Underflow:
Occurs when a non-zero result of a calculation is too small in magnitude (too close to zero) to be represented. This happens because the negative exponent required is smaller than the minimum possible exponent. Scenario: Dividing a tiny fractional value by a very large number.

(a) [5.0 Marks total]:
- 1 mark for correctly converting the exponent to its denary value (\( +3 \)).
- 1 mark for representing the mantissa as a binary fraction (\( 0.1011_2 \) or \( 11/16 \)).
- 1 mark for showing the correct shifting of the binary point by 3 places (or multiplying by \( 2^3 \)).
- 2 marks for the correct final denary answer of 5.5.

(b) [5.7 Marks total]:
- 2 marks for explaining overflow (exceeding maximum exponent range) and providing a valid scenario.
- 2 marks for explaining underflow (absolute value too small/close to zero for minimum negative exponent range) and providing a valid scenario.
- 1.7 marks for mentioning how fixed exponent bit sizes lead to these boundaries.

(a) A Virtual Machine (VM) is a software emulation of a complete physical computer system. It runs on a host operating system and executes compiled instructions. Intermediate code (e.g., bytecode) is a low-level, non-platform-specific compiled version of source code. The VM acts as an interpreter or Just-In-Time (JIT) compiler, translating this intermediate code into the specific native machine code of the host system during execution, enabling cross-platform compatibility.

(b) Benefits:
1. Portability (Write Once, Run Anywhere): The same intermediate bytecode can run on any physical machine that has a compatible VM installed without modification.
2. Security / Isolation: The VM acts as a 'sandbox', protecting the host machine from crashes or malicious actions caused by the executing code.

Drawbacks:
1. Performance Overhead: Interpreting intermediate code or running an entire emulation layer consumes additional CPU cycles and memory, resulting in slower execution speeds compared to native compiled machine code.

(a) [5.7 Marks total]:
- 2 marks for defining a Virtual Machine (software-emulated hardware/sandboxed environment).
- 2 marks for explaining intermediate code as a platform-independent, low-level instruction set.
- 1.7 marks for explaining the VM's role in translating intermediate code to the physical host CPU's instruction set.

(b) [5.0 Marks total]:
- 2 marks for explaining two distinct benefits (1 mark per benefit: portability, security/isolation, easy debugging).
- 2 marks for explaining one distinct drawback (performance overhead/emulation penalty, higher memory usage).
- 1 mark for contrasting with native direct-to-metal compilation.

To search for the TargetID in the Inventory array, the loop must continue as long as we have not reached the end of the array and the item has not been found yet. Thus, is 'Found = FALSE' or 'NOT Found'.
Inside the loop, we check if the current product's ProductID matches TargetID. Hence, is 'Inventory[Index].ProductID = TargetID'.
If a match is found, the stock level is updated by adding Quantity, so is 'Inventory[Index].StockLevel + Quantity'.
If not found, we increment the index to check the next record, meaning is 'Index + 1'.
After the loop, if the product was never found, we output an error message. This check requires to be 'Found = FALSE' or 'NOT Found'.

Award marks as follows:
- 1.875 marks for Blank A: Correct loop condition (Found = FALSE or NOT Found).
- 1.875 marks for Blank B: Correct comparison of record field with TargetID (Inventory[Index].ProductID = TargetID).
- 1.875 marks for Blank C: Correct update calculation (Inventory[Index].StockLevel + Quantity).
- 1.875 marks for Blank D: Correct increment of index (Index + 1).
- 1.875 marks for Blank E: Correct check to see if never found (Found = FALSE or NOT Found).

Before popping, we check if the stack is empty. An empty stack is indicated when `TopPointer` is 0. Thus, is 'TopPointer = 0' or 'TopPointer < 1'.
To retrieve the item, we copy the item at the top of the stack to the `Item` parameter, so is 'StackData[TopPointer]'.
We then update the `TopPointer` to point to the next element down by decrementing it, making 'TopPointer - 1'.
Finally, since the operation succeeded, we return true, meaning is 'TRUE'.

Award marks as follows:
- 2.34 marks for Blank A: Correctly check if the stack is empty (TopPointer = 0 or TopPointer < 1).
- 2.345 marks for Blank B: Correctly retrieve the item at the top of the stack (StackData[TopPointer]).
- 2.345 marks for Blank C: Correctly decrement the stack pointer (TopPointer - 1).
- 2.345 marks for Blank D: Correctly return success (TRUE).

In a binary search, the loop must continue as long as the search boundaries are valid, which is when Low is less than or equal to High. Thus, is 'Low <= High'.
The midpoint is calculated by taking the integer division of the sum of the low and high bounds, making '(Low + High) DIV 2' or 'INT((Low + High) / 2)'.
If the target is found at the midpoint index, we return this index, so is 'Mid'.
If the value at Mid is larger than our target, the target must be in the lower half, so we adjust High to 'Mid - 1' for .
Otherwise, the target is in the upper half, so we adjust Low to 'Mid + 1' for .

Award marks as follows:
- 1.875 marks for Blank A: Correct loop condition (Low <= High).
- 1.875 marks for Blank B: Correct midpoint calculation using integer division ((Low + High) DIV 2 or equivalent).
- 1.875 marks for Blank C: Correct return value when target is found (Mid).
- 1.875 marks for Blank D: Correct upper boundary adjustment (Mid - 1).
- 1.875 marks for Blank E: Correct lower boundary adjustment (Mid + 1).

The loop must iterate through the file until the end of file (EOF) of 'Students.txt' is reached. Thus, is 'NOT EOF("Students.txt")'.
Inside the loop, the next line from the file must be read into the Record variable, so is 'READFILE "Students.txt", Record'.
If the status of the record is "Active", we write the record to the output file, making 'WRITEFILE "ActiveStudents.txt", Record'.
Finally, after the loop terminates, the output file must be properly closed, meaning is 'CLOSEFILE "ActiveStudents.txt"'.

Award marks as follows:
- 2.34 marks for Blank A: Correctly check for end of file (NOT EOF("Students.txt")).
- 2.345 marks for Blank B: Correct syntax for reading a file line (READFILE "Students.txt", Record).
- 2.345 marks for Blank C: Correct syntax for writing a record to a file (WRITEFILE "ActiveStudents.txt", Record).
- 2.345 marks for Blank D: Correct statement to close the output file (CLOSEFILE "ActiveStudents.txt").

The queue has a maximum capacity of 10 elements. Thus, we check if the queue is full by evaluating if `NumItems = 10`. Therefore, is 'NumItems = 10' or 'NumItems >= 10'.
To insert in a circular array of size 10, the TailPointer must advance circularly, which can be expressed as : '(TailPointer MOD 10) + 1'.
Since a new item is added, we increment the total item count, making 'NumItems + 1'.
As the operation was successful, we return true, meaning is 'TRUE'.

Award marks as follows:
- 2.34 marks for Blank A: Correct full check condition (NumItems = 10 or NumItems >= 10).
- 2.345 marks for Blank B: Correct mathematical formula for circular index advancement ((TailPointer MOD 10) + 1).
- 2.345 marks for Blank C: Correctly incrementing the item counter (NumItems + 1).
- 2.345 marks for Blank D: Correct success return value (TRUE).

The base case for the recursion occurs when there are no more positive even numbers to add. This happens when `N` is less than or equal to 0 (or less than 2, as 2 is the smallest positive even number). Thus, is 'N <= 0' or 'N < 2'.
If `N` is even, we want to add `N` to the sum of the remaining even numbers from the recursive call. Hence, is 'N + SumEven(N - 1)' (or 'N + SumEven(N - 2)').
If `N` is odd, we do not add `N` and simply pass the reduction step down to the next integer, so is 'SumEven(N - 1)'.

Award marks as follows:
- 3.125 marks for Blank A: Correct base case condition (N <= 0 or N < 2 or equivalent).
- 3.125 marks for Blank B: Correct recursive call when N is even (N + SumEven(N - 1) or N + SumEven(N - 2)).
- 3.125 marks for Blank C: Correct recursive call when N is odd (SumEven(N - 1)).

In a Bubble Sort, the inner loop index compares elements at `Inner` and `Inner + 1`, meaning the upper bound of the loop must be one less than the current unsorted portion limit. Thus, is 'Outer - 1'.
Since we want descending order, we should swap elements if the current element's score is less than the next element's score. Therefore, is 'Scores[Inner, 2] < Scores[Inner + 1, 2]'.
To complete swapping the Player IDs (Column 1), we must assign the value from `Scores[Inner + 1, 1]` to `Scores[Inner, 1]`. Thus, is 'Scores[Inner, 1] <- Scores[Inner + 1, 1]'.
If a swap has occurred, we must flag `Swapped` as true, so is 'TRUE'.
After each complete pass, the outer limit of unsorted items decreases by one, which makes 'Outer - 1'.

Award marks as follows:
- 1.875 marks for Blank A: Correct limit for the Inner loop (Outer - 1).
- 1.875 marks for Blank B: Correct comparison for a descending order sort (Scores[Inner, 2] < Scores[Inner + 1, 2]).
- 1.875 marks for Blank C: Correct instruction to complete the Column 1 swap (Scores[Inner, 1] <- Scores[Inner + 1, 1]).
- 1.875 marks for Blank D: Correctly setting Swapped flag to true (TRUE).
- 1.875 marks for Blank E: Correct decrement of the Outer boundary variable (Outer - 1).

First, the function checks if there are empty slots in the free list. A null representation of 0 means there are no free nodes, so is 'FreeListPointer = 0'.
We then take the node from the free list and advance the free list pointer to the next free node, so is 'LinkedList[FreeListPointer].Pointer'.
To maintain alphabetical order during traversal, we iterate as long as the current node's value is alphabetically smaller than our new item. Thus, is 'LinkedList[CurrentPointer].Data < NewItem'.
During list traversal, we move to the next node by setting `CurrentPointer` to the current node's pointer field, so is 'LinkedList[CurrentPointer].Pointer'.
Finally, if inserting in the middle or at the end, the previous node's pointer must point to our new node, making 'LinkedList[PreviousPointer].Pointer <- NewNodePointer'.

Award marks as follows:
- 1.875 marks for Blank A: Correct check for a full list / no free nodes (FreeListPointer = 0).
- 1.875 marks for Blank B: Correct extraction of the next free list node (LinkedList[FreeListPointer].Pointer).
- 1.875 marks for Blank C: Correct sorted search comparison (LinkedList[CurrentPointer].Data < NewItem).
- 1.875 marks for Blank D: Correct linked list traversal assignment (LinkedList[CurrentPointer].Pointer).
- 1.875 marks for Blank E: Correct reference assignment of the preceding pointer (LinkedList[PreviousPointer].Pointer <- NewNodePointer).

First, convert -3.375 to binary. We know +3.375 is 11.011 in binary. Expressing this in normalized positive binary format gives 0.110110000000 * 2^2. The exponent is +2, which in 4-bit two's complement is 0010. To find the normalized negative mantissa, we take the two's complement of 0.110110000000: first invert the bits to get 1.001001111111, then add 1 to the least significant bit, giving 1.001010000000. Thus, the 12-bit mantissa is 100101000000 and the 4-bit exponent is 0010. Normalizing a floating-point number ensures that there are no leading redundant sign bits (except the single required sign bit), which leaves the maximum possible number of bits in the mantissa available to represent the fractional part, thereby maximizing precision.

1 mark for expressing the binary equivalent of 3.375. 1 mark for correct positive normalized mantissa representation. 1 mark for applying two's complement correctly to obtain the negative mantissa. 1 mark for the correct 4-bit exponent. 1 mark for correct final combined binary values. 1.8 marks for a clear explanation of how normalization eliminates leading redundant sign bits to maximize mantissa capacity for the fractional value.

Prolog first attempts the base rule: route(london, berlin, Total) :- flight(london, berlin, Total). Since there is no direct flight fact for london to berlin, this fails. Prolog then backtracks to the recursive rule: route(london, berlin, Total) :- flight(london, Z, C1), route(Z, berlin, C2), Cost is C1 + C2. Prolog finds the fact flight(london, paris, 120), binding Z to paris and C1 to 120. Prolog then recursively evaluates route(paris, berlin, C2). For this recursive call, Prolog first attempts the base rule: flight(paris, berlin, C2). This matches the direct flight fact flight(paris, berlin, 150), binding C2 to 150. Prolog returns to the caller and evaluates Total is 120 + 150, which calculates Total = 270. The final query succeeds with Total = 270.

2 marks for explaining the failure of the initial direct route check and backtracking to the recursive rule. 2 marks for tracing the recursive call with correct binding of variable Z to paris and Cost C1 to 120. 1 mark for correctly matching the recursive call to the direct flight of paris to berlin with Cost C2 as 150. 1.8 marks for correctly tracing the arithmetic calculation of Total = 120 + 150 = 270.

For an input n, the loop runs from 1 to n, performing n additions. The return statement performs 1 addition with the recursive call. Therefore, the recursive step performs n + 1 additions. This gives the recurrence relation T(n) = T(n-1) + n + 1, with T(1) = 0. Unrolling this relation: T(n) = T(n-1) + n + 1 = T(n-2) + (n) + (n+1) = T(1) + sum_{k=2}^{n} (k + 1) = 0 + sum_{k=2}^{n} k + sum_{k=2}^{n} 1 = [n(n+1)/2 - 1] + (n - 1) = 0.5 n^2 + 0.5 n - 1 + n - 1 = 0.5 n^2 + 1.5 n - 2. Since the highest power of n is 2, the Big-O complexity is O(n^2). This quadratic complexity signifies that as the input size n grows, the number of operations increases quadratically, making the algorithm highly inefficient for large values of n.

2 marks for establishing the recurrence relation T(n) = T(n-1) + n + 1 with base case T(1) = 0. 2 marks for the correct algebraic steps in solving the summation. 1 mark for identifying the closed-form equation as 0.5 n^2 + 1.5 n - 2. 1.8 marks for identifying O(n^2) complexity and explaining its significance in algorithm design.

The allocated block 192.168.16.0/20 contains 4096 addresses. Using Variable Length Subnet Masking (VLSM), we allocate starting with the largest subnet: (1) Subnet A: 500 hosts. The smallest power of 2 greater than 500 is 512 (2^9). This requires 9 host bits, leaving 23 network bits. Prefix: /23. Mask: 255.255.254.0. Range: 192.168.16.0 to 192.168.17.255. (2) Subnet B: 250 hosts. Smallest power of 2 greater than 250 is 256 (2^8). This requires 8 host bits, leaving 24 network bits. Prefix: /24. Mask: 255.255.255.0. Range: 192.168.18.0 to 192.168.18.255. (3) Subnet C: 100 hosts. Smallest power of 2 greater than 100 is 128 (2^7). This requires 7 host bits, leaving 25 network bits. Prefix: /25. Mask: 255.255.255.128. Range: 192.168.19.0 to 192.168.19.127. (4) Subnet D: 50 hosts. Smallest power of 2 greater than 50 is 64 (2^6). This requires 6 host bits, leaving 26 network bits. Prefix: /26. Mask: 255.255.255.192. Range: 192.168.19.128 to 192.168.19.191. The mathematical relationship is that a prefix of length P leaves 32 - P host bits. The maximum host capacity is 2^(32 - P) - 2 (subtracting 2 for the network address and broadcast address).

2 marks for Subnet A design (correct prefix, mask, range). 1 mark for Subnet B design. 1 mark for Subnet C design. 1 mark for Subnet D design. 1.8 marks for explaining the formula 2^(32 - P) - 2 and defining the role of network/broadcast addresses.

First, compute the weighted sum z: z = (x1 * w1) + (x2 * w2) + (x3 * w3) + b = (0.5 * 0.4) + (-1.2 * 0.5) + (0.8 * -0.3) + 0.1 = 0.2 - 0.6 - 0.24 + 0.1 = -0.54. Next, apply the activation function: y = ReLU(-0.54) = max(0, -0.54) = 0. During backpropagation, a loss function (like Mean Squared Error) calculates the gradient of the error with respect to the weights using the chain rule: dL/dw_i = (dL/dy) * (dy/dz) * (dz/dw_i). Since the derivative of the ReLU function for any negative z is 0 (dy/dz = 0), the gradient dL/dw_i becomes 0. Consequently, no weight updates will happen for this neuron on this training step. This is known as the 'dying ReLU' problem, where inactive neurons cannot learn because they pass zero gradient back.

2 marks for the correct mathematical calculation of the weighted sum z = -0.54. 1 mark for the correct application of the ReLU activation function yielding y = 0. 2 marks for detailing the backpropagation chain rule and explaining why the derivative is zero. 1.8 marks for identifying and explaining the implications of the 'dying ReLU' issue on weight updates.

(a) Modulus n = p * q = 3 * 11 = 33. Totient phi(n) = (p - 1)(q - 1) = 2 * 10 = 20. (b) We need d * 3 mod 20 = 1. The smallest value that satisfies this is d = 7 (since 7 * 3 = 21, and 21 mod 20 = 1). (c) The encryption formula is C = M^e mod n. Thus, C = 5^3 mod 33 = 125 mod 33. Since 33 * 3 = 99, 125 - 99 = 26. So C = 26. (d) RSA is based on a trapdoor one-way function. Multiplication of two large primes is easy (one-way), but factoring the product n back into p and q is computationally infeasible without additional information. The prime factors p and q serve as the 'trapdoor' (the secret shortcut); knowing them allows the easy calculation of the totient phi(n) and the private key d. Without this trapdoor, finding d is virtually impossible.

1.5 marks for correct n = 33 and phi(n) = 20. 1.5 marks for finding d = 7 with clear working. 2 marks for correct calculation of C = 26 showing step-by-step modular arithmetic. 1.8 marks for explaining how prime factorization acts as a trapdoor one-way function to secure the algorithm.

(a) Page size = 4 KiB = 4096 bytes = 2^12 bytes. Therefore, 12 bits are needed for the page offset. (b) Number of virtual pages: Virtual address is 24 bits. Offset is 12 bits, leaving 24 - 12 = 12 bits for the virtual page number (VPN). Number of pages = 2^12 = 4096. Number of physical frames: Physical address is 20 bits. Offset is 12 bits, leaving 20 - 12 = 8 bits for physical frame number (PFN). Number of frames = 2^8 = 256. (c) For virtual address 0x3A5B2F: the page offset is the lower 12 bits (3 hex digits) which is 0xB2F. The VPN is the upper 12 bits (3 hex digits) which is 0x3A5. Given VPN 0x3A5 maps to frame 0xC2 (which is 8 bits, 2 hex digits), we concatenate the frame number and the offset to get physical address 0xC2B2F. (d) The TLB is a high-speed cache inside the CPU that stores recent virtual-to-physical address mappings. When a translation is needed, the CPU checks the TLB first. A TLB hit avoids querying the multi-level page table in main memory, saving memory access cycles.

1 mark for calculating offset bits = 12. 1 mark for calculating virtual pages = 4096 and physical frames = 256. 2 marks for translating the hexadecimal address correctly to 0xC2B2F with clear step-by-step logic. 1.8 marks for explaining the TLB's role as a cache to minimize memory access latency.

(a) SJF schedules shortest first: P3 runs 0 to 4 ms, P2 runs 4 to 10 ms, P1 runs 10 to 28 ms. RR (quantum 5 ms): P1 runs 0 to 5 ms, P2 runs 5 to 10 ms, P3 runs 10 to 14 ms, P1 runs 14 to 19 ms, P2 runs 19 to 20 ms, P1 runs 20 to 28 ms. (b) SJF waiting times: P3 = 0 ms, P2 = 4 ms, P1 = 10 ms. Average = (0 + 4 + 10)/3 = 4.67 ms. RR waiting times: P1 waiting time is 10 ms (ran 0-5, 14-19, 20-28, so turnaround 28 - burst 18 = 10 ms). P2 waiting time is 14 ms (ran 5-10, 19-20, so turnaround 20 - burst 6 = 14 ms). P3 waiting time is 10 ms (ran 10-14, so turnaround 14 - burst 4 = 10 ms). Average = (10 + 14 + 10)/3 = 11.33 ms. (c) SJF has higher efficiency for average waiting time (4.67 ms vs 11.33 ms) but can cause starvation for longer jobs. RR is fairer because it guarantees equal CPU allocation to all processes but has higher average waiting time and context-switching overhead.

2 marks for describing correct execution order/time blocks for both SJF and RR. 2 marks for correct calculations of waiting times for each individual process. 1 mark for calculating correct average waiting times (4.67 ms and 11.33 ms). 1.8 marks for comparing efficiency (average waiting time) and fairness (preventing starvation).

(a) The mantissa is 01101000. Since the most significant bit is 0, it is a positive number. Placing the binary point after the first bit gives \(0.1101000\). In decimal, this is \(0.5 + 0.25 + 0.0625 = 0.8125\). The exponent is 0011, which represents the decimal value \(3\). The overall value is \(0.8125 \times 2^{3} = 0.8125 \times 8 = 6.5\). (b) Increasing the exponent size to 5 bits increases the range of numbers that can be represented (both larger and smaller numbers). Decreasing the mantissa size to 7 bits reduces the precision of the represented numbers. (c) Normalization ensures that there is a unique binary representation for each non-zero real number, preventing multiple representations. It also maximizes the precision of the represented number by using the available bits of the mantissa as efficiently as possible.

(a) [3 marks total]: 1 mark for correct conversion of mantissa to decimal (\(0.8125\)), 1 mark for correct conversion of exponent to decimal (\(3\)), 1 mark for correct final calculation (\(6.5\)). (b) [2 marks total]: 1 mark for stating that range is increased, 1 mark for stating that precision is decreased. (c) [2 marks total]: 1 mark for stating it provides a unique representation for each number, 1 mark for stating it maximizes precision / makes efficient use of mantissa bits.

(a) A /22 CIDR prefix means that the first 22 bits of the subnet mask are set to 1, and the remaining 10 bits are set to 0. In binary: 11111111.11111111.11111100.00000000. Converting to dotted decimal notation gives 255.255.252.0. (b) The number of host bits is \(32 - 22 = 10\). The total number of addresses is \(2^{10} = 1024\). Subtracting the network address and the broadcast address, the number of usable host addresses is \(2^{10} - 2 = 1022\). (c) (i) Dividing the block into 4 equal subnets requires adding \(\log_2(4) = 2\) bits to the prefix length. The new prefix length is \(22 + 2 = 24\) (written as /24). (ii) The first subnet begins at 192.168.4.0/24. The network address is 192.168.4.0 and the broadcast address is 192.168.4.255. Therefore, the range of usable host IP addresses is from 192.168.4.1 to 192.168.4.254.

(a) [2 marks total]: 1 mark for correct third octet (252), 1 mark for full correct subnet mask (255.255.252.0). (b) [2 marks total]: 1 mark for calculating \(2^{10}\) or 1024, 1 mark for subtracting 2 to yield 1022. (c) [3 marks total]: (i) 1 mark for correctly determining the /24 prefix. (ii) 2 marks for host range: 1 mark for starting address 192.168.4.1, 1 mark for ending address 192.168.4.254.

(a) The evaluation function formula is \(f(n) = g(n) + h(n)\). Where: \(f(n)\) is the total estimated path cost through node \(n\); \(g(n)\) is the actual cost incurred to reach node \(n\) from the start node; \(h(n)\) is the estimated cost from node \(n\) to the goal node (the heuristic value). (b) An admissible heuristic is one that never overestimates the actual cost to reach the goal node. It is crucial because admissibility guarantees that the A* algorithm will always find the mathematically optimal (shortest) path to the goal if one exists. (c) If \(h(n) = 0\) for all nodes, the evaluation function becomes \(f(n) = g(n)\). The A* search algorithm behaves exactly like Dijkstra's algorithm (performing an unguided uniform-cost search). It will still find the optimal path, but it will be much less efficient because it will explore many more nodes in all directions, increasing time and space complexity.

(a) [3 marks total]: 1 mark for stating the correct formula \(f(n) = g(n) + h(n)\), 1 mark for defining \(g(n)\) as actual path cost from start, 1 mark for defining \(h(n)\) as estimated cost to goal. (b) [2 marks total]: 1 mark for explaining admissibility (never overestimates actual cost), 1 mark for stating it guarantees finding the optimal path. (c) [2 marks total]: 1 mark for stating it behaves like Dijkstra's algorithm / uniform-cost search, 1 mark for explaining that performance degrades / runs slower / expands more nodes.

```python
class Package:
def __init__(self, package_id, weight, destination):
self.__PackageID = package_id
self.__Weight = weight
self.__Destination = destination

def get_package_id(self):
return self.__PackageID

def get_weight(self):
return self.__Weight

def get_destination(self):
return self.__Destination

def CalculateCost(self):
return self.__Weight * 1.50


class ExpressPackage(Package):
def __init__(self, package_id, weight, destination, rapid_service, express_fee):
super().__init__(package_id, weight, destination)
self.__RapidService = rapid_service
self.__ExpressFee = express_fee

def CalculateCost(self):
cost = super().CalculateCost() + self.__ExpressFee
if self.__RapidService:
cost += 10.00
return cost


# Main program
Shipments = [None] * 5

# Instantiate objects
Shipments[0] = Package('PKG01', 4.5, 'Paris')
Shipments[1] = ExpressPackage('EXP02', 2.0, 'London', True, 5.50)

def DisplayShipments():
for pkg in Shipments:
if pkg is not None:
print(f'ID: {pkg.get_package_id()} | Destination: {pkg.get_destination()} | Cost: ${pkg.CalculateCost():.2f}')

DisplayShipments()
```

Marking Scheme (Total: 25 Marks):

**Package Class Definition (7 Marks)**
- 1 Mark: Correctly defining the class `Package`.
- 2 Marks: Private attributes declared/initialized (`__PackageID`, `__Weight`, `__Destination`).
- 1 Mark: Constructor with parameters initializing attributes.
- 2 Marks: Implementation of all getters.
- 1 Mark: `CalculateCost()` returning correct base calculation.

**ExpressPackage Class Definition (8 Marks)**
- 1 Mark: Class `ExpressPackage` correctly inherits from `Package`.
- 2 Marks: Private attributes (`__RapidService`, `__ExpressFee`) defined.
- 2 Marks: Constructor correctly accepts all parameters and calls `super().__init__`.
- 3 Marks: Overridden `CalculateCost()` calls base cost calculation, adds `ExpressFee`, and conditionally adds 10.00.

**Main Program & Array Manipulation (10 Marks)**
- 1 Mark: Array `Shipments` declared with size 5 (or equivalent 5-element list in Python initialized to empty/None).
- 2 Marks: Standard `Package` instantiated correctly with requested parameters and added to array.
- 2 Marks: `ExpressPackage` instantiated correctly with requested parameters and added to array.
- 2 Marks: Correct declaration of procedure `DisplayShipments()`.
- 2 Marks: `DisplayShipments()` loops through non-null entries and prints correct data calling getters and `CalculateCost()`.
- 1 Mark: Program runs and successfully outputs the correct cost values ($6.75 and $18.50 respectively).

```python
# Global arrays and variables
LeftPointer = [0] * 10
Data = [0] * 10
RightPointer = [0] * 10
RootPointer = -1
FreePointer = 0

def InitializeTree():
global FreePointer, RootPointer
RootPointer = -1
FreePointer = 0
for i in range(9):
LeftPointer[i] = i + 1
Data[i] = -1
RightPointer[i] = -1
LeftPointer[9] = -1
Data[9] = -1
RightPointer[9] = -1

def InsertNode(CurrentNode, NewValue):
global FreePointer, RootPointer, LeftPointer, RightPointer, Data

# If the tree or branch is empty
if CurrentNode == -1:
if FreePointer == -1:
print('Tree is full')
return -1

# Get a free node
newNode = FreePointer
FreePointer = LeftPointer[FreePointer]

# Initialize the new node
Data[newNode] = NewValue
LeftPointer[newNode] = -1
RightPointer[newNode] = -1
return newNode

if NewValue < Data[CurrentNode]:
LeftPointer[CurrentNode] = InsertNode(LeftPointer[CurrentNode], NewValue)
elif NewValue > Data[CurrentNode]:
RightPointer[CurrentNode] = InsertNode(RightPointer[CurrentNode], NewValue)

return CurrentNode

def PostOrder(CurrentNode):
if CurrentNode != -1:
PostOrder(LeftPointer[CurrentNode])
PostOrder(RightPointer[CurrentNode])
print(Data[CurrentNode])

# Main Program
InitializeTree()
RootPointer = InsertNode(RootPointer, 50)
RootPointer = InsertNode(RootPointer, 30)
RootPointer = InsertNode(RootPointer, 70)
RootPointer = InsertNode(RootPointer, 40)

print('Post-order traversal results:')
PostOrder(RootPointer)
```

Marking Scheme (Total: 25 Marks):

**Initial setup and arrays declaration (4 Marks)**
- 1 Mark: Correct global arrays `LeftPointer`, `Data`, `RightPointer` initialized to size 10.
- 1 Mark: Global variables `RootPointer` and `FreePointer` declared and initialized.
- 2 Marks: `InitializeTree()` correctly links `LeftPointer` elements to represent the free list and sets final pointers to -1.

**Insertion Algorithm (12 Marks)**
- 2 Marks: Correctly checking if the free list is empty (`FreePointer == -1`) and handling appropriately.
- 2 Marks: Extracting node index from `FreePointer` and advancing `FreePointer`.
- 2 Marks: Assigning the value to `Data[newNode]` and setting its children pointers to -1.
- 3 Marks: Correct recursive call of `InsertNode` when value is smaller (traversing left).
- 3 Marks: Correct recursive call of `InsertNode` when value is larger (traversing right).

**Traversal Procedure (5 Marks)**
- 1 Mark: `PostOrder(CurrentNode)` recursive procedure header established.
- 1 Mark: Correctly checks base case condition (`CurrentNode != -1`).
- 1 Mark: Recursive call for left subtree: `PostOrder(LeftPointer[CurrentNode])`.
- 1 Mark: Recursive call for right subtree: `PostOrder(RightPointer[CurrentNode])`.
- 1 Mark: Outputting the data after children traversal (Root printed last).

**Main Program (4 Marks)**
- 1 Mark: Initializing tree before insertions.
- 2 Marks: Correctly inserting elements and updating `RootPointer` during insertion operations.
- 1 Mark: Printing output showing correct traversal values (expected: 40, 30, 70, 50).

```python
# Global variables
StackData = [''] * 10
TopPointer = -1

def Push(ItemValue):
global TopPointer, StackData
if TopPointer >= 9:
print('Stack overflow: Stack is full.')
return False
else:
TopPointer += 1
StackData[TopPointer] = ItemValue
return True

def Pop():
global TopPointer, StackData
if TopPointer == -1:
return 'EMPTY'
else:
item = StackData[TopPointer]
TopPointer -= 1
return item

def SearchStack(SearchItem, CurrentIndex):
global TopPointer, StackData
# Base Case 1: Search exceeded active stack items
if CurrentIndex > TopPointer:
return -1
# Base Case 2: Found the item
if StackData[CurrentIndex] == SearchItem:
return CurrentIndex
# Recursive step
return SearchStack(SearchItem, CurrentIndex + 1)

# Main Program to demonstrate functionality
Push('Apple')
Push('Banana')
Push('Cherry')
Push('Date')
Push('Elderberry')

search_target = 'Cherry'
pos = SearchStack(search_target, 0)
if pos != -1:
print(f'Item {search_target} found at index: {pos}')
else:
print(f'Item {search_target} not found.')

print('Popping items from stack:')
for i in range(6):
print(f'Popped: {Pop()}')
```

Marking Scheme (Total: 25 Marks):

**Global Declarations (2 Marks)**
- 1 Mark: Correctly defining `StackData` array of size 10.
- 1 Mark: Initializing `TopPointer` to -1.

**Push Function (6 Marks)**
- 2 Marks: Checking if stack is full correctly (e.g., index reaches boundary size - 1) and outputting message.
- 1 Mark: Returning `False` if stack is full.
- 1 Mark: Correctly incrementing `TopPointer`.
- 1 Mark: Assigning `ItemValue` to `StackData[TopPointer]`.
- 1 Mark: Returning `True` upon successful push.

**Pop Function (6 Marks)**
- 2 Marks: Checking if stack is empty (e.g., `TopPointer == -1`).
- 1 Mark: Returning `'EMPTY'` if stack is empty.
- 1 Mark: Storing the value from the top of the stack in a variable.
- 1 Mark: Correctly decrementing `TopPointer`.
- 1 Mark: Returning the stored value.

**Recursive SearchStack Function (8 Marks)**
- 1 Mark: Parameter definition correct (`SearchItem`, `CurrentIndex`).
- 2 Marks: Correct base case returning -1 when search index exceeds stack boundary limits/`TopPointer`.
- 2 Marks: Correct base case returning `CurrentIndex` when value is found.
- 2 Marks: Correct recursive call passing `CurrentIndex + 1` to search the next stack slot.
- 1 Mark: Standard non-destructive nature of the search preserved (elements not popped).

**Main Program (3 Marks)**
- 1 Mark: Demonstrating pushes of elements to stack.
- 1 Mark: Demonstrating search of elements showing returned indexes.
- 1 Mark: Demonstrating pops showing proper empty stack condition handling at the end.