2025 Cambridge IAL Computer Science (9618) 模擬試題連答案詳解

Part (a):
1. Convert positive 91 to binary: \(91 = 64 + 16 + 8 + 2 + 1 = 01011011_2\).
2. Find the one's complement: \(10100100_2\).
3. Add 1 to find the two's complement: \(10100101_2\).

Part (b):
Addition working:
01101100
+ 00110101
= 10100001

Explanation of overflow:
- The MSB (sign bit) of both inputs is 0, indicating both numbers are positive (\(+108\) and \(+53\)).
- The MSB of the result is 1, representing a negative number in two's complement.
- Adding two positive numbers cannot yield a negative result, indicating arithmetic overflow. This occurs because the true sum (\(+161\)) exceeds the maximum representable positive signed 8-bit integer limit of \(+127\).

Part (c):
- Application: Electronic calculators, cash registers, or digital clocks.
- Reason: BCD prevents rounding errors that occur when converting fractional denary values to binary (e.g. 0.1 cannot be represented exactly in standard binary), or it allows direct and simple translation to output on decimal decimal/7-segment displays.

Part (a): [3 marks]
- 1 mark for correct binary representation of +91 (01011011)
- 1 mark for correct one's complement (10100100)
- 1 mark for correct final two's complement (10100101)

Part (b): [4 marks]
- 1 mark for correct binary addition result (10100001)
- 1 mark for showing working with correct carries
- 1 mark for stating that the sum (+161) exceeds the maximum limit (+127)
- 1 mark for noting that two positive numbers added together gave a negative result (MSB changed to 1)

Part (c): [2 marks]
- 1 mark for identifying a valid application (e.g. calculator displays, financial transaction systems)
- 1 mark for a valid reason (e.g. prevents fractional rounding errors, simpler decoding for 7-segment displays)

Part (a):
1. Execution Location: Client-side scripts (e.g., JavaScript) are executed directly on the user's local web browser. Server-side scripts (e.g., PHP, Python, ASP) are executed on the remote web server before the HTML is sent to the client.
2. Access & Security: Client-side scripts cannot access resources on the server (like databases) and are visible to the user (via view source). Server-side scripts can access secure databases, keep credentials hidden from the client, and run background processes.

Part (b):
1. Addressing Space: IPv4 only provides approximately 4.3 billion addresses, which are nearly exhausted. IPv6 uses 128-bit addresses, offering an virtually inexhaustible supply of IP addresses for IoT devices.
2. Built-in Security and Efficiency: IPv6 includes native support for IPSec (for encryption/authentication) and has simplified packet headers to improve routing efficiency.

Part (c):
- A router acts as a gateway connecting different networks.
- It receives incoming data packets and extracts the destination IP address from the packet header.
- It looks up the destination in its routing table to determine the optimal next hop/path.
- It forwards the packet along that path toward its final destination.

Part (a): [4 marks]
- Max 2 marks per difference. Award 1 mark for the feature in client-side and 1 mark for the corresponding contrast in server-side.
- Examples: Execution location (browser vs. server), access to database/files (local restrictions vs. server databases), security of source code (visible to user vs. hidden behind server execution).

Part (b): [2 marks]
- 1 mark for mentioning the depletion of available IPv4 addresses / requirement for more addresses.
- 1 mark for stating another technical benefit (e.g., more efficient routing due to simplified headers, built-in security features/IPSec, elimination of NAT requirement).

Part (c): [3 marks]
- 1 mark for explaining that the router reads the destination IP address from the incoming packet.
- 1 mark for mentioning the use of a routing table to determine the best path.
- 1 mark for stating that it forwards the packet to the next node/router/destination network.

Part (a):
1. A drum inside the printer is given a uniform electrostatic charge.
2. A laser beam is directed at the drum via a rotating mirror, discharging specific areas to create a latent electrostatic image.
3. The drum is coated with toner (charged ink powder), which only clings to the charged (or discharged) parts of the drum representing the image.
4. Paper is fed through and given a stronger charge, pulling the toner off the drum onto the paper.
5. The paper passes through a fuser (heated rollers), which melts the toner, fusing it permanently to the paper fibers.

Part (b):
- A capacitive screen consists of glass layers coated with a transparent conductive material (like Indium Tin Oxide) that holds a continuous electrostatic charge.
- When a conductive object, such as a human finger, touches the screen, it alters the electrostatic field and causes a localized change in capacitance.
- Sensors located at the corners/edges of the screen measure this change in current/capacitance and calculate the exact coordinates of the touch.

Part (c):
- Speed: SSDs have significantly faster read/write speeds (near-instant startup/load times) because there is no latency from rotating platters or read/write head movement.
- Physical durability: SSDs have no moving parts, making them highly resistant to physical shocks and damage if the laptop is dropped.
- Power consumption: SSDs use much less electrical energy, which extends laptop battery life and generates less heat.

Part (a): [4 marks]
- 1 mark for charging the drum (electrostatic charge).
- 1 mark for the laser discharging specific parts of the drum to create the image.
- 1 mark for toner sticking to the charged areas of the drum.
- 1 mark for using heat and pressure (fuser) to fuse the toner onto the paper.

Part (b): [2 marks]
- 1 mark for stating that the screen has a conductive/electrostatic layer and the human finger is also conductive.
- 1 mark for explaining that touching the screen changes the electrical current/capacitance, which is measured by sensors to determine the coordinates.

Part (c): [3 marks]
- 1 mark for faster data transfer speeds (lower latency).
- 1 mark for higher reliability/robustness due to no moving parts.
- 1 mark for lower power consumption / less heat generated.

Part (a):
(i) Program Counter (PC): Holds the address of the next instruction to be fetched and executed. It is automatically incremented during the fetch cycle to point to the subsequent instruction.
(ii) Memory Data Register (MDR): Acts as a buffer register that holds the data or instruction currently being transferred between the CPU and the main memory (RAM).

Part (b):
1. The address currently held in the Program Counter (PC) is copied to the Memory Address Register (MAR) via the Address Bus.
2. The Program Counter (PC) is incremented by 1 to point to the next instruction in sequence.
3. A read signal is sent along the Control Bus, causing the instruction stored at the address in the MAR to be loaded from main memory into the Memory Data Register (MDR) via the Data Bus.
4. The instruction stored in the MDR is copied into the Current Instruction Register (CIR) where it will be decoded.

Part (c):
- The Status Register (SR) contains status flags (e.g., Carry, Overflow, Zero, Negative) that are set or cleared by the ALU depending on the outcome of the last operation. These flags are used to make decisions during conditional branch instructions.

Part (a): [4 marks]
- (i) 1 mark for holding the address of the next instruction, 1 mark for stating that it increments.
- (ii) 1 mark for acting as a buffer / temporarily holding data, 1 mark for specifying that it handles data moving to/from memory.

Part (b): [4 marks]
- 1 mark for copying address from PC to MAR.
- 1 mark for incrementing the PC.
- 1 mark for transferring the instruction from the memory location in MAR to the MDR.
- 1 mark for copying the instruction from MDR to CIR.

Part (c): [1 mark]
- 1 mark for explaining that it contains status flags/bits (e.g., Zero, Carry) indicating the outcome of arithmetic/logical operations (used for conditional branching).

Part (a):
(i) Error Reporting:
- Compiler: Processes the entire source code file first. If there are syntax errors, it compiles a complete report of all errors found and fails to produce an executable until all are fixed.
- Interpreter: Translates and executes line-by-line. If a syntax error is reached, execution halts immediately at that line, making it easier to pinpoint the exact location during development.
(ii) Execution Speed:
- Compiler: Produces a standalone executable file of native machine code. It runs very rapidly since no translation is required at runtime.
- Interpreter: Must translate each instruction into machine code every time the program runs, making execution significantly slower.

Part (b):
- Over time, files on an HDD become fragmented, meaning their data blocks are stored in non-adjacent sectors across the disk platters.
- The defragmenter utility scans the disk and physically relocates these scattered file sectors so that all blocks of each file are stored in continuous/contiguous sectors.
- It also groups free space together.
- This improves performance because the physical read/write head of the HDD does not have to move back and forth across different tracks to read a single file, minimizing disk head seek time and drive wear.

Part (c):
- Memory efficiency: Multiple programs can share a single copy of a DLL loaded into RAM, saving memory.
- Disk space: Code is not duplicated across multiple executable files on disk.
- Maintainability: The DLL can be updated/patched independently without recompiling the entire parent applications.

Part (a): [4 marks]
- (i) 1 mark for compiler reporting all errors at the end, 1 mark for interpreter stopping immediately at the first error.
- (ii) 1 mark for compiler producing fast machine code, 1 mark for interpreter being slower due to line-by-line translation at runtime.

Part (b): [4 marks]
- 1 mark for explaining how files become fragmented (stored in non-contiguous sectors over time).
- 1 mark for explaining that the defragmenter moves blocks of files so they are stored adjacently/contiguously.
- 1 mark for mentioning that free space is also consolidated.
- 1 mark for explaining that this reduces physical drive head movement (seek time), increasing read/write performance.

Part (c): [1 mark]
- 1 mark for a valid benefit (e.g., saves RAM by sharing code, reduces overall executable file size, allows modular updates of software without re-compilation).

Part (a):
- Bob has a key pair: a public key (accessible to anyone) and a private key (known only to Bob).
- Alice obtains Bob's public key and uses it to encrypt the sensitive message.
- Because of the mathematical properties of asymmetric cryptography, a message encrypted with a public key can only be decrypted by the matching private key.
- Since only Bob possesses his private key, only Bob can decrypt and read the message, ensuring absolute confidentiality.

Part (b):
- Purpose: To ensure authenticity (the message definitely came from the stated sender) and integrity (the message was not modified in transit), preventing non-repudiation.
- Verification process:
1. The sender creates a cryptographic hash of the message, encrypts this hash with their own private key to generate the digital signature, and sends both the message and signature.
2. The recipient decrypts the digital signature using the sender's public key to retrieve the original hash.
3. The recipient independently calculates a new hash of the received message using the same hashing algorithm.
4. The recipient compares the retrieved hash with the newly calculated hash. If they are identical, the signature is verified, proving the message is authentic and unaltered.

Part (c):
- Before transmission, the sender applies a mathematical formula to the data payload to calculate a checksum value (a numerical sum of the bytes), which is appended to the block of data.
- Upon receipt, the receiving system extracts the data and applies the exact same mathematical formula to calculate its own checksum.
- The receiver compares its calculated checksum against the transmitted checksum. If there is any mismatch, it indicates that the data was corrupted during transit.

Part (a): [3 marks]
- 1 mark for stating that Alice uses Bob's public key to encrypt the message.
- 1 mark for stating that the message can only be decrypted using Bob's matching private key.
- 1 mark for explaining that because only Bob has the private key, confidentiality is preserved (interceptors cannot read it).

Part (b): [4 marks]
- 1 mark for identifying the purpose: verification of identity (authenticity) or detection of tampering (integrity).
- 1 mark for explaining that the sender encrypts a message hash using their private key to create the signature.
- 1 mark for explaining that the recipient decrypts this signature with the sender's public key.
- 1 mark for explaining that the recipient calculates their own hash of the message and compares them for a match.

Part (c): [2 marks]
- 1 mark for explaining that the sender runs an algorithm on the data block to generate a checksum value that is sent alongside the data.
- 1 mark for explaining that the receiver re-calculates the checksum and compares it; any difference indicates a corruption/transmission error.

Part (a):
1. Source Code Access: Open Source software provides full access to the source code, allowing users to study, modify, and improve it. Freeware does not provide access to the source code (it is closed source).
2. User Rights: Users of Open Source software have the freedom to redistribute modified versions of the software. Users of Freeware are permitted to use the software for free but are restricted from modifying, reverse-engineering, or redistributing the software for commercial gain.

Part (b):
- License Type: Shareware.
- Characteristics:
- The software is initially distributed for free, usually with a built-in evaluation/trial period (e.g., 30 days) or limited functionality (nag screens, watermarks, disabled features).
- After the trial period expires, the user is ethically or technically required to pay a registration fee (purchase a license) to continue using the software or unlock the complete feature set.
- The source code remains proprietary and copyrighted by the developer.

Part (c):
- To provide clear ethical guidance to computer professionals on how to make decisions when facing moral dilemmas (e.g., data privacy, safety-critical systems).
- To safeguard the public interest, ensure safety, and protect the rights of users and clients.
- To maintain the professional status, credibility, integrity, and public reputation of the computer science profession.

Part (a): [4 marks]
- Max 2 marks per difference. Award 1 mark for the Open Source aspect and 1 mark for the Freeware contrast.
- Point 1: Source code access (Open source allows viewing/modification of source code vs. Freeware keeps it compiled and hidden).
- Point 2: Redistribution rights (Open source allows modification and redistribution vs. Freeware prohibits modifying or redistributing for commercial use).

Part (b): [3 marks]
- 1 mark for identifying the license type as **Shareware**.
- 1 mark for mentioning the trial period or restricted/limited-feature functionality.
- 1 mark for explaining that payment is required after the trial to continue using the full version, whilst copyright is retained.

Part (c): [2 marks]
- 1 mark for mentioning protection of the public / ensuring user safety and privacy.
- 1 mark for maintaining high professional standards / keeping the credibility of the association and providing a framework for ethical decision-making.

Part (a):
- Referential integrity is a database property ensuring that relationships between tables remain consistent. Specifically, any foreign key value in one table must have a matching, valid primary key value in the corresponding parent table (or be NULL).
- It is enforced by DBMS-level rules (foreign key constraints). For example, if a user attempts to delete a parent record, the database will block the deletion (or cascade the delete) if there are matching child records, preventing orphaned records.

Part (b):
(i) Second Normal Form (2NF):
- The database table must already satisfy First Normal Form (1NF) requirements (atomic values, primary key, no repeating groups).
- It must have no partial key dependencies. This means every non-key attribute must depend on the whole primary key (and not just a part of it, which applies to composite keys).
(ii) Third Normal Form (3NF):
- The database table must already satisfy Second Normal Form (2NF) requirements.
- It must have no transitive dependencies. This means that non-prime attributes must not depend on other non-prime attributes; they must depend only on the primary key.

Part (c):
To define a foreign key constraint in standard SQL DDL (usually during CREATE TABLE or ALTER TABLE):
FOREIGN KEY (StudentID) REFERENCES Student(StudentID)
(Note: An alternative using ALTER TABLE is also acceptable, e.g., ALTER TABLE Enrollment ADD FOREIGN KEY (StudentID) REFERENCES Student(StudentID);)

Part (a): [3 marks]
- 1 mark for defining referential integrity (ensuring foreign keys always point to valid, existing primary keys / no orphaned records).
- 1 mark for explaining that it is enforced using foreign key constraints.
- 1 mark for explaining the enforcement mechanism (e.g., blocking deletions of referenced records, or cascading deletes/updates to prevent breaking links).

Part (b): [4 marks]
- (i) 1 mark for stating it must be in 1NF. 1 mark for explaining the elimination of partial dependencies (every attribute must depend on the entire primary key).
- (ii) 1 mark for stating it must be in 2NF. 1 mark for explaining the elimination of transitive dependencies (non-key attributes cannot depend on other non-key attributes).

Part (c): [2 marks]
- 1 mark for using the correct keywords FOREIGN KEY and REFERENCES with correct parenthesization.
- 1 mark for specifying the correct fields and tables in order: FOREIGN KEY (StudentID) REFERENCES Student(StudentID) (either as part of a table definition or an ALTER TABLE statement).

FUNCTION ProcessScores(Scores : ARRAY OF INTEGER, NumStudents : INTEGER, BYREF PerfectCount : INTEGER) RETURNS REAL
DECLARE TotalPassScore : INTEGER
DECLARE PassCount : INTEGER
DECLARE Index : INTEGER
DECLARE Average : REAL

TotalPassScore <- 0
PassCount <- 0
PerfectCount <- 0

FOR Index <- 1 TO NumStudents
IF Scores[Index] = 100 THEN
PerfectCount <- PerfectCount + 1
ENDIF
IF Scores[Index] >= 50 THEN
TotalPassScore <- TotalPassScore + Scores[Index]
PassCount <- PassCount + 1
ENDIF
ENDFOR

IF PassCount > 0 THEN
Average <- TotalPassScore / PassCount
ELSE
Average <- -1.0
ENDIF

RETURN Average
ENDFUNCTION

1 mark: Correct function header with appropriate parameters and types, including BYREF for `PerfectCount` and return type REAL.
1 mark: Declaring all internal variables with correct data types.
1 mark: Initialising accumulator variables (`TotalPassScore`, `PassCount`, `PerfectCount`) to 0.
2 marks: Correct loop structure from 1 to `NumStudents` to iterate through the array.
1 mark: Checking if the score is equal to 100 and incrementing `PerfectCount`.
1 mark: Checking if the score is greater than or equal to 50.
1 mark: Correctly accumulating the total score and incrementing the count for passing students.
1 mark: Correct conditional check after the loop to prevent division by zero.
1 mark: Correct calculation of average and returning it (or returning -1.0 if no passes).
0.71 marks: Correct syntax for function ending (`ENDFUNCTION`).

PROCEDURE Push(NewItem : STRING)
IF TopPointer >= 100 THEN
OUTPUT "Stack Overflow"
ELSE
TopPointer <- TopPointer + 1
StackData[TopPointer] <- NewItem
ENDIF
ENDPROCEDURE

1.71 marks: Correct procedure header taking a string parameter.
2 marks: Correct boundary check to determine if stack is full (`TopPointer >= 100` or `TopPointer = 100`).
2 marks: Outputting "Stack Overflow" when the stack is full.
2 marks: Correctly incrementing `TopPointer` in the `ELSE` block.
2 marks: Correctly storing `NewItem` at the new `TopPointer` index of `StackData`.
1 mark: Correct syntax for the conditional structure (`IF ... ELSE ... ENDIF`) and procedure ending (`ENDPROCEDURE`).

FUNCTION ExtractDomain(EmailAddress : STRING) RETURNS STRING
DECLARE AtIndex : INTEGER
DECLARE AtCount : INTEGER
DECLARE Index : INTEGER
DECLARE Length : INTEGER
DECLARE Char : STRING

Length <- LENGTH(EmailAddress)
AtCount <- 0
AtIndex <- 0

FOR Index <- 1 TO Length
Char <- MID(EmailAddress, Index, 1)
IF Char = "@" THEN
AtCount <- AtCount + 1
AtIndex <- Index
ENDIF
ENDFOR

IF AtCount <> 1 THEN
RETURN "INVALID"
ENDIF

IF AtIndex = 1 OR AtIndex = Length THEN
RETURN "INVALID"
ENDIF

RETURN MID(EmailAddress, AtIndex + 1, Length - AtIndex)
ENDFUNCTION

1 mark: Correct function header with string parameter and string return type.
1 mark: Declaring all necessary internal variables.
2 marks: Loop to count '@' symbols and record the position of the '@' symbol.
2 marks: Checking if the count of '@' symbols is exactly 1, returning "INVALID" if not.
2 marks: Checking if the '@' symbol is at the first or last character position, returning "INVALID" if so.
2 marks: Correctly extracting the substring from `AtIndex + 1` to the end of the string using standard function `MID`.
0.71 marks: Correct return statements and correct end function structure.

FUNCTION FindMinInRow(Grid : ARRAY OF INTEGER, RowIndex : INTEGER) RETURNS SearchResult
DECLARE Result : SearchResult
DECLARE Col : INTEGER

Result.MinValue <- Grid[RowIndex, 1]
Result.ColIndex <- 1

FOR Col <- 2 TO 10
IF Grid[RowIndex, Col] < Result.MinValue THEN
Result.MinValue <- Grid[RowIndex, Col]
Result.ColIndex <- Col
ENDIF
ENDFOR

RETURN Result
ENDFUNCTION

1.71 marks: Correct function header specifying the 2D array and integer parameters, and returning `SearchResult`.
1 mark: Declaring a local variable of type `SearchResult` and loop counter.
2 marks: Initialising `Result.MinValue` and `Result.ColIndex` to the first column elements of the given row.
2 marks: Setting up a loop from column 2 to 10.
2 marks: Correctly comparing each element in the row with the current minimum (`Grid[RowIndex, Col] < Result.MinValue`).
1 mark: Updating both fields of the `Result` record if a smaller value is found.
1 mark: Correctly returning the record variable and ending the function.

PROCEDURE FilterHighAchievers()
DECLARE Line : STRING
DECLARE Name : STRING
DECLARE ScoreStr : STRING
DECLARE Score : INTEGER
DECLARE CommaPos : INTEGER
DECLARE Index : INTEGER
DECLARE HighAchieverCount : INTEGER

HighAchieverCount <- 0
OPENFILE "Students.txt" FOR READ
OPENFILE "HighAchievers.txt" FOR WRITE

WHILE NOT EOF("Students.txt")
READFILE "Students.txt", Line
CommaPos <- 0
FOR Index <- 1 TO LENGTH(Line)
IF MID(Line, Index, 1) = "," THEN
CommaPos <- Index
ENDIF
ENDFOR

IF CommaPos > 0 THEN
Name <- MID(Line, 1, CommaPos - 1)
ScoreStr <- MID(Line, CommaPos + 1, LENGTH(Line) - CommaPos)
Score <- TO_INTEGER(ScoreStr)

IF Score >= 90 THEN
WRITEFILE "HighAchievers.txt", Name
HighAchieverCount <- HighAchieverCount + 1
ENDIF
ENDIF
ENDWHILE

CLOSEFILE "Students.txt"
CLOSEFILE "HighAchievers.txt"

OUTPUT "Total High Achievers: ", HighAchieverCount
ENDPROCEDURE

1 mark: Correctly opening both files with appropriate modes.
1 mark: Correct loop structure using `WHILE NOT EOF("Students.txt")`.
2 marks: Correct algorithm to find the comma position in the read line.
2 marks: Correct extraction of `Name` (substring before comma) and `ScoreStr` (substring after comma).
1 mark: Correct conversion of `ScoreStr` to an integer.
1 mark: Correct validation check for score >= 90.
1 mark: Correctly writing the name to `HighAchievers.txt` and incrementing the counter.
1 mark: Correctly closing both files.
0.71 marks: Correctly outputting the count and ending the procedure.

PROCEDURE SortProducts(BYREF ProductList : ARRAY OF Product)
DECLARE Outer : INTEGER
DECLARE Inner : INTEGER
DECLARE Temp : Product
DECLARE Swapped : BOOLEAN
DECLARE Limit : INTEGER

Limit <- 50
REPEAT
Swapped <- FALSE
FOR Inner <- 1 TO Limit - 1
IF ProductList[Inner].Price > ProductList[Inner + 1].Price THEN
Temp <- ProductList[Inner]
ProductList[Inner] <- ProductList[Inner + 1]
ProductList[Inner + 1] <- Temp
Swapped <- TRUE
ENDIF
ENDFOR
Limit <- Limit - 1
UNTIL Swapped = FALSE OR Limit = 1
ENDPROCEDURE

1.71 marks: Correct procedure header taking `ProductList` by reference.
1 mark: Declaring local variables (`Outer`, `Inner`, `Temp` of type `Product`, `Swapped` of type `BOOLEAN`).
2 marks: Correct outer loop (using `REPEAT...UNTIL` or `FOR` loop) to manage passes.
2 marks: Correct inner loop traversing the active part of the array (`1` to `Limit - 1`).
2 marks: Correct comparison of prices of adjacent elements (`ProductList[Inner].Price > ProductList[Inner + 1].Price`).
2 marks: Correct swap logic using a temporary variable `Temp` of type `Product` and setting the swap flag.
0.1 marks: Clean syntax ending loop structures and procedure.

FUNCTION Power(Base : INTEGER, Exponent : INTEGER) RETURNS INTEGER
IF Exponent = 0 THEN
RETURN 1
ELSE
RETURN Base * Power(Base, Exponent - 1)
ENDIF
ENDFUNCTION

1.71 marks: Correct function header with parameters and return type.
3 marks: Correct base case checking if `Exponent = 0` and returning 1.
4 marks: Correct recursive step (`Base * Power(Base, Exponent - 1)`).
2 marks: Proper implementation of `IF ... ELSE ... ENDIF` conditions and function endings, without infinite recursion.

1. Represent -3.625 in binary: -3.625 = -(2^1 + 2^0 + 2^{-1} + 2^{-3}) = -11.101 in binary. 2. To normalize this negative number, the mantissa must lie in the range [-1, -0.5). This means the first two bits must be different (i.e., 10... for a negative number). 3. We can write -3.625 as -0.90625 * 2^2. 4. Now convert the normalized mantissa -0.90625 to 8-bit two's complement: Since -0.90625 = -1 + 0.09375 = -1 + 2^{-4} + 2^{-5}, this gives the binary representation 1.0011000 (8 bits). Verify: -1 + 0.0625 + 0.03125 = -0.90625. This is correct. 5. Convert the exponent +2 to 4-bit two's complement: +2 in binary is 0010. 6. Combine the mantissa and exponent to get the final representation: 10011000 0010.

1.25 marks: Identifying the binary representation of -3.625 or showing working. 1.25 marks: Normalizing the value to find the correct power of 2 (exponent value of +2). 1.25 marks: Converting the exponent +2 to a 4-bit two's complement value (0010). 1.25 marks: Converting the negative mantissa to normalized two's complement form (10011000). 1.25 marks: Final correct 12-bit sequence (10011000 0010) with correct division between mantissa and exponent.

Initial state: State S0, Tape: [1] 0 1 B. Step 1: Read 1 in State S0. Rule (S0, 1) -> (0, R, S0) applies. Write 0, move Right, change state to S0. Current tape: 0 [0] 1 B. Step 2: Read 0 in State S0. Rule (S0, 0) -> (1, R, S0) applies. Write 1, move Right, change state to S0. Current tape: 0 1 [1] B. Step 3: Read 1 in State S0. Rule (S0, 1) -> (0, R, S0) applies. Write 0, move Right, change state to S0. Current tape: 0 1 0 [B]. Step 4: Read B in State S0. Rule (S0, B) -> (B, L, S1) applies. Write B, move Left, change state to S1. Current tape: 0 1 [0] B. Step 5: Read 0 in State S1. Rule (S1, 0) -> (1, L, HALT) applies. Write 1, move Left, change state to HALT. Current tape: 0 [1] 1 B. The machine halts. The final tape contents are 0 1 1.

1.25 marks: Correctly tracing the first three transitions under state S0. 1.25 marks: Correctly transitioning on blank symbol B at Step 4. 1.25 marks: Correctly executing the transition under state S1 at Step 5. 1.25 marks: Correctly identifying the final halted state and final position of the head. 1.25 marks: Correctly stating the final tape contents (0 1 1).

Part (a): The ADD instruction writes its result to register R1 in the Write Back (WB) stage (Cycle 5). The SUB instruction needs to read the value of R1 in its Instruction Decode (ID) stage (Cycle 3). Since SUB attempts to read R1 before ADD has written it back, it will read stale data. This is a Read-After-Write (RAW) data hazard. Part (b): The hazard is detected during the ID stage of the SUB instruction by comparing its source register with the destination register of the active ADD instruction. Operand forwarding resolves this by passing the computed result of the ADD instruction directly from the EX/MEM pipeline register to the ALU input for the SUB instruction's EX stage, bypassing the write-back step and avoiding any pipeline stalls.

1.25 marks: Identifying the hazard as a Read-After-Write (RAW) data hazard. 1.25 marks: Explaining the write-back vs read stage timing conflict. 1.25 marks: Stating the hazard is detected in the ID stage. 1.25 marks: Explaining that operand forwarding routes the value directly from the EX/MEM pipeline register. 1.25 marks: Explaining that this bypasses the register file write-back and avoids stalls.

Start at A: g(A)=0, f(A)=6. Open List: [(A, f=6)]. Step 1: Expand A. Successors: B with g(B)=2, f(B)=2+4=6; C with g(C)=5, f(C)=5+2=7. Open List: [(B, f=6), (C, f=7)]. Step 2: Expand B (lowest f). Successors: C via B with g(C)=4, f(C)=4+2=6 (updates old f(C)=7); D with g(D)=8, f(D)=8+0=8. Open List: [(C, f=6), (D, f=8)]. Step 3: Expand C (lowest f). Successor: D via C with g(D)=4+3=7, f(D)=7+0=7 (updates old f(D)=8). Open List: [(D, f=7)]. Step 4: Expand D. Goal reached! Optimal path is A -> B -> C -> D with actual cost 7.

1.25 marks: Correctly calculating f(B)=6 and f(C)=7 in Step 1. 1.25 marks: Expanding B next and updating C's cost to 4 (f(C)=6). 1.25 marks: Calculating the path cost to D through B as 8 (f(D)=8). 1.25 marks: Expanding C and updating D's cost to 7 (f(D)=7). 1.25 marks: Terminating at D and identifying the path A -> B -> C -> D with cost 7.

To resolve cousin(william, Who), the interpreter matches the cousin rule: cousin(william, Who) :- parent(A, william), parent(B, Who), sibling(A, B). 1. It evaluates parent(A, william), binding A = charles. 2. It evaluates parent(B, Who). To satisfy sibling(charles, B), the interpreter resolves sibling(charles, B) :- parent(Z, charles), parent(Z, B), charles \= B. 3. It finds parent(elizabeth, charles), binding Z = elizabeth. 4. It finds parent(elizabeth, B) where B is not charles, which yields B = anne. 5. Now it resolves parent(anne, Who) from the cousin rule, which binds Who = peter. 6. Upon backtracking, it finds the next match for parent(anne, Who), binding Who = zara. This yields the final solutions Who = peter and Who = zara.

1.25 marks: Stating the rule substitution with X = william and Y = Who. 1.25 marks: Binding A = charles from parent(charles, william). 1.25 marks: Resolving sibling(charles, B) to find B = anne using parent(elizabeth, charles) and parent(elizabeth, anne). 1.25 marks: Evaluating parent(anne, Who) to find the first binding Who = peter. 1.25 marks: Explaining backtracking to find the second binding Who = zara.

1. Alice's Steps: Alice passes the original document through a cryptographic hash function to produce a unique, fixed-size value called a message digest. Alice encrypts this message digest using her own private key. This encrypted hash is the digital signature. Alice appends the digital signature to the original document and sends both to Bob. 2. Bob's Steps: Bob receives the document and the appended digital signature. Bob decrypts the digital signature using Alice's public key to retrieve the original message digest. Bob independently passes the received document through the same cryptographic hash function to compute his own message digest. Bob compares the decrypted message digest with his newly calculated message digest. If the two hashes match, Bob is assured of the document's integrity and Alice's authenticity (non-repudiation).

1.25 marks: Explaining Alice generates a hash/message digest from the document using a hash function. 1.25 marks: Specifying Alice encrypts this hash using her private key to produce the digital signature. 1.25 marks: Explaining Bob decrypts the digital signature using Alice's public key to obtain the original hash. 1.25 marks: Explaining Bob computes his own hash of the received document using the same hash function. 1.25 marks: Detailing Bob compares both hashes; a match proves integrity and authenticity/non-repudiation.

Part (a): The Symbol Table is a central database used by the compiler to keep track of information about source code identifiers (such as variable names, function names) and their associated attributes. Three types of information stored: 1) Identifier Name/Lexeme, 2) Data Type (e.g. INTEGER), 3) Scope/Lifetime (e.g. Local/Global), 4) Memory Allocation Details (relative address). Part (b): A hash table is used because it provides near-constant time efficiency O(1) on average for lookup, insertion, and update of identifiers. Since multiple identifiers can hash to the same index (a collision), the implementation must handle collisions. Common methods include Chaining (using a linked list at each hash bucket) or Open Addressing (probing subsequent slots like linear probing, quadratic probing, or double hashing until an empty slot is found).

1.25 marks: Defining the purpose of the symbol table as storing properties of identifiers for semantic analysis and code generation. 1.25 marks: Listing three correct items stored in the symbol table (Name, Data Type, Scope, Address). 1.25 marks: Explaining that a hash table is used for near constant-time O(1) efficiency. 1.25 marks: Describing Chaining (linked lists) as a collision resolution method. 1.25 marks: Describing Open Addressing (probing) as an alternative collision resolution method.

Part (a): Algorithm A (Linear Search) has a Best-case complexity of O(1) when the target is the first element, and a Worst-case complexity of O(N) when the target is at the end or absent. Algorithm B (Binary Search) has a Best-case complexity of O(1) when the target is the middle element, and a Worst-case complexity of O(log N) when the target is at the final leaf/subdivision or absent. Part (b): Binary search works by dividing the search interval in half. Let N be the initial size of the array. After 1 step, the size of the search space is N/2. After 2 steps, it is N/4. After k steps, the size of the search space is N / (2^k). In the worst case, the search space is reduced to 1 element, so we set N / (2^k) = 1, which implies 2^k = N. Taking the base-2 logarithm of both sides gives k = log_2(N) steps. Since the maximum number of comparison steps is directly proportional to log_2(N), the worst-case time complexity is O(log N).

1.25 marks: Stating best-case and worst-case complexities for Algorithm A (O(1) and O(N)) with brief justifications. 1.25 marks: Stating best-case and worst-case complexities for Algorithm B (O(1) and O(log N)) with brief justifications. 1.25 marks: Explaining that Binary Search halves the remaining search space at each iteration. 1.25 marks: Formulating the search space size after k steps as N / (2^k). 1.25 marks: Solving the equation 2^k = N to obtain k = log_2(N) and concluding that this represents O(log N) complexity.

(i) To represent \(-6.25_{10}\): First, convert the positive value \(6.25\) to binary, which is \(110.01_2\). In fixed-point form, the positive representation is \(0110.0100_2\). The two's complement of this value is obtained by inverting the bits and adding 1: \(1001.1100_2\) (since \(-8 + 1 + 0.5 + 0.25 = -6.25\)). To normalize this negative number, the first two bits of the mantissa must be different (i.e., start with '10'). Currently, the binary point is after the sign bit: \(1.0011100\). To make it equal to the target value, we shift the binary point 3 places to the right, which corresponds to multiplying by \(2^3\). Thus, the normalized mantissa is \(1.0011100\) and the exponent is \(+3\). In 4-bit two's complement, \(+3\) is represented as \(0011\). Combine them to get Mantissa: 10011100, Exponent: 0011. (ii) Underflow occurs when a calculation produces a non-zero result that is too close to zero to be represented with the smallest possible exponent. For a normalized positive floating-point number in this system, the smallest possible mantissa starts with '01', which is \(01000000\) representing \(0.5_{10}\). The minimum exponent in 4-bit 2's complement is \(-8\) (binary \(1000\)). The smallest positive normalized real value is therefore \(0.5 \times 2^{-8} = 2^{-1} \times 2^{-8} = 2^{-9}\), which equals \(1/512\) or \(0.001953125_{10}\).

Part (i): [Total 4.25 marks] - Convert positive 6.25 to binary (1 mark). - Convert to 2's complement fixed-point form (1 mark). - Correctly shift and normalize to obtain negative mantissa 10011100 (1.25 marks). - Correct 4-bit exponent 0011 (1 mark). Part (ii): [Total 2 marks] - Clear explanation of underflow (too small to represent, exponent at minimum) (1 mark). - Correct smallest normalized positive value as 2^(-9) or 1/512 (1 mark).

(i) Converting \( (A + B) \times (C - D / E) \) to postfix (RPN): First, evaluate sub-expressions according to operator precedence. The addition is grouped: \((A + B)\) becomes \(A B +\). The division takes precedence inside the second bracket: \(D / E\) becomes \(D E /\). The subtraction in the second bracket becomes \(C D E / -\). Finally, the multiplication combines both parts: \(A B + C D E / - *\). (ii) To evaluate the expression, the interpreter processes the RPN string from left to right: Operands are pushed onto the stack. When an operator is encountered, the top two items are popped (where the first popped is the right operand and the second is the left operand), the operation is executed, and the result is pushed back onto the stack. Trace with values A=4, B=6, C=12, D=8, E=2: Step 1: Token 'A' (4) -> Push 4. Stack: [4]. Step 2: Token 'B' (6) -> Push 6. Stack: [4, 6]. Step 3: Token '+' -> Pop 6, Pop 4. Evaluate 4 + 6 = 10. Push 10. Stack: [10]. Step 4: Token 'C' (12) -> Push 12. Stack: [10, 12]. Step 5: Token 'D' (8) -> Push 8. Stack: [10, 12, 8]. Step 6: Token 'E' (2) -> Push 2. Stack: [10, 12, 8, 2]. Step 7: Token '/' -> Pop 2, Pop 8. Evaluate 8 / 2 = 4. Push 4. Stack: [10, 12, 4]. Step 8: Token '-' -> Pop 4, Pop 12. Evaluate 12 - 4 = 8. Push 8. Stack: [10, 8]. Step 9: Token '*' -> Pop 8, Pop 10. Evaluate 10 * 8 = 80. Push 80. Stack: [80]. Final answer is 80.

Part (i): [Total 2.25 marks] - Correct conversion of (A + B) to RPN (0.75 marks). - Correct conversion of (C - D / E) to RPN with proper precedence (0.75 marks). - Correct final RPN expression: A B + C D E / - * (0.75 marks). Part (ii): [Total 4 marks] - Explanation of stack operation (pushing operands, popping two for operations, pushing result back) (1.5 marks). - Correct step-by-step stack trace showing the intermediate contents (2 marks). - Correct final result of 80 (0.5 marks).

(i) A data hazard occurs when instructions that are overlapping in execution pipeline have data dependencies, and the source operand for a subsequent instruction is not yet available because the preceding instruction has not finished writing to it. (ii) The hazard in the snippet is a Read-After-Write (RAW) data hazard. The 'ADD' instruction updates register 'R1', which is immediately read by the 'SUB' instruction. In a 5-stage pipeline without operand forwarding: Cycle 1: ADD is in IF. Cycle 2: ADD is in ID, SUB is in IF. Cycle 3: ADD is in EX, SUB is in ID. At this point, SUB needs the value of R1, but ADD will not write it to R1 until its WB stage. If split-phase register access is used (where register writes occur in the first half of a clock cycle and reads in the second half), ADD writes the updated R1 in the first half of Cycle 5, allowing SUB to safely read it in the second half of Cycle 5. Therefore, SUB's ID stage is stalled during Cycles 3 and 4, resulting in 2 stall cycles (or 2 NOPs). If split-phase access is NOT used, ADD completes writing to R1 at the end of Cycle 5, meaning SUB can only read R1 in Cycle 6. In this case, SUB's ID stage must be stalled during Cycles 3, 4, and 5, resulting in 3 stall cycles (or 3 NOPs).

Part (i): [Total 1.75 marks] - Clear definition of a data hazard with reference to execution overlap (1.75 marks). Part (ii): [Total 4.5 marks] - Correct identification of the RAW hazard (1 mark). - Clear explanation of why the hazard occurs referring to stages (ADD writes in WB, SUB reads in ID) (1.5 marks). - Correct calculation of 2 stall cycles with split-phase register access (1 mark) and 3 stall cycles without split-phase register access (1 mark).

(i) Backtracking is a fundamental execution mechanism in Prolog where the interpreter, upon encountering a failure in satisfying a sub-goal, retreats to the most recent choice point (where alternative rules or facts could be matched) and attempts to find an alternative path to satisfy the goal. (ii) Tracing ?- ancestor_prereq(cs101, cs201): Step 1: Prolog attempts to match rule 1: ancestor_prereq(cs101, cs201) :- prereq(cs201, cs101). The database is checked for prereq(cs201, cs101), which is false. This match fails. Step 2: Prolog backtracks and matches rule 2: ancestor_prereq(cs101, cs201) :- prereq(cs201, Z), ancestor_prereq(cs101, Z). Step 3: It searches the database for a match to prereq(cs201, Z). It finds prereq(cs201, cs102), instantiating Z = cs102. Step 4: The new sub-goal is ancestor_prereq(cs101, cs102). Step 5: It tries rule 1 for this sub-goal: ancestor_prereq(cs101, cs102) :- prereq(cs102, cs101). It searches the database for prereq(cs102, cs101), which is a fact. This succeeds. Step 6: Since both sub-goals of rule 2 succeeded, the overall query succeeds and returns true. (iii) The rules for can_enroll/2 can be written as: can_enroll(Student, Course) :- prereq(Course, Pre), completed(Student, Pre). can_enroll(Student, Course) :- course(Course), not(prereq(Course, _)).

Part (i): [Total 1.5 marks] - Clear definition of backtracking referencing choice points and failure (1.5 marks). Part (ii): [Total 2.75 marks] - Checking rule 1 first and noting the failure of prereq(cs201, cs101) (1 mark). - Backtracking to rule 2 and correctly instantiating Z to cs102 (1 mark). - Evaluation of sub-goal ancestor_prereq(cs101, cs102) using rule 1 to find a database match and returning success (0.75 marks). Part (iii): [Total 2 marks] - Correct rule for checking direct prerequisite and completed status (1 mark). - Correct rule for checking courses with no prerequisites (using negation like not or \+ and anonymous variable _) (1 mark).

### Python Implementation

```python
class Cabin:
def __init__(self, cabin_id, capacity, rate):
self.__CabinID = cabin_id
self.__Capacity = int(capacity)
self.__Rate = float(rate)
self.__IsBooked = False

def get_cabin_id(self):
return self.__CabinID

def get_capacity(self):
return self.__Capacity

def get_rate(self):
return self.__Rate

def get_is_booked(self):
return self.__IsBooked

def set_is_booked(self, status):
self.__IsBooked = status

CabinList = [None] * 10

def ReadData():
try:
file = open("CabinData.txt", "r")
index = 0
for line in file:
line = line.strip()
if not line:
continue
parts = line.split(",")
cabin_id = parts[0]
capacity = int(parts[1])
rate = float(parts[2])
is_booked = parts[3].strip().lower() == "true"

cabin_obj = Cabin(cabin_id, capacity, rate)
cabin_obj.set_is_booked(is_booked)

if index < 10:
CabinList[index] = cabin_obj
index += 1
file.close()
except FileNotFoundError:
print("Error: CabinData.txt file could not be found.")

def BookCabin(MinCapacity):
for cabin in CabinList:
if cabin is not None:
if not cabin.get_is_booked() and cabin.get_capacity() >= MinCapacity:
cabin.set_is_booked(True)
return cabin.get_cabin_id()
return "None"

# Main Program
if __name__ == "__main__":
# Setup CabinData.txt programmatically for demonstration
with open("CabinData.txt", "w") as f:
f.write("C01,4,120.0,False
")
f.write("C02,2,80.0,False
")
f.write("C03,6,180.0,False
")
f.write("C04,4,130.0,True
")
f.write("C05,2,85.0,False
")
f.write("C06,8,250.0,False
")
f.write("C07,4,140.0,False
")
f.write("C08,2,90.0,True
")
f.write("C09,6,195.0,False
")
f.write("C10,10,350.0,False
")

ReadData()
print("First booking for capacity 5:", BookCabin(5))
print("Second booking for capacity 5:", BookCabin(5))

# Count booked
booked_count = sum(1 for c in CabinList if c is not None and c.get_is_booked())
print("Total booked cabins:", booked_count)
```

### Marking Scheme (Total: 25 Marks)

* **Class Definition & Fields (3 Marks)**:
* 1 Mark: Correctly defining the class `Cabin`.
* 1 Mark: Defining private attributes with appropriate types.
* 1 Mark: Implementation of constructor initializing variables correctly (`IsBooked` defaults to `False`).

* **Getters and Setter (3 Marks)**:
* 1 Mark: Implement getters for ID, Capacity, and Rate.
* 1 Mark: Implement getter for `IsBooked`.
* 1 Mark: Implement setter for `IsBooked`.

* **Array Declaration (2 Marks)**:
* 1 Mark: Declaring `CabinList` globally.
* 1 Mark: Initializing it to hold exactly 10 elements.

* **File Reading / Population (`ReadData`) (6 Marks)**:
* 1 Mark: Attempting to open "CabinData.txt" safely with a try/catch or try/except block.
* 1 Mark: Reading the file line by line and parsing split items correctly.
* 1 Mark: Converting data types properly (Capacity to Int, Rate to Float, Booking to Boolean).
* 1 Mark: Instantiating `Cabin` object within loop.
* 1 Mark: Setting booking status explicitly via the setter.
* 1 Mark: Storing each instance systematically in the sequential index of `CabinList`.

* **Cabin Reservation Logic (`BookCabin`) (6 Marks)**:
* 1 Mark: Creating loop to search `CabinList` sequentially.
* 1 Mark: Checking if Cabin index is not null/empty.
* 1 Mark: Checking `IsBooked` is false and capacity is greater than or equal to parameter.
* 1 Mark: Using setter to update booking state to true inside match block.
* 1 Mark: Immediately returning the valid cabin ID.
* 1 Mark: Returning "None" if loop completes with no match.

* **Main Program and Verification (5 Marks)**:
* 1 Mark: Execution of `ReadData()` without program crashing.
* 1 Mark: Executing `BookCabin(5)` and outputting matching Cabin ID (C03).
* 1 Mark: Executing secondary call and outputting next matching ID (C06).
* 1 Mark: Counting and printing total booked (4).
* 1 Mark: Screen capture or verified execution matching expected logic.

### Python Implementation

```python
class Node:
def __init__(self, data):
self.__Data = data
self.__LeftPointer = -1
self.__RightPointer = -1

def get_data(self):
return self.__Data

def set_data(self, data):
self.__Data = data

def get_left_pointer(self):
return self.__LeftPointer

def set_left_pointer(self, ptr):
self.__LeftPointer = ptr

def get_right_pointer(self):
return self.__RightPointer

def set_right_pointer(self, ptr):
self.__RightPointer = ptr

BSTArray = [None] * 15
RootPointer = -1
FreePointer = 0

def InitializeTree():
global RootPointer, FreePointer
RootPointer = -1
FreePointer = 0
for i in range(15):
BSTArray[i] = Node(-1)
if i < 14:
BSTArray[i].set_left_pointer(i + 1)
else:
BSTArray[i].set_left_pointer(-1)

def InsertNode(NewValue):
global RootPointer, FreePointer
if FreePointer == -1:
print("Tree is full")
return

# Get node from free list
newNodeIndex = FreePointer
FreePointer = BSTArray[FreePointer].get_left_pointer()

BSTArray[newNodeIndex].set_data(NewValue)
BSTArray[newNodeIndex].set_left_pointer(-1)
BSTArray[newNodeIndex].set_right_pointer(-1)

if RootPointer == -1:
RootPointer = newNodeIndex
else:
currentNode = RootPointer
placed = False
while not placed:
if NewValue < BSTArray[currentNode].get_data():
if BSTArray[currentNode].get_left_pointer() == -1:
BSTArray[currentNode].set_left_pointer(newNodeIndex)
placed = True
else:
currentNode = BSTArray[currentNode].get_left_pointer()
else:
if BSTArray[currentNode].get_right_pointer() == -1:
BSTArray[currentNode].set_right_pointer(newNodeIndex)
placed = True
else:
currentNode = BSTArray[currentNode].get_right_pointer()

def InOrder(CurrentNodePointer):
if CurrentNodePointer != -1:
InOrder(BSTArray[CurrentNodePointer].get_left_pointer())
print(BSTArray[CurrentNodePointer].get_data())
InOrder(BSTArray[CurrentNodePointer].get_right_pointer())

# Main Program Execution
if __name__ == "__main__":
InitializeTree()
test_values = [45, 23, 67, 12, 34, 56, 89]
for val in test_values:
InsertNode(val)

print("In-order Traversal:")
InOrder(RootPointer)
```

### Marking Scheme (Total: 25 Marks)

* **Node Class Design (3 Marks)**:
* 1 Mark: Class defined with requested private attributes.
* 1 Mark: Constructor initializing variables and parameters correctly.
* 1 Mark: Getter and Setter methods implemented correctly.

* **Tree Structure Setup (2 Marks)**:
* 1 Mark: Global `BSTArray` declaration of size 15.
* 1 Mark: `RootPointer` and `FreePointer` declared globally.

* **InitializeTree Procedure (5 Marks)**:
* 1 Mark: Loop through range 0 to 14 to instantiate `Node(-1)`.
* 1 Mark: Correctly assigning index-based chaining (`i + 1`) to `LeftPointer` of free nodes.
* 1 Mark: Setting the last node's `LeftPointer` to -1.
* 1 Mark: Resetting `RootPointer` to -1.
* 1 Mark: Setting `FreePointer` to 0.

* **Insertion Logic (`InsertNode`) (8 Marks)**:
* 1 Mark: Checking for full tree condition (`FreePointer == -1`).
* 1 Mark: Correctly extracting new node index from `FreePointer` and updating `FreePointer` using the free-node chain pointer.
* 1 Mark: Assigning value and setting both pointers of the allocated node to -1.
* 1 Mark: Handling base case when `RootPointer` is -1.
* 1 Mark: Loop/Recursion through existing BST elements comparing values.
* 1 Mark: Branching to left if input is smaller, and checking for terminal state (`-1`).
* 1 Mark: Branching to right if input is larger/equal, and checking for terminal state (`-1`).
* 1 Mark: Updating parent index to point to `newNodeIndex`.

* **Traversal and Testing (7 Marks)**:
* 1 Mark: InOrder method implemented using base case check (does not print if node index is -1).
* 1 Mark: Correct order of recursion: recurse left, process current node, recurse right.
* 1 Mark: Invoking `InitializeTree()` in main scope.
* 1 Mark: Inserting all specified test data in correct sequence.
* 1 Mark: Successful verification of printed output in proper numerical order (12, 23, 34, 45, 56, 67, 89).

### Python Implementation

```python
# 1. Global Grid structure
Grid = [
[2, 0, 3, 1, 5],
[1, 0, 1, 4, 2],
[0, 3, 2, 0, 1],
[4, 1, 0, 1, 3],
[2, 0, 1, 2, 1]
]

# 2. Recursive Function
def MaxPoints(Row, Col):
# Trace statement for visited cells
print(f"Visited: [{Row}, {Col}]")

# Base case: reached destination
if Row == 4 and Col == 4:
return Grid[Row][Col]

# Boundary case: can only go right
if Row == 4:
return Grid[Row][Col] + MaxPoints(Row, Col + 1)

# Boundary case: can only go down
if Col == 4:
return Grid[Row][Col] + MaxPoints(Row + 1, Col)

# Recursive step: get maximum of either choice
go_right = MaxPoints(Row, Col + 1)
go_down = MaxPoints(Row + 1, Col)

if go_right > go_down:
return Grid[Row][Col] + go_right
else:
return Grid[Row][Col] + go_down

# 3. Main program execution
if __name__ == "__main__":
print("Starting point calculation...")
result = MaxPoints(0, 0)
print("-----------------------------")
print("Maximum Points possible:", result)
```

### Marking Scheme (Total: 25 Marks)

* **Grid Initialization (4 Marks)**:
* 2 Marks: Global array variable `Grid` set up correctly.
* 2 Marks: Initialization data represents the specified 5x5 layout correctly.

* **Recursive Function Header and parameters (2 Marks)**:
* 2 Marks: `MaxPoints` correctly parameterized with current state `Row` and `Col` values.

* **Base Case Implementation (4 Marks)**:
* 2 Marks: Correct comparison to determine when the bottom-right corner `(4, 4)` is reached.
* 2 Marks: Correctly returning only the current cell's points when target is reached.

* **Boundary Conditions (4 Marks)**:
* 2 Marks: Logic determining if `Row == 4` and traversing rightward recursively, returning current grid value + recursive return value.
* 2 Marks: Logic determining if `Col == 4` and traversing downward recursively, returning current grid value + recursive return value.

* **Recursive Branching Steps (6 Marks)**:
* 2 Marks: Two independent recursive calls initiated: `MaxPoints(Row + 1, Col)` and `MaxPoints(Row, Col + 1)`.
* 2 Marks: Accurate comparison of the output values of both directions to select the maximum.
* 2 Marks: Returning the current cell's value summed with the chosen maximum value.

* **Main & Debugging Execution (5 Marks)**:
* 1 Mark: Main program triggers function with initial coordinates `(0, 0)`.
* 2 Marks: Trace output tracking correctly "Visited: [Row, Col]" format on recursion step entry.
* 2 Marks: Accurate final result verification showing total score of 17.