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

Step 1: Convert the positive value 87 to an 8-bit binary number. 87 = 64 + 16 + 4 + 2 + 1, which gives 01010111. Step 2: Perform the one's complement by inverting all the bits, which changes 01010111 to 10101000. Step 3: Add 1 to the least significant bit of the inverted value to complete the two's complement, giving 10101001.

1 mark: Correct binary representation of positive 87 (01010111). 1 mark: Correctly inverting all bits (10101000). 1 mark: Correctly adding 1 to yield the final correct answer (10101001).

Referential integrity ensures that the relationships between tables in a database remain accurate and consistent. This is implemented via foreign keys, where a foreign key field in one table links to the primary key in another table. The database system monitors actions and prevents operations that violate this relationship, ensuring no orphaned records are created.

1 mark: Definition of referential integrity (maintaining consistency/validity of relationships between tables). 1 mark: Explanation of the foreign key to primary key linkage. 1 mark: Explanation of how DBMS prevents integrity violations (e.g., blocking deletions of referenced records or blocking invalid inserts).

The printing process starts with a drum receiving a uniform static charge. A laser beam then scans the drum, discharging specific points to write a latent electrostatic image. Oppositely charged toner is attracted to these discharged spots. Finally, the toner is transferred to the paper and fused into place using heated rollers.

1 mark: Mention of the drum receiving a static charge. 1 mark: Laser beam selectively discharging areas of the drum to create the image outline. 1 mark: Toner being attracted to the drum and transferred to the paper, then fused using heat and pressure.

Client-side scripting executes code on the user's browser, meaning login validation code and database queries would be exposed to potential attackers. By using server-side scripting, the verification is done entirely on the secure host server. This protects sensitive database credentials, prevents the user from bypassing validation checks, and guarantees execution regardless of client configuration.

1 mark: Security of code and database credentials (not visible to user). 1 mark: Secure access to the central server's database. 1 mark: Independence from client-side settings / browser configurations (e.g., disabled scripting).

The Status Register holds system flags that change based on ALU results. The CMP instruction performs a subtraction between two operands. Instead of storing the numeric result, it updates flags like Zero (Z), Negative (N), and Overflow (V) in the Status Register. The next conditional jump instruction checks these flags to determine if the jump criteria are satisfied.

1 mark: Identifying that the Status Register contains status flags (e.g., Z, N, C, V) representing the state of the last operation. 1 mark: Explaining that CMP performs a comparison/subtraction and updates these flags without changing operand values. 1 mark: Explaining that conditional jump instructions inspect these flags to make branching decisions.

Over time, files stored on a magnetic hard disk become fragmented, with parts of a single file spread across different tracks and sectors. Defragmentation utility software identifies these scattered parts and physically relocates them so that each file is stored in contiguous sectors. This significantly reduces the physical travel time of the read/write drive head, boosting system speed.

1 mark: Stating that it reorganizes file segments scattered across the disk. 1 mark: Explaining that it rearranges segments so that files are stored in contiguous sectors/blocks. 1 mark: Connecting this contiguous storage to reduced physical read/write head movement, resulting in faster data access.

The process of signing an email involves: 1) The sender uses a hash function to compute a unique hash value (digest) of the message content. 2) The sender encrypts this hash value with their own private key, which becomes the digital signature. 3) The digital signature is sent alongside the email. The recipient can decrypt this signature with the sender's public key to verify that the message has not been tampered with.

1 mark: The message content is passed through a hashing algorithm to create a unique hash digest. 1 mark: The sender encrypts this hash digest using their private key to form the digital signature. 1 mark: The digital signature is attached to the email for transmission (which the recipient decrypts using the sender's public key to check consistency).

Shareware is commercial software distributed for free on a trial basis, keeping its source code proprietary and prohibiting modifications. Free Software (Software Libre), however, respects users' freedoms, providing full access to the source code, allowing changes, modifications, and free distribution, and is typically completely free of charge.

1 mark: Contrast regarding cost/trial (Shareware is trial-based/commercial, Free Software is completely free of charge and trial constraints). 1 mark: Contrast regarding source code access (Shareware is closed source, Free Software is open source). 1 mark: Contrast regarding modification/redistribution rights (Shareware restricts modification/sharing, Free Software encourages and legalizes it).

Vector graphics are based on mathematical representations (such as lines, curves, and shapes) rather than a grid of individual pixels. Because of this, they can be scaled infinitely without any loss of quality or pixelation. Additionally, they generally require less storage space for simple drawings since they only store the instructions to draw the shapes rather than color data for every single pixel.

Award 1 mark for each valid characteristic up to a maximum of 3 marks:
- Vector graphics store geometric shapes, objects, or mathematical formulas (whereas bitmaps store a grid of individual pixels) [1 mark].
- Vector graphics do not lose quality / become pixelated when scaled or resized (whereas bitmaps lose quality/pixelate) [1 mark].
- Vector graphics typically have smaller file sizes (for simple illustrations) because they only store drawing parameters (whereas bitmaps require data for every pixel) [1 mark].
- Individual components/objects in a vector graphic can be edited independently (whereas bitmaps require editing at the pixel level) [1 mark].

In a relational database, tables are linked together using keys. The primary key is a unique identifier for a record in the parent table. To establish a link, this primary key is added as a field (the foreign key) in the related (child) table. This creates a relationship (typically a 1-to-many relationship) where multiple records in the child table can refer back to a single record in the parent table, while maintaining referential integrity.

Award marks as follows (maximum 3 marks):
- State that a primary key uniquely identifies a record/row in a table [1 mark].
- State that a foreign key is a field in one table that references/links to the primary key of another table [1 mark].
- Explain that matching the foreign key value to the primary key value establishes a relationship (typically a one-to-many relationship) between the tables [1 mark].
- Explain that this link enforces referential integrity (e.g., preventing orphaned records in the child table) [1 mark].

- Data Bus: A bi-directional bus that transmits the actual data or instruction codes between the CPU, memory, and input/output devices.
- Address Bus: A unidirectional bus that carries the physical memory address of the location where data is to be read from or written to.
- Control Bus: A bi-directional bus that transmits control signals and timing commands (such as read/write requests, clock pulses, and interrupt signals) to manage the activities of all system components.

Award 1 mark for each correct description up to a maximum of 3 marks:
- Data Bus: Transports data/instructions between the CPU and memory or I/O devices (bi-directional) [1 mark].
- Address Bus: Transports the memory address of the location currently being read from or written to (unidirectional from CPU) [1 mark].
- Control Bus: Transports control, command, and synchronization signals (such as read/write instructions and interrupt requests) to coordinate system operations [1 mark].

To detect transmission errors, the sender runs a specific algorithm on the block of data to generate a numerical checksum value. This value is appended to the data block and transmitted. Upon receiving the transmission, the receiver runs the same algorithm on the received data block. The receiver then compares its calculated checksum with the transmitted checksum. If the two values match, the data is assumed to be error-free; if they do not match, a transmission error has occurred.

Award marks as follows (maximum 3 marks):
- The sending device applies an algorithm/formula to the data block to calculate a checksum value [1 mark].
- The checksum value is transmitted along with the data [1 mark].
- The receiving device applies the same algorithm to the received data to generate its own checksum [1 mark].
- The receiver compares the calculated checksum with the transmitted checksum; a mismatch indicates a transmission error [1 mark].

1. Convert the absolute denary number 3.25 to fixed-point binary: 3 is 11, and 0.25 is 0.01, giving 11.01. 2. Write this as an 8-bit two's complement representation: +3.25 is 0011.0100. Inverting the bits gives 1100.1011, and adding 1 gives 1100.1100. 3. Normalize the binary number. A normalized negative number must start with 1.0. Shift the binary point 2 places to the left to obtain 1.0011000. 4. Calculate the exponent. Shifting 2 places to the left means multiplying by \(2^2\), so the exponent is +2. 5. Convert the exponent +2 to a 4-bit binary value: 0010. 6. Combine the 8-bit mantissa (10011000) and 4-bit exponent (0010).

1 mark: Identify positive binary representation is 11.01 or 0011.0100. 1 mark: Apply two's complement correctly to obtain 1100.1100. 1 mark: Shift binary point correctly to get normalized mantissa starting with 1.0 (1.0011000). 1 mark: Correct exponent value of +2. 1 mark: Correct 4-bit exponent representation (0010) and correct final mantissa/exponent combination.

(a) Rule: grandparent(X, Y) :- parent(X, Z), parent(Z, Y). (b) 1. The query grandparent(albert, Who) unifies X with albert and Y with Who. 2. The interpreter sets subgoals parent(albert, Z) and parent(Z, Who). 3. It searches facts from top to bottom, matches parent(albert, bob) and binds Z to bob. 4. It then attempts parent(bob, Who) and finds parent(bob, charlie), returning Who = charlie as the first solution. 5. To find more solutions, it backtracks to the last choice point, attempts parent(bob, Who) again, matches parent(bob, diana), and returns Who = diana.

2 marks: Correct Prolog rule (1 mark for correct structure/syntax, 1 mark for correct logic using an intermediate variable Z). 3 marks for backtracking explanation: 1 mark for explaining the binding of Z to bob via parent(albert, Z); 1 mark for finding the first match charlie; 1 mark for explaining backtracking to the choice point to find diana.

(a) The composite primary key for STUDENT_SPORTS is (StudentID, SportCode). The table has partial key dependencies, which violates Second Normal Form (and therefore Third Normal Form): StudentName depends only on StudentID, while SportName and Fee depend only on SportCode. (b) To achieve 3NF, the relation must be split: 1. STUDENT(StudentID, StudentName) [Primary Key: StudentID] 2. SPORT(SportCode, SportName, Fee) [Primary Key: SportCode] 3. REGISTRATION(StudentID, SportCode) [Primary Key: (StudentID, SportCode); Foreign Keys: StudentID references STUDENT, SportCode references SPORT].

2 marks: Explanation of why it is not in 3NF (1 mark for identifying that (StudentID, SportCode) is the composite primary key, 1 mark for explaining that partial dependencies exist, such as StudentName depending only on StudentID). 3 marks: Normalized relations (1 mark for STUDENT table, 1 mark for SPORT table, 1 mark for REGISTRATION table with primary and foreign keys correctly identified).

(a) The Host Operating System is installed directly on the physical hardware. It manages physical resources and runs the hypervisor. The Guest Operating System runs inside a virtual machine managed by the hypervisor, interacting with virtualized hardware resources instead of actual physical hardware. (b) Running a database inside a virtual machine introduces performance overhead. Every input/output (I/O) operation and memory allocation must be translated by the hypervisor, leading to increased latency and decreased throughput compared to a bare-metal installation.

2 marks: Contrast host vs guest (1 mark for describing host OS running on bare metal, 1 mark for describing guest OS running in a virtual machine). 3 marks: Explanation of a limitation (1 mark for identifying performance overhead/I/O latency, 1 mark for explaining how hypervisor translation causes this latency, 1 mark for applying this specifically to a resource-intensive system like a database).

(a) Structure: Root node is 15. Root 15 has left child 8 and right child 24. Node 8 has left child 5 and right child 12. Node 24 has left child 19 and right child 30. Nodes 5, 12, 19, and 30 are leaf nodes. (b) Post-order traversal traverses Left subtree, then Right subtree, then Root. 1. Left subtree of 15: post-order of 8 gives 5, 12, 8. 2. Right subtree of 15: post-order of 24 gives 19, 30, 24. 3. Combine with root 15: 5, 12, 8, 19, 30, 24, 15.

3 marks: Tree structure description (1 mark for root 15 with children 8 and 24; 1 mark for node 8 with children 5 and 12; 1 mark for node 24 with children 19 and 30). 2 marks: Post-order traversal sequence (2 marks for fully correct sequence: 5, 12, 8, 19, 30, 24, 15; 1 mark if only 1 or 2 minor order errors).

1. Alice creates a unique, fixed-size message digest by passing her message through a cryptographic hash function. 2. Alice encrypts this message digest using her private key to produce the digital signature. 3. Alice sends both the original message and the digital signature to Bob. 4. Bob decrypts the received digital signature using Alice's public key to recover the original message digest. 5. Bob hashes the received message using the same hash function to produce a new digest. 6. Bob compares the two digests; if they match, integrity is verified (the message has not been altered) and non-repudiation is achieved (only Alice could have created the signature).

1 mark: Alice hashes the message to create a digest. 1 mark: Alice encrypts the digest with her private key to create the signature. 1 mark: Bob decrypts the signature with Alice's public key to get the original digest. 1 mark: Bob hashes the message to get a new digest. 1 mark: Bob compares the two digests to verify integrity and authenticity.

1. Round Robin (RR) prioritizes processes based on a first-in, first-out cyclic queue. Each process is allocated a fixed time slice (quantum) of CPU time before being pre-empted and moved to the back of the queue. 2. Shortest Job First (SJF) prioritizes processes based on their expected CPU burst time; the process with the shortest execution time is executed first. 3. RR is completely immune to starvation because every process in the queue is guaranteed a CPU time slice in turn. 4. SJF is vulnerable to starvation because long processes may wait indefinitely if shorter processes continuously enter the ready queue. 5. This vulnerability in SJF can be mitigated using aging, which increases the priority of waiting jobs over time.

1 mark: RR explanation of prioritization (cyclic queue with time slices/quanta). 1 mark: SJF explanation of prioritization (prioritized by shortest CPU burst/execution time). 1 mark: Explain why RR prevents starvation (fair distribution of time ensures every process gets a turn). 1 mark: Explain why SJF is vulnerable to starvation (long processes are bypassed by newer, shorter processes). 1 mark: Identify a mitigation for SJF starvation (such as aging).

1. Initial state: Num = 345, Total = 0. 2. Loop 1: Temp = 345 MOD 10 = 5. Total = 0 + (5 * 5) = 25. Num = 345 DIV 10 = 34. 3. Loop 2: Temp = 34 MOD 10 = 4. Total = 25 + (4 * 4) = 41. Num = 34 DIV 10 = 3. 4. Loop 3: Temp = 3 MOD 10 = 3. Total = 41 + (3 * 3) = 50. Num = 3 DIV 10 = 0. 5. Loop terminates as Num > 0 is false. 6. Return value is 50.

1 mark: Correct initial state (Num=345, Total=0). 1 mark: Correct trace of Loop 1 (Temp=5, Total=25, Num=34). 1 mark: Correct trace of Loop 2 (Temp=4, Total=41, Num=3). 1 mark: Correct trace of Loop 3 (Temp=3, Total=50, Num=0). 1 mark: Correct final return value of 50.

Step-by-step trace of recursive calls:
1. Process("CAMBRIDGE") -> 'C' is not a vowel -> Returns "C" & Process("AMBRIDGE")
2. Process("AMBRIDGE") -> 'A' is a vowel -> Returns Process("MBRIDGE") & "A"
3. Process("MBRIDGE") -> 'M' is not a vowel -> Returns "M" & Process("BRIDGE")
4. Process("BRIDGE") -> 'B' is not a vowel -> Returns "B" & Process("RIDGE")
5. Process("RIDGE") -> 'R' is not a vowel -> Returns "R" & Process("IDGE")
6. Process("IDGE") -> 'I' is a vowel -> Returns Process("DGE") & "I"
7. Process("DGE") -> 'D' is not a vowel -> Returns "D" & Process("GE")
8. Process("GE") -> 'G' is not a vowel -> Returns "G" & Process("E")
9. Process("E") -> Length is 1 -> Returns "E"

Unwinding the stack:
- Process("GE") = "G" & "E" = "GE"
- Process("DGE") = "D" & "GE" = "DGE"
- Process("IDGE") = "DGE" & "I" = "DGEI"
- Process("RIDGE") = "R" & "DGEI" = "RDGEI"
- Process("BRIDGE") = "B" & "RDGEI" = "BRDGEI"
- Process("MBRIDGE") = "M" & "BRDGEI" = "MBRDGEI"
- Process("AMBRIDGE") = "MBRDGEI" & "A" = "MBRDGEIA"
- Process("CAMBRIDGE") = "C" & "MBRDGEIA" = "CMBRDGEIA"

(a) Call stack and return trace: [4 marks]
- 1 mark for correct base case return value ("E").
- 1 mark for showing correct vowel shifting mechanism (e.g., 'A' and 'I' appended at the end of their sub-results).
- 1 mark for correct intermediate strings for at least 4 recursive steps.
- 1 mark for correct final output "CMBRDGEIA".
(b) Overall purpose: [2 marks]
- 1 mark for stating that it filters and moves all vowels to the end of the string.
- 1 mark for noting that consonants retain their original relative positions while vowels are shifted to the back.

Let's trace each outer loop pass step-by-step:
- Pass 1 (I = 1): Inner loop J goes from 1 to 4.
- J=1: Arr[1](12) < Arr[2](45) is TRUE -> Swap. Arr becomes [45, 12, 23, 56, 17], Swapped = TRUE.
- J=2: Arr[2](12) < Arr[3](23) is TRUE -> Swap. Arr becomes [45, 23, 12, 56, 17], Swapped = TRUE.
- J=3: Arr[3](12) < Arr[4](56) is TRUE -> Swap. Arr becomes [45, 23, 56, 12, 17], Swapped = TRUE.
- J=4: Arr[4](12) < Arr[5](17) is TRUE -> Swap. Arr becomes [45, 23, 56, 17, 12], Swapped = TRUE.
- End of Pass 1: Arr = [45, 23, 56, 17, 12], I increments to 2.
- Pass 2 (I = 2): Inner loop J goes from 1 to 3.
- J=1: Arr[1](45) < Arr[2](23) is FALSE.
- J=2: Arr[2](23) < Arr[3](56) is TRUE -> Swap. Arr becomes [45, 56, 23, 17, 12], Swapped = TRUE.
- J=3: Arr[3](23) < Arr[4](17) is FALSE.
- End of Pass 2: Arr = [45, 56, 23, 17, 12], I increments to 3.
- Pass 3 (I = 3): Inner loop J goes from 1 to 2.
- J=1: Arr[1](45) < Arr[2](56) is TRUE -> Swap. Arr becomes [56, 45, 23, 17, 12], Swapped = TRUE.
- J=2: Arr[2](45) < Arr[3](23) is FALSE.
- End of Pass 3: Arr = [56, 45, 23, 17, 12], I increments to 4.
- Pass 4 (I = 4): Inner loop J goes from 1 to 1.
- J=1: Arr[1](56) < Arr[2](45) is FALSE. Swapped remains FALSE.
- End of Pass 4: Arr = [56, 45, 23, 17, 12], I increments to 5.
Loop terminates because Swapped is FALSE (and I = Size).

Trace Table Marks: [6 marks total]
- 1 mark for correct array values and Swapped=TRUE at the end of Pass 1.
- 1 mark for correct array values and Swapped=TRUE at the end of Pass 2.
- 1 mark for correct array values and Swapped=TRUE at the end of Pass 3.
- 1 mark for correct array values and Swapped=FALSE at the end of Pass 4.
- 1 mark for correct outer loop counter values of I (1, 2, 3, 4).
- 1 mark for showing correct exit condition (Swapped = FALSE at Pass 4).

Detailed step-by-step trace:
- Start: Front = 0, Rear = 0, Q = [0, 0, 0, 0, 0]
1. Enqueue(10): Front becomes 1, Rear becomes 1. Q[1] = 10. Q = [10, 0, 0, 0, 0]
2. Enqueue(20): Rear becomes 2. Q[2] = 20. Q = [10, 20, 0, 0, 0]
3. X <- Dequeue(): Front is 1. Item = Q[1] = 10. Front becomes 2. X = 10.
4. Enqueue(30): Rear becomes 3. Q[3] = 30. Q = [10, 20, 30, 0, 0]
5. Enqueue(40): Rear becomes 4. Q[4] = 40. Q = [10, 20, 30, 40, 0]
6. Enqueue(50): Rear becomes 5. Q[5] = 50. Q = [10, 20, 30, 40, 50]
7. Enqueue(60): (5 MOD 5) + 1 = 1. Since 1 != Front (2), not full. Rear becomes 1. Q[1] = 60. Q = [60, 20, 30, 40, 50]
8. Y <- Dequeue(): Front is 2. Item = Q[2] = 20. Front becomes 3. Y = 20.
9. Enqueue(70): (1 MOD 5) + 1 = 2. Since 2 != Front (3), not full. Rear becomes 2. Q[2] = 70. Q = [60, 70, 30, 40, 50]

Final values:
- Front = 3, Rear = 2
- Q = [60, 70, 30, 40, 50]
- X = 10, Y = 20

- (a) 1 mark for Front = 3, 1 mark for Rear = 2.
- (b) 2 marks for correct array contents [60, 70, 30, 40, 50]. Deduct 1 mark if either element 60 or 70 is placed in the wrong index.
- (c) 1 mark for X = 10, 1 mark for Y = 20.

- Input: Msg = "BZA4"
- Key = VALUE(RIGHT("BZA4", 1)) = VALUE("4") = 4
- Out = ""
- Loop I from 1 to LENGTH(Msg) - 1 = 3:
- Pass 1 (I = 1):
- Ch = MID("BZA4", 1, 1) = "B"
- CodeVal = ASC("B") - 4 = 66 - 4 = 62
- Since CodeVal < 65, CodeVal = 62 + 26 = 88
- Ch = CHR(88) = "X"
- Out = "" & "X" = "X"
- Pass 2 (I = 2):
- Ch = MID("BZA4", 2, 1) = "Z"
- CodeVal = ASC("Z") - 4 = 90 - 4 = 86
- CodeVal is not less than 65
- Ch = CHR(86) = "V"
- Out = "X" & "V" = "XV"
- Pass 3 (I = 3):
- Ch = MID("BZA4", 3, 1) = "A"
- CodeVal = ASC("A") - 4 = 65 - 4 = 61
- Since CodeVal < 65, CodeVal = 61 + 26 = 87
- Ch = CHR(87) = "W"
- Out = "XV" & "W" = "XVW"
- Output printed: "XVW"

- 1 mark for correctly extracting Key = 4.
- 1 mark for correct I = 1 row (Ch = "B", CodeVal = 88, Out = "X").
- 1 mark for correct I = 2 row (Ch = "Z", CodeVal = 86, Out = "XV").
- 1 mark for correct I = 3 row (Ch = "A", CodeVal = 87, Out = "XVW").
- 1 mark for correctly performing the ASCII boundary wrap-around logic (+26) for "B" and "A".
- 1 mark for the correct final output "XVW".

(a) Step-by-step calls:
1. Traverse(1) is called.
2. Traverse(1) calls Traverse(LeftPointer[1]) which is Traverse(2).
3. Traverse(2) calls Traverse(LeftPointer[2]) which is Traverse(4).
4. Traverse(4) has no children, so it outputs "B" and returns to Traverse(2).
5. Traverse(2) calls Traverse(RightPointer[2]) which is Traverse(5).
6. Traverse(5) has no children, so it outputs "H" and returns to Traverse(2).
7. Traverse(2) outputs "F" and returns to Traverse(1).
8. Traverse(1) calls Traverse(RightPointer[1]) which is Traverse(3).
9. Traverse(3) calls Traverse(LeftPointer[3]) which is Traverse(6).
10. Traverse(6) outputs "P" and returns to Traverse(3).
11. Traverse(3) calls Traverse(RightPointer[3]) which is Traverse(7).
12. Traverse(7) outputs "T" and returns to Traverse(3).
13. Traverse(3) outputs "R" and returns to Traverse(1).
14. Traverse(1) outputs "M".

(b) Output sequence: "B", "H", "F", "P", "T", "R", "M".
(c) The traversal is post-order because it recursively processes the left subtree, then the right subtree, and finally outputs the root node.

(a) Sequence of calls: [3 marks]
- 1 mark for correct first three calls in order: Traverse(1), Traverse(2), Traverse(4).
- 1 mark for next two calls: Traverse(5), Traverse(3).
- 1 mark for final two calls: Traverse(6), Traverse(7).
(b) Output sequence: [2 marks]
- 1 mark for correct first three outputs: "B", "H", "F".
- 1 mark for remaining correct outputs: "P", "T", "R", "M".
(c) Traversal type: [1 mark]
- 1 mark for "Post-order" (or "postorder").

(a) Tracing JumpSearch(Arr, 35, 10):
- Initial: Step = 3, Prev = 1.
- First loop condition: Arr[MIN(3,10)] < 35 -> Arr[3] < 35 -> 20 < 35 is TRUE.
- Prev becomes 3, Step becomes 6.
- Next loop condition: Arr[MIN(6,10)] < 35 -> Arr[6] < 35 -> 35 < 35 is FALSE.
- First loop terminates with Prev = 3, Step = 6.
- Second part: I starts at 3.
- Arr[3](20) < 35 is TRUE -> I becomes 4.
- Arr[4](25) < 35 is TRUE -> I becomes 5.
- Arr[5](30) < 35 is TRUE -> I becomes 6.
- Arr[6](35) < 35 is FALSE -> second loop terminates with I = 6.
- Check: Arr[6] = 35 is TRUE -> returns 6.

(b) Tracing JumpSearch(Arr, 22, 10):
- Initial: Step = 3, Prev = 1.
- First loop condition: Arr[3](20) < 22 is TRUE.
- Prev becomes 3, Step becomes 6.
- Next condition: Arr[6](35) < 22 is FALSE -> first loop terminates.
- Second part: I starts at 3.
- Arr[3](20) < 22 is TRUE -> I becomes 4.
- Next condition: Arr[4](25) < 22 is FALSE -> second loop terminates.
- Check: Arr[4] = 22 is FALSE -> returns -1.
- Explanation: The first loop successfully localized the potential target to the range [3..6]. When linear search starts at index 3, it inspects Arr[4] which is 25. Since 25 > 22, and the array is sorted, no subsequent items can equal 22. The loop condition Arr[I] < Target fails immediately, allowing the algorithm to stop early.

(a) Trace for Target = 35: [3 marks]
- 1 mark for Prev = 3 at termination of first loop.
- 1 mark for Step = 6 at termination of first loop.
- 1 mark for final index I = 6 (and returns 6).
(b) Trace for Target = 22: [3 marks]
- 1 mark for stating that the function returns -1.
- 1 mark for noting that the second loop terminates because Arr[4] = 25 is greater than 22 (the condition Arr[I] < 22 is violated).
- 1 mark for explaining that because the array is sorted, any value past 25 will also be larger than 22, proving 22 is not present.

The function calculates the average score for each student by summing up their grades across 5 subjects and dividing by 5.0. It compares each student's average to the current maximum average. If a student's average is strictly greater than the current maximum, the maximum average is updated and the student's index is stored. This ensures that in the case of a tie, the first student with that average is preserved.

Pseudocode:
```
FUNCTION FindHighestAverage() RETURNS INTEGER
DECLARE Student, Test : INTEGER
DECLARE Sum : INTEGER
DECLARE Average, MaxAverage : REAL
DECLARE BestStudent : INTEGER

MaxAverage <- -1.0
BestStudent <- 1

FOR Student <- 1 TO 50
Sum <- 0
FOR Test <- 1 TO 5
Sum <- Sum + Grades[Student, Test]
NEXT Test
Average <- Sum / 5.0
IF Average > MaxAverage THEN
MaxAverage <- Average
BestStudent <- Student
ENDIF
NEXT Student

RETURN BestStudent
ENDFUNCTION
```

- 1 mark: Correct function header and return type (RETURNS INTEGER).
- 1 mark: Correctly declaring all local variables (Student, Test, Sum, Average, MaxAverage, BestStudent) with appropriate data types.
- 1 mark: Initialising MaxAverage to -1.0 (or another low value) and BestStudent before processing.
- 1 mark: Outer loop iterating through 50 students correctly.
- 1 mark: Inner loop iterating through 5 tests for each student correctly.
- 1 mark: Calculating the sum and the average score (Sum / 5.0) accurately.
- 1 mark: Comparing Average > MaxAverage and updating MaxAverage and BestStudent if true.
- 1 mark: Returning the correct BestStudent index and terminating the function properly.

The algorithm first checks the length of the string. If it's outside the valid range [8, 16], it returns FALSE. It then scans each character using a FOR loop with MID. It marks boolean flags when matching characters are found. Finally, it returns TRUE only if all three flags are TRUE.

Pseudocode:
```
FUNCTION ValidatePassword(Password : STRING) RETURNS BOOLEAN
DECLARE PassLength, i : INTEGER
DECLARE HasUpper, HasLower, HasDigit : BOOLEAN
DECLARE Char : STRING

PassLength <- LENGTH(Password)
IF PassLength < 8 OR PassLength > 16 THEN
RETURN FALSE
ENDIF

HasUpper <- FALSE
HasLower <- FALSE
HasDigit <- FALSE

FOR i <- 1 TO PassLength
Char <- MID(Password, i, 1)
IF Char >= "A" AND Char <= "Z" THEN
HasUpper <- TRUE
ELSEIF Char >= "a" AND Char <= "z" THEN
HasLower <- TRUE
ELSEIF Char >= "0" AND Char <= "9" THEN
HasDigit <- TRUE
ENDIF
NEXT i

IF HasUpper AND HasLower AND HasDigit THEN
RETURN TRUE
ELSE
RETURN FALSE
ENDIF
ENDFUNCTION
```

- 1 mark: Correct function header with parameter Password : STRING and RETURNS BOOLEAN.
- 1 mark: Length check of Password using LENGTH() to ensure it is between 8 and 16 characters inclusive.
- 1 mark: Declaring and initializing three boolean flags (HasUpper, HasLower, HasDigit) to FALSE.
- 1 mark: Correct loop structure (FOR i <- 1 TO PassLength) to traverse every character.
- 1 mark: Extracting single character using MID(Password, i, 1).
- 1 mark: Checking character range for uppercase ('A' to 'Z') and lowercase ('a' to 'z') and setting corresponding flags.
- 1 mark: Checking character range for digit ('0' to '9') and setting corresponding flag.
- 1 mark: Returning TRUE if and only if all criteria are satisfied, otherwise returning FALSE.

To add an element to a circular queue, we first check if the queue is full by comparing NumItems to the maximum size of the array (10). If full, the function returns FALSE.
If not full, we increment the Tail index using modular arithmetic (Tail <- (Tail + 1) MOD 10) to handle the wrap-around. We then insert the Value at Queue[Tail], increment NumItems by 1, and return TRUE.

Pseudocode:
```
FUNCTION Enqueue(Value : INTEGER) RETURNS BOOLEAN
IF NumItems = 10 THEN
RETURN FALSE
ENDIF

Tail <- (Tail + 1) MOD 10
Queue[Tail] <- Value
NumItems <- NumItems + 1

RETURN TRUE
ENDFUNCTION
```

- 1 mark: Correct function header with correct parameters and return type.
- 2 marks: Correctly checking if the queue is full (comparing NumItems to 10) and returning FALSE if so.
- 2 marks: Correct circular wrapping formula for Tail (either Tail <- (Tail + 1) MOD 10 or using an IF block: Tail <- Tail + 1; IF Tail = 10 THEN Tail <- 0 ENDIF).
- 1 mark: Storing the element in Queue at index Tail.
- 1 mark: Incrementing NumItems by 1.
- 1 mark: Returning TRUE at the end.

A binary search works by continually dividing the search space in half. We initialize Lower to 1 and Upper to 100. Inside the WHILE loop, we compute Mid as the integer division of (Lower + Upper). We compare SearchList[Mid] with Item. If they are equal, we terminate the loop. If SearchList[Mid] is greater than Item, we adjust the Upper boundary to Mid - 1. Otherwise, we adjust the Lower boundary to Mid + 1. If Found is true, we return Mid; otherwise, -1.

Pseudocode:
```
FUNCTION BinarySearch(SearchList : ARRAY[1:100] OF STRING, Item : STRING) RETURNS INTEGER
DECLARE Lower, Upper, Mid : INTEGER
DECLARE Found : BOOLEAN

Lower <- 1
Upper <- 100
Found <- FALSE
Mid <- -1

WHILE Lower <= Upper AND NOT Found
Mid <- (Lower + Upper) DIV 2
IF SearchList[Mid] = Item THEN
Found <- TRUE
ELSEIF SearchList[Mid] > Item THEN
Upper <- Mid - 1
ELSE
Lower <- Mid + 1
ENDIF
ENDWHILE

IF Found THEN
RETURN Mid
ELSE
RETURN -1
ENDIF
ENDFUNCTION
```

- 1 mark: Correct function header with correct parameters and RETURNS INTEGER.
- 1 mark: Initializing Lower to 1 and Upper to 100.
- 1 mark: Loop with correct termination condition (Lower <= Upper AND NOT Found).
- 1 mark: Correct calculation of Mid using integer division (DIV or equivalent).
- 1 mark: Correct conditional statement checking if SearchList[Mid] is equal to Item.
- 1 mark: Correctly updating Upper <- Mid - 1 if SearchList[Mid] > Item.
- 1 mark: Correctly updating Lower <- Mid + 1 if SearchList[Mid] < Item.
- 1 mark: Returning Mid if found, otherwise returning -1.

The procedure opens the specified file and uses a loop checking EOF to process all lines. For each non-empty line, it extracts the transaction amount (since the salesperson ID and comma take exactly 6 characters, the amount starts at index 7). It then converts the string to a real number using TONUM(), adds it to the running sum, and increments the count. After reading the whole file, it closes the file and outputs the calculated values, handling the division-by-zero risk if the file was empty.

Pseudocode:
```
PROCEDURE SummariseSales(FileName : STRING)
DECLARE Line, AmountStr : STRING
DECLARE Total, Amount : REAL
DECLARE Count : INTEGER

Total <- 0.0
Count <- 0

OPENFILE FileName FOR READ

WHILE NOT EOF(FileName)
READFILE FileName, Line
IF Line <> "" THEN
AmountStr <- MID(Line, 7, LENGTH(Line) - 6)
Amount <- TONUM(AmountStr)
Total <- Total + Amount
Count <- Count + 1
ENDIF
ENDWHILE

CLOSEFILE FileName

IF Count > 0 THEN
OUTPUT "Total Sales: $", Total
OUTPUT "Average Sale: $", (Total / Count)
ELSE
OUTPUT "No transactions found"
ENDIF
ENDPROCEDURE
```

- 1 mark: Correct procedure header (PROCEDURE SummariseSales(FileName : STRING)) and local declarations.
- 1 mark: Correct syntax to open and close the file (OPENFILE ... FOR READ and CLOSEFILE ...).
- 1 mark: Using a WHILE loop with EOF(FileName) to read all lines correctly.
- 1 mark: Using READFILE to read line-by-line.
- 1 mark: Extracting the amount substring using MID(Line, 7, LENGTH(Line) - 6) or equivalent logic.
- 1 mark: Converting the extracted string to a REAL value using TONUM().
- 1 mark: Keeping a running total and counting transactions.
- 1 mark: Formatting output messages correctly, including handling of empty files with an appropriate IF-ELSE check.

1. Separate the mantissa and exponent: Mantissa = 10110000, Exponent = 0101. 2. Calculate the exponent value: Since the exponent 0101 is positive, it equals 1 * 2^2 + 1 * 2^0 = 4 + 1 = 5. 3. Calculate the mantissa value: The mantissa is negative because the sign bit is 1. Convert to two's complement to find its magnitude: flip bits to get 01001111, then add 1 to get 01010000. This represents the binary fraction 0.1010000, which has the denary value 0.5 + 0.125 = 0.625. Thus, the actual value of the mantissa is -0.625. Alternatively, using negative weights: -1 * 2^0 + 0 * 2^-1 + 1 * 2^-2 + 1 * 2^-3 = -1 + 0.25 + 0.125 = -0.625. 4. Multiply the mantissa by 2 raised to the exponent: Value = -0.625 * 2^5 = -0.625 * 32 = -20.

1 mark: Correctly identifies exponent binary '0101' as denary 5. 1 mark: Shows correct conversion of negative mantissa to a denary fraction (e.g., via bit flipping or using negative weight of MSB). 1 mark: Obtains correct denary value of the mantissa as -0.625. 1 mark: Shows the calculation of multiplying the mantissa by 2 raised to the power of the exponent (e.g., -0.625 * 32). 1 mark: Obtains correct final answer of -20.

1. Convert the third octet of the destination IP (67) to binary: 67 = 01000011. 2. For Route A (192.168.64.0/18): The mask /18 has 18 ones, meaning the third octet mask is 11000000 (192). Perform bitwise AND: 01000011 AND 11000000 = 01000000 (64). Resulting network address is 192.168.64.0. This matches. 3. For Route B (192.168.64.0/22): The mask /22 has 22 ones, meaning the third octet mask is 11111100 (252). Perform bitwise AND: 01000011 AND 11111100 = 01000000 (64). Resulting network address is 192.168.64.0. This matches. 4. For Route C (192.168.66.0/23): The mask /23 has 23 ones, meaning the third octet mask is 11111110 (254). Perform bitwise AND: 01000011 AND 11111110 = 01000010 (66). Resulting network address is 192.168.66.0. This matches. 5. Selection: Route C is selected. Although Route A, Route B, and Route C all match, Route C has the longest prefix match (/23 is the most specific mask).

1 mark: Shows subnet calculation for Route A resulting in 192.168.64.0 (matching). 1 mark: Shows subnet calculation for Route B resulting in 192.168.64.0 (matching). 1 mark: Shows subnet calculation for Route C resulting in 192.168.66.0 (matching). 1 mark: Identifies Route C as the chosen route. 1 mark: Explains that Route C is selected because it is the longest prefix match (most specific subnet mask).

We evaluate the expression step-by-step: 1. Push 8: [8]; 2. Push 3: [8, 3]; 3. Push 2: [8, 3, 2]; 4. Operator '*': Pop 2 and Pop 3. Calculate 3 * 2 = 6. Push 6. Stack state: [8, 6]; 5. Operator '-': Pop 6 and Pop 8. Calculate 8 - 6 = 2. Push 2. Stack state: [2]; 6. Push 5: [2, 5]; 7. Push 4: [2, 5, 4]; 8. Operator '+': Pop 4 and Pop 5. Calculate 5 + 4 = 9. Push 9. Stack state: [2, 9]; 9. Operator '*': Pop 9 and Pop 2. Calculate 2 * 9 = 18. Push 18. Stack state: [18]. The final evaluated value is 18.

1 mark: Correct stack state after the first operator '*': [8, 6]. 1 mark: Correct stack state after the operator '-': [2]. 1 mark: Correct stack state after the operator '+': [2, 9]. 1 mark: Correct stack state after the final operator '*': [18]. 1 mark: Correctly states the final value is 18.

(a) Map the terms: \(\bar{A}\bar{B}CD\) -> Row 00, Col 11; \(\bar{A}\bar{B}C\bar{D}\) -> Row 00, Col 10; \(\bar{A}BCD\) -> Row 01, Col 11; \(\bar{A}BC\bar{D}\) -> Row 01, Col 10; \(AB\bar{C}\bar{D}\) -> Row 11, Col 00; \(ABC\bar{D}\) -> Row 11, Col 10; \(A\bar{B}\bar{C}\bar{D}\) -> Row 10, Col 00; \(A\bar{B}C\bar{D}\) -> Row 10, Col 10. (b) Identify groups of size 4: Group 1: Consists of the four 1s in rows 00 and 01, columns 11 and 10. These represent the terms \(\bar{A}\bar{B}C\) and \(\bar{A}BC\). The variable B changes state, so it is eliminated, leaving \(\bar{A}C\). Group 2: Consists of the four 1s in rows 11 and 10, columns 00 and 10. This is the corners/edges on the bottom half. Since the rows are 11 and 10, B changes and is eliminated, leaving A. The columns are 00 and 10, C changes and is eliminated, leaving \(\bar{D}\). This group simplifies to \(A\bar{D}\). All 1s are now covered by these two groups of size 4. Hence, the simplified expression is: \(\bar{A}C + A\bar{D}\).

2 marks: Correctly maps all 8 of the 1s in the K-map (1 mark if 6 or 7 are correct). 2 marks: Identifies the two optimal loops of size 4 (1 mark for group \(\bar{A}C\), 1 mark for group \(A\bar{D}\)). 1 mark: Correctly combines the terms into the final simplified Boolean expression: \(\bar{A}C + A\bar{D}\).

(a) Modulus n = p * q = 3 * 11 = 33. Totient \(\phi(n)\) = (p - 1) * (q - 1) = 2 * 10 = 20. (b) Find d such that \((d \times 3) \pmod{20} = 1\). We can check values of d: d = 1: 3 mod 20 = 3; d = 7: 21 mod 20 = 1. Thus, d = 7. (c) Encrypt plaintext M = 4: \(C = M^e \pmod{n} = 4^3 \pmod{33} = 64 \pmod{33}\). 64 = 1 * 33 + 31. So, C = 31.

1 mark: Correctly calculates n = 33. 1 mark: Correctly calculates \(\phi(n)\) = 20. 1 mark: Correctly finds private key d = 7 with appropriate working. 1 mark: Writes the correct encryption formula \(C = 4^3 \pmod{33}\). 1 mark: Correctly calculates final ciphertext C = 31.

(a) Calculate denary value: Mantissa: 0.0001100. Binary point is after the first bit. The 1s are at positions \(2^{-4}\) (1/16) and \(2^{-5}\) (1/32). Value = 1/16 + 1/32 = 3/32 = 0.09375. Exponent: 0110. This is positive, so it equals 4 + 2 = 6. Value = \(0.09375 \times 2^6 = 0.09375 \times 64 = 6.0\). (b) Normalize the representation: For a positive floating-point number to be normalized, the mantissa must start with '0.1'. To achieve this, shift the mantissa three places to the left: 0.0001100 -> 0.1100000. To compensate for shifting the mantissa left by three, we must subtract 3 from the exponent: Exponent = 6 - 3 = 3. Convert the new exponent 3 to 4-bit two's complement: 0011. Final normalized values: Mantissa = 0.1100000, Exponent = 0011.

1 mark: Shows working for denary value: Mantissa = 0.09375, Exponent = 6, and value = 6.0. 1 mark: Identifies that a normalized positive mantissa must begin with '0.1'. 1 mark: Shifts the mantissa three places to the left to obtain 0.1100000. 1 mark: Decrements the exponent by 3 to compensate for the shift, resulting in 3. 1 mark: States the correct final binary representations: Mantissa = 0.1100000, Exponent = 0011.

Dijkstra's algorithm execution: 1. Initialize distances from A: A=0, B=inf, C=inf, D=inf, E=inf. 2. Visit A (shortest distance = 0): update neighbours: B = 4 (via A), C = 2 (via A). 3. Select unvisited node with smallest distance: C (distance = 2). Visit C: update neighbours: B = min(4, 2 + 1) = 3 (via C); D = 2 + 8 = 10 (via C); E = 2 + 10 = 12 (via C). 4. Select next unvisited node with smallest distance: B (distance = 3). Visit B: update neighbours: D = min(10, 3 + 5) = 8 (via B). 5. Select next unvisited node with smallest distance: D (distance = 8). Visit D: update neighbours: E = min(12, 8 + 2) = 10 (via D). 6. Select final unvisited node: E (distance = 10). Visit E. Shortest path: A -> C -> B -> D -> E. Total weight: 10.

1 mark: Shows correct initialization and first step visiting A (C is 2, B is 4). 1 mark: Shows step visiting C and updating B to 3, D to 10, E to 12. 1 mark: Shows step visiting B and updating D to 8. 1 mark: Shows step visiting D and updating E to 10. 1 mark: Identifies correct final shortest path A -> C -> B -> D -> E and correct total weight 10.

1. Key 43: \(H(43) = 3\). Slot 3 is empty, so insert 43 at index 3. 2. Key 23: \(H(23) = 3\). Slot 3 is occupied (collision). Probing next slot: index 4 is empty, so insert 23 at index 4. 3. Key 72: \(H(72) = 2\). Slot 2 is empty, so insert 72 at index 2. 4. Key 33: \(H(33) = 3\). Slot 3 is occupied. Probe 4 (occupied). Probe 5 (empty), so insert 33 at index 5. 5. Key 52: \(H(52) = 2\). Slot 2 is occupied. Probe 3 (occupied). Probe 4 (occupied). Probe 5 (occupied). Probe 6 (empty), so insert 52 at index 6. Final Hash Table contents: Index 2: 72; Index 3: 43; Index 4: 23; Index 5: 33; Index 6: 52 (other indexes are empty).

1 mark: Inserts 43 at index 3 and 72 at index 2 correctly. 1 mark: Inserts 23 at index 4 with correct description of linear probing (collision at 3). 1 mark: Inserts 33 at index 5 after linear probing from 3 through 4. 1 mark: Inserts 52 at index 6 after linear probing from 2 through 5. 1 mark: Shows correct final state of the entire hash table.

1. Express both numbers in normalized binary floating-point form:
- \(16.0 = 0.10000000_2 \times 2^5\) (Mantissa: `01000000`, Exponent: `0101` which is \(+5\))
- \(0.015625 = 0.10000000_2 \times 2^{-5}\) (Mantissa: `01000000`, Exponent: `1011` which is \(-5\))

2. Align the exponents to the larger value (\(+5\)):
- The difference between exponents is \(5 - (-5) = 10\).
- The mantissa of the smaller number must be shifted 10 positions to the right.

3. Apply the shift to the 8-bit mantissa:
- Shifting `0.10000000` to the right by 10 places yields `0.00000000` (all original significant bits are lost because the register only holds 8 bits).

4. Perform addition:
- \(0.10000000_2 \times 2^5 + 0.00000000_2 \times 2^5 = 0.10000000_2 \times 2^5\) (which is exactly \(16.0\)). Thus, the addition has no effect due to underflow/loss of precision.

- 1 mark: Identify the exponents of both numbers when normalized (\(+5\) for \(16.0\) and \(-5\) for \(0.015625\)).
- 1 mark: Explain that to perform binary addition, the exponents must be aligned to the larger value (\(+5\)).
- 1 mark: Compute the required shift of 10 positions to the right for the smaller number.
- 1 mark: Explain that since the mantissa is constrained to 8 bits, shifting right by 10 places causes all significant bits to be discarded (underflow to zero).
- 1 mark: Show that adding the zeroed mantissa results in the sum being identical to the original large value (\(16.0\)), completing the analytical proof.

1. Convert the final octet of the destination IP `192.168.4.75` to binary: `75` is `01001011_2`.
2. Apply bitwise AND with subnet mask `255.255.255.192` (last octet `192` = `11000000_2`):
- `01001011` AND `11000000` = `01000000_2` (which is `64`). The destination network is `192.168.4.64`. This does not match `192.168.4.0` (Interface A).
3. Apply bitwise AND with subnet mask `255.255.255.224` (last octet `224` = `11100000_2`):
- `01001011` AND `11100000` = `01000000_2` (which is `64`). The destination network is `192.168.4.64`. This matches Interface B.
4. Apply bitwise AND with subnet mask `255.255.0.0`:
- The result is `192.168.0.0`, which matches Interface C.
5. Longest Prefix Match resolution:
- Interface B uses a mask length of 27 bits (`255.255.255.224`).
- Interface C uses a mask length of 16 bits (`255.255.0.0`).
- Since 27 > 16, Interface B is chosen as it has the longest matching prefix.

- 1 mark: Explain that a bitwise AND operation is performed between the destination IP address and the subnet mask of each entry.
- 1 mark: Show the correct binary conversion and AND process for at least one subnet mask (e.g., `01001011` AND `11100000` = `01000000`).
- 1 mark: Identify that both the subnet for Interface B (`192.168.4.64`) and Interface C (`192.168.0.0`) match the destination IP.
- 1 mark: Explain the 'longest prefix match' (or 'most specific route') routing rule used to resolve conflicts when multiple matches occur.
- 1 mark: Conclude that Interface B is selected because `/27` is a longer prefix (more 1s) than `/16`.

MIMD and SIMD differ in key architectural areas:
- **Instruction Execution**: SIMD employs a single control unit to broadcast a single instruction to all processing units, executing them in lockstep. MIMD has multiple independent processors, each with its own control unit and program counter, executing different instructions asynchronously.
- **Data Streams**: SIMD operates on multiple data points simultaneously using one instruction (ideal for parallel vectors). MIMD handles multiple instruction streams operating on multiple data streams.
- **Memory Models**: SIMD systems rely on unified, synchronized memory structures. MIMD systems can utilize either shared memory (e.g., SMP systems where processors share RAM) or distributed memory (e.g., clusters where processors communicate via interconnect messages).
- **Handling Branches**: SIMD is inefficient at handling conditional branches because execution branches must be serialized. MIMD handles branching natively with zero performance impact on other processors.
- **Applications**: SIMD is used in graphics cards (GPUs), vector math, and image processing. MIMD is used in multi-core general-purpose CPUs and supercomputing clusters.

- 1 mark: Contrast instruction execution (SIMD is lock-step/single control unit; MIMD has multiple independent control units/asynchronous execution).
- 1 mark: Contrast data streams (SIMD applies one operation to multiple data elements; MIMD applies multiple operations on multiple distinct data sets).
- 1 mark: Contrast memory architectures (SIMD relies on highly synchronized shared memory; MIMD can use shared memory or distributed memory architectures with message passing).
- 1 mark: Explain how branching/conditional code affects performance (SIMD degrades due to path serialization; MIMD handles independent branches natively without performance loss).
- 1 mark: Provide valid application examples for both (e.g., SIMD: GPUs/image processing; MIMD: multi-core general CPUs/distributed high-performance clusters).

During the SSL/TLS handshake, the client browser performs the following verification steps on the server's certificate:
1. **CA Public Key Retrieval**: The browser reads the identity of the certificate's issuer (the CA) and retrieves that CA's public key from its pre-installed, trusted root certificate store.
2. **Signature Decryption**: The browser decrypts the digital signature attached to the certificate using the CA's public key. Since the signature was encrypted with the CA's private key, successful decryption proves the certificate's authenticity.
3. **Integrity Check**: The browser applies the designated cryptographic hashing algorithm (e.g., SHA-256) to the plaintext fields of the certificate. It compares this calculated hash to the decrypted hash from the digital signature. If they match, the certificate has not been altered.
4. **Domain and Expiry Validation**: The browser verifies that the domain name in the certificate matches the domain name of the accessed website and check that the current date falls within the certificate's validity period.
5. **Revocation Check**: The browser contacts the CA or checks a Certificate Revocation List (CRL) or uses OCSP (Online Certificate Status Protocol) to confirm the certificate has not been revoked.

- 1 mark: State that the browser retrieves the issuing CA's public key from its built-in trusted root store.
- 1 mark: Explain that the browser uses the CA's public key to decrypt the digital signature (proving authenticity because only the CA has the private key).
- 1 mark: Explain the integrity check (calculating a hash of the certificate and comparing it to the decrypted signature hash to ensure no tampering occurred).
- 1 mark: Identify domain matching checks (checking Common Name/SAN against the requested URL) and validity period checks.
- 1 mark: Describe revocation checking using CRLs or OCSP to ensure the certificate remains active and has not been revoked.

1. **Identify Primary Key**: The primary key for the unnormalized table must be the composite key `(ProjectID, EmployeeID)` because only both values together can uniquely determine `HoursWorked`.
2. **Analyze 2NF Violation**: A table is in Second Normal Form (2NF) if it contains no partial dependencies. In this table, `ProjectName` depends solely on `ProjectID`, and `EmployeeName` depends solely on `EmployeeID`. Because these non-key attributes depend on only parts of the composite primary key, this is a partial dependency violation. It is not in 2NF, which means it cannot be in 3NF.
3. **Decomposition to achieve 3NF**:
- Create a `Project` table with primary key `ProjectID`: `Project(ProjectID, ProjectName)`
- Create an `Employee` table with primary key `EmployeeID`: `Employee(EmployeeID, EmployeeName)`
- Create a bridging/assignment table with composite key `(ProjectID, EmployeeID)`: `ProjectAssignment(ProjectID, EmployeeID, HoursWorked)` (where `ProjectID` and `EmployeeID` act as foreign keys).
These three tables now possess only full functional dependencies on their primary keys and no transitive dependencies, satisfying 3NF.

- 1 mark: State that the primary key of the initial table is the composite key `(ProjectID, EmployeeID)`.
- 1 mark: Define the 2NF violation by explaining the partial dependencies (`ProjectName` depends only on `ProjectID`; `EmployeeName` depends only on `EmployeeID`).
- 1 mark: Explain that 3NF requires the table to first be in 2NF (meaning all partial dependencies must be removed) and have no transitive dependencies.
- 1 mark: Specify the correct decomposed tables for entities: `Project(ProjectID, ProjectName)` and `Employee(EmployeeID, EmployeeName)` with their respective primary keys.
- 1 mark: Specify the correct link table `ProjectAssignment(ProjectID, EmployeeID, HoursWorked)` with foreign key constraints and the fully-dependent non-key attribute.

1. **Normalized Negative Mantissa**: A normalized negative number in two's complement mantissa must start with the bits `10...` to represent a value in the range \([-1.0, -0.5)\).
2. **Most Negative Mantissa Value**: The lowest possible value represented by an 8-bit normalized mantissa is exactly \(-1.0\), which corresponds to the binary string `10000000`.
3. **Choosing the Exponent**: To obtain the most negative overall value, we must multiply our negative mantissa by the largest possible positive factor. This requires the largest possible exponent.
4. **Largest Exponent**: The exponent is a 4-bit two's complement integer. The range of a 4-bit two's complement number is \([-8, +7]\). The maximum positive exponent is \(+7\), which is represented in binary as `0111`.
5. **Combining the Bit Patterns**: Joining the 8-bit mantissa (`10000000`) and the 4-bit exponent (`0111`) yields the 12-bit string: `100000000111` (which represents \(-1.0 \times 2^7 = -128.0\)).

- 1 mark: State that a normalized negative mantissa must start with binary bits `1` and `0` (range \([-1.0, -0.5)\)).
- 1 mark: Identify that the most negative mantissa value is \(-1.0\), represented in binary as `10000000`.
- 1 mark: Explain that to find the most negative value overall, the largest positive exponent is required to maximize magnitude.
- 1 mark: Identify the maximum positive exponent in 4-bit two's complement as \(+7\), represented as binary `0111`.
- 1 mark: Combine these components to give the correct 12-bit string `100000000111` (or calculate the correct decimal equivalent of \(-128.0\)).

- **Resource Allocation**: Circuit switching establishes a dedicated physical channel for the duration of a session. Packet switching breaks data into packets that travel independently, sharing transmission lines.
- **Efficiency under Bursty Traffic**: Internet traffic consists of active bursts and idle silences. In circuit switching, idle gaps waste reserved bandwidth. Packet switching dynamically multiplexes packets from different sources across the same links, maximizing link utilization.
- **Performance Degradation (Jitter and Latency)**: In packet switching, packets experience queuing delays at routers and can take different paths. This produces variable delay (jitter) and delivery delays (latency). If packets arrive late or out of order, VoIP audio becomes garbled or broken.
- **Circuit Switching Advantage for Real-time**: Circuit switching provides a fixed, guaranteed route with zero jitter and constant latency, ensuring high performance for real-time audio streams, despite the initial overhead of line setup and bandwidth inefficiency.

- 1 mark: Contrast resource allocation (circuit switching uses a dedicated, reserved circuit; packet switching shares physical paths dynamically using packets).
- 1 mark: Explain why packet switching is efficient for bursty traffic (multiplexes data, allowing other users to use the line during idle periods).
- 1 mark: Explain why circuit switching is inefficient for bursty traffic (reserved line sits idle, wasting network capacity during silences).
- 1 mark: Detail how packet switching introduces latency and jitter (variable routing paths, router queuing delays, and out-of-order delivery).
- 1 mark: Relate these issues to real-time applications like VoIP (which require consistent, timely, sequential delivery of data packets to avoid sound dropouts, making circuit switching's guaranteed constant latency preferable).

The binary search algorithm starts with two pointers representing the search space: `low` at 0 and `high` at the last index of the array (99, or `len(Stock) - 1`). In each iteration of the `while` loop, the midpoint index `mid` is calculated using integer division (`//`). The `ProductID` attribute of the product at `mid` is compared with the target `SearchID`. If they match, `mid` is returned. If the ID at `mid` is less than the search value, the lower boundary `low` is updated to `mid + 1` to search the right half. Otherwise, the upper boundary `high` is updated to `mid - 1` to search the left half. If the loop terminates because `low` exceeds `high`, the target is not present, and `-1` is returned.

1 mark: Correct function header with parameters `Stock` and `SearchID`.
1 mark: Initializing search boundaries: `low` to 0 and `high` to last index.
1 mark: Loop with condition `low <= high` (or equivalent structure).
1 mark: Calculating the midpoint index correctly using integer division.
1 mark: Correctly accessing the attribute `ProductID` from the `Stock` array element.
1 mark: Updating boundaries: setting `low = mid + 1` and `high = mid - 1` based on the comparison.
1 mark: Returning the index when found and returning -1 when the loop finishes without finding the value.

An optimized bubble sort uses nested loops. The outer loop controls the passes, while the inner loop compares adjacent elements. In this descending sort, if the current element is less than the adjacent element (`DataArray[j] < DataArray[j+1]`), they are swapped. A boolean variable `swapped` is initialized to `False` at the beginning of each pass of the outer loop. If a swap occurs, `swapped` is set to `True`. At the end of the inner loop, if `swapped` is still `False`, it means the array is already sorted, and the outer loop is terminated prematurely using a `break` statement.

1 mark: Correct function header with parameter `DataArray`.
1 mark: Outer loop iterating up to `n - 1` times.
1 mark: Inner loop comparing adjacent elements, stopping short of already sorted items (e.g., using `n - i - 1`).
1 mark: Comparison check for descending order (`DataArray[j] < DataArray[j+1]`).
1 mark: Correctly swapping elements using a temporary variable or tuple assignment.
1 mark: Initializing a boolean flag to `False` before each pass and setting it to `True` upon a swap.
1 mark: Checking the flag and exiting the outer loop early if no swaps occurred.

The insertion sort algorithm begins at the second element (index 1) and treats it as the `key`. The inner loop shifts elements of the sorted sublist (`Usernames[0..i-1]`) that are greater than the `key` to the right by one position. The inner loop terminates either when the start of the list is reached (`j < 0`) or an element smaller than or equal to the `key` is found. Finally, the `key` is inserted into its correct position at index `j + 1`.

1 mark: Correct procedure header with parameter.
1 mark: Outer loop iterating from index 1 to the end of the array.
1 mark: Storing the current element in a temporary `key` variable.
1 mark: Correctly initializing the inner pointer variable `j = i - 1`.
1 mark: Inner loop condition checking bounds (`j >= 0`) and key comparison (`Usernames[j] > key` for ascending).
1 mark: Shifting the larger elements one index to the right inside the loop.
1 mark: Correctly inserting the `key` value at position `j + 1` after the inner loop terminates.

A linear search in a 2D array requires examining each element row by row (or column by column). We use nested loops to iterate through every cell in the grid. The outer loop iterates through the row indices from 0 to 9, and the inner loop iterates through the column indices from 0 to 9. We check if `Grid[row][col]` matches `TargetValue`. If a match is found, we immediately return the coordinates as `(row, col)`. If both loops complete and the value was not found, the function returns `(-1, -1)`.

1 mark: Correct function header with parameters `Grid` and `TargetValue`.
1 mark: Outer loop to iterate through all 10 row indices.
1 mark: Inner loop to iterate through all 10 column indices.
1 mark: Correct indexing syntax for a 2D array: `Grid[row][col]`.
1 mark: Comparison of the array cell against `TargetValue`.
1 mark: Immediately returning `(row, col)` upon finding a match.
1 mark: Returning `(-1, -1)` after both loops exhaustively finish without finding a match.

To implement inheritance in Python, define the class MediaItem with a constructor setting its private variables (using double leading underscores). Write public getter methods to allow child classes or external objects to access these values. Next, define Book with MediaItem passed in parentheses to declare inheritance. Inside the Book constructor, use super().__init__(...) to initialize the parent's attributes, then set __Author. The GetDetails() method retrieves parent properties using getter methods and builds the formatted string.

1 mark: Define class MediaItem with constructor and private attributes __Title and __RunTime.
1 mark: Implement public getters GetTitle() and GetRunTime().
1 mark: Define class Book inheriting from MediaItem with private attribute __Author.
1 mark: Implement Book constructor taking three parameters.
1 mark: Call parent class constructor using super().__init__(title, runtime).
1 mark: Implement GetDetails() calling GetTitle() and GetRunTime() and formatting output string correctly.

In this composite relationship, a Booking object stores a reference to a Customer object in its private field __Client. Since __CustomerName is private within Customer, Booking cannot access it directly. Thus, Customer must provide the public getter GetName() which Booking calls within GetBookingSummary().

1 mark: Define Customer class with constructor initialising private attributes.
1 mark: Implement public getters GetName() and GetEmail() in Customer.
1 mark: Define Booking class with constructor taking bookingID and client.
1 mark: Correctly assign client parameter (representing Customer object) to private attribute __Client.
1 mark: Implement GetBookingSummary() method in Booking.
1 mark: Retrieve customer name inside GetBookingSummary() by calling GetName() on the __Client reference and return correctly formatted string.

Polymorphism allows a subclass to override a method in the superclass with its own specialized implementation. Since __PowerRating is private in Appliance, SmartAppliance must use self.GetPower() to retrieve the rating value before performing the custom calculation.

1 mark: Define base class Appliance with constructor and private attributes.
1 mark: Implement getter method GetPower() returning __PowerRating.
1 mark: Implement CalculatePower(hours) in Appliance returning power * hours.
1 mark: Define subclass SmartAppliance inheriting from Appliance.
1 mark: Correctly call parent constructor using super().__init__(brand, powerRating) and assign private attribute __EfficiencyFactor.
1 mark: Override CalculatePower(hours) in SmartAppliance correctly accessing base power via self.GetPower() and incorporating __EfficiencyFactor.

This scenario models encapsulation and robustness in object state. The state parameter __Balance can only be updated via the verified public methods Deposit and Withdraw. Conditions ensure negative values or excessive withdrawals are blocked.

1 mark: Correct class header and constructor initialising __AccountNumber to the parameter and __Balance to 0.0.
1 mark: Implement Deposit method checking if amount > 0.
1 mark: Correctly add amount to balance and return True (otherwise returning False) in Deposit.
1 mark: Implement Withdraw method checking both conditions (amount > 0 and __Balance >= amount).
1 mark: Correctly subtract amount from balance and return True (otherwise returning False) in Withdraw.
1 mark: Implement getter GetBalance() returning __Balance.

The Fleet class manages an aggregation of Vehicle instances. Inside the Fleet constructor, an empty list __FleetList is initialized. AddVehicle checks if __Count < 10 before appending and incrementing. FindVehicle iterates through the existing vehicles in __FleetList using range(__Count), calls GetRegNo() on each vehicle object, compares it to the target parameter reg, and returns the appropriate index or -1 if not found.

1 mark: Define Vehicle class with constructor and GetRegNo() getter.
1 mark: Define Fleet class with constructor setting __FleetList to empty list and __Count to 0.
1 mark: Implement AddVehicle(newVehicle) checking if __Count < 10.
1 mark: In AddVehicle, append object to list, increment count, and return True (or False if full).
1 mark: Implement search in FindVehicle(reg) iterating up to __Count (or length of list).
1 mark: Access each vehicle's registration via GetRegNo() inside FindVehicle, compare with parameter reg, return index if found, else return -1.

The procedure first checks if the queue is full by comparing NumItems with the maximum capacity of 5. If it is full, an appropriate error message is displayed. Otherwise, if the queue is currently empty (indicated by HeadPointer being -1), HeadPointer is initialized to 0. The TailPointer is then updated circularly using modulo 5 arithmetic: TailPointer = (TailPointer + 1) % 5. Finally, the new item is stored in QueueArray at the updated TailPointer index, and NumItems is incremented by 1.

1 mark: Correctly check if the queue is full (NumItems == 5) and output an error message.
1 mark: Check if the queue is empty (HeadPointer == -1) and set HeadPointer to 0.
1 mark: Correctly calculate the circular update for TailPointer using modulo or equivalent logic.
1 mark: Assign NewItem to the QueueArray at index TailPointer.
1 mark: Increment NumItems by 1.
1 mark: Declare global scope for pointers/variables and write correct Python syntax.

The Pop function must first handle stack underflow by checking if TopPointer is -1. If it is, the function prints an error message and returns -1. If elements exist, it retrieves the item stored at StackArray[TopPointer], decrements TopPointer by 1, and returns the retrieved item.

1 mark: Check for empty stack condition (TopPointer == -1).
1 mark: Correctly output an underflow error message when empty.
1 mark: Return -1 when stack underflow occurs.
1 mark: Retrieve and store the value from StackArray at TopPointer.
1 mark: Decrement TopPointer by 1.
1 mark: Return the popped value from the non-empty path.

The function uses recursion to traverse the binary search tree. There are two base cases:
1. If CurrentNodePointer is -1, the tree or subtree is empty, meaning the value does not exist, so the function returns -1.
2. If the current node's data matches SearchValue, the search is successful, and the function returns the CurrentNodePointer.

For the recursive step:
- If SearchValue is less than the current node's data, the function calls itself with the left child's pointer.
- If SearchValue is greater, it calls itself with the right child's pointer.

1 mark: Base case checking if pointer is -1 and returning -1.
1 mark: Base case checking if data equals search value and returning current pointer.
1 mark: Comparison check if SearchValue is less than current node data.
1 mark: Recursive call using LeftPointer with matching return.
1 mark: Recursive call using RightPointer with matching return.
1 mark: Correct function header and parameters matching recursive calls.