MetadataPastPaper.sampleTitle

(a) To represent \(-78\) in 8-bit two's complement:
1. Find the binary representation for positive 78:
\(78 = 64 + 8 + 4 + 2 = 01001110_2\)
2. Invert all bits (one's complement):
\(10110001_2\)
3. Add 1 (two's complement):
\(10110001 + 1 = 10110010_2\)

(b) To convert \(10110010_2\) to hexadecimal, split into two 4-bit nibbles:
1. Left nibble: \(1011_2 = 11_{10} = B_{16}\)
2. Right nibble: \(0010_2 = 2_{16}\)
Combined Hexadecimal value: \(B2_{16}\)

(c) BCD is used because each decimal digit is converted individually into 4 binary bits. This prevents rounding/representation errors that occur with floating-point binary when representing certain decimal fractions. It is also easier to decode and display. One common application is digital calculators or digital watch displays.

(d) Vector graphics are stored as a set of mathematical instructions/geometric formulas and parameters (like coordinates, stroke thickness, fill color) rather than mapping individual pixels. Three typical objects are: Line, Circle, Rectangle (or Polygon, Arc).

(e) Lossless compression reduces file size by identifying and encoding patterns without losing any original data, allowing the exact original file to be reconstructed. Lossy compression permanently discards less essential data to achieve much smaller file sizes. Lossless must be used for program source files because even a tiny change (like a single character altered or omitted) will corrupt the program, changing its meaning or causing compile-time syntax errors.

Part (a) [2 marks]:
- 1 mark for showing correct working (e.g., finding representation of +78 or 1's complement).
- 1 mark for correct final binary answer: 10110010.

Part (b) [2 marks]:
- 1 mark for separating into nibbles or demonstrating hex conversion technique.
- 1 mark for correct final answer: B2 (or B2_16).

Part (c) [3 marks]:
- 1 mark for explaining that BCD avoids binary rounding/fraction representation errors.
- 1 mark for explaining that it is easier/faster to convert and display directly on a screen.
- 1 mark for identifying a valid application (e.g., calculator, digital clock, cash register).

Part (d) [4 marks]:
- 1 mark for explaining that vector graphics use mathematical/geometric properties/formulas and attributes (rather than individual pixels).
- 3 marks for identifying three distinct drawing objects (e.g., Line, Circle, Rectangle, Arc, Curve, Polygon).

Part (e) [4 marks]:
- 1 mark for explaining that lossless allows perfect reconstruction with no data lost.
- 1 mark for explaining that lossy permanently discards unnecessary/redundant data.
- 1 mark for stating that losing even one character in a source file ruins the syntax/meaning.
- 1 mark for stating this causes compilation/execution errors.

(a)
(i) Program Counter (PC): Holds the memory address of the next instruction to be fetched.
(ii) Memory Address Register (MAR): Holds the address in memory that is currently being accessed for a read or write operation.
(iii) Memory Data Register (MDR): Temporarily holds data read from memory, or data waiting to be written to memory.
(iv) Current Instruction Register (CIR): Holds the instruction that is currently being decoded and executed.

(b) The Fetch stage represented in RTN is:
1. \(MAR \leftarrow [PC]\) (The address in PC is copied to MAR)
2. \(PC \leftarrow [PC] + 1\) (PC is incremented to point to the next instruction address)
3. \(MDR \leftarrow [[MAR]]\) (The instruction at the address in MAR is loaded into MDR)
4. \(CIR \leftarrow [MDR]\) (The instruction is copied from MDR to CIR for decoding)

(c)
- Direct Addressing: The operand in the instruction is the actual address of the data. For example, `LDD 200` directly loads the accumulator with whatever data value is stored at memory address 200.
- Indirect Addressing: The operand is a memory address that contains the final/actual address of the data. For example, `LDI 200` looks at memory address 200 to find a second address (e.g., 350) and then loads the accumulator with the data value stored at address 350.

(d)
- Address Bus: Unidirectional (travels from CPU to memory/IO components only).
- Data Bus: Bidirectional (carries data back and forth between the CPU, memory, and IO components).

Part (a) [4 marks]:
- 1 mark for correct definition of PC.
- 1 mark for correct definition of MAR.
- 1 mark for correct definition of MDR.
- 1 mark for correct definition of CIR.

Part (b) [5 marks]:
- 1 mark for \(MAR \leftarrow [PC]\)
- 1 mark for \(PC \leftarrow [PC] + 1\)
- 1 mark for loading memory content: \(MDR \leftarrow [[MAR]]\) (or equivalent descriptive notation)
- 1 mark for copying to CIR: \(CIR \leftarrow [MDR]\)
- 1 mark for logical sequential flow linking the fetch steps correctly.

Part (c) [4 marks]:
- 1 mark for defining direct addressing (address points directly to data).
- 1 mark for an accurate direct addressing example (e.g., LDD 200 loads content at 200).
- 1 mark for defining indirect addressing (address points to an address holding the data).
- 1 mark for an accurate indirect addressing example (e.g., LDI 200 fetches value stored at address found in 200).

Part (d) [2 marks]:
- 1 mark for: Address Bus is unidirectional.
- 1 mark for: Data Bus is bidirectional (or Control Bus is bidirectional).

(a)
- Primary Key: A field (or group of fields) that uniquely identifies a unique record in a database table.
- Foreign Key: An attribute in one table that references the primary key of another table, creating a relational link.
- Referential Integrity: A database property ensuring that relationships between tables remain consistent. Any foreign key value must have a matching primary key value in the related table (no orphaned records).

(b)
(i) A table is not in 1NF if it contains multi-valued attributes or repeating groups (non-atomic values) in a single row (e.g., multiple courses listed together for one employee ID). To convert it to 1NF, ensure that all attribute values are atomic by creating a separate record/row for each unique combination of employee and course.

(ii) Normalization steps:
- 1NF Schema: `CourseBooking(EmployeeID, EmployeeName, CourseCode, CourseTitle, DateEnrolled)` where the primary key is a composite key: `(EmployeeID, CourseCode)`.
- Convert to 2NF: Eliminate partial dependencies.
- `EmployeeName` depends only on part of the key (`EmployeeID`).
- `CourseTitle` depends only on part of the key (`CourseCode`).
- `DateEnrolled` depends on the full composite key `(EmployeeID, CourseCode)`.
- This yields three tables:
1. `Employee(EmployeeID, EmployeeName)` with PK: `EmployeeID`
2. `Course(CourseCode, CourseTitle)` with PK: `CourseCode`
3. `Booking(EmployeeID, CourseCode, DateEnrolled)` with Composite PK: `(EmployeeID, CourseCode)` and FKs: `EmployeeID` (ref `Employee`), `CourseCode` (ref `Course`).
- Convert to 3NF: Eliminate transitive dependencies. In the 2NF tables, no non-key field depends on another non-key field. Therefore, the tables are already in 3NF.

(c) SQL Query:
```sql
SELECT Employee.EmployeeName, Course.CourseTitle
FROM Booking
JOIN Employee ON Booking.EmployeeID = Employee.EmployeeID
JOIN Course ON Booking.CourseCode = Course.CourseCode
WHERE Booking.DateEnrolled > '2023-01-01';
```

Part (a) [4 marks]:
- 1 mark for defining Primary Key (unique identifier of a row/record).
- 1 mark for defining Foreign Key (field in one table referencing a primary key in another table).
- 2 marks for defining Referential Integrity (ensuring foreign key refers to a valid primary key / no orphaned records).

Part (b)(i) [2 marks]:
- 1 mark for stating that multiple entries in a field violate atomicity/contain repeating groups.
- 1 mark for stating that to resolve it, each row must contain only atomic values (split into multiple rows/records).

Part (b)(ii) [6 marks]:
- 1 mark for explaining partial key dependency removal (transition from 1NF to 2NF).
- 1 mark for explaining transitive dependency check (transition to 3NF).
- 1 mark for `Employee` table with PK `EmployeeID` correctly identified.
- 1 mark for `Course` table with PK `CourseCode` correctly identified.
- 1 mark for `Booking` table with composite PK `(EmployeeID, CourseCode)` correctly identified.
- 1 mark for correctly identifying foreign keys in `Booking` linking to `Employee` and `Course` tables.

Part (c) [3 marks]:
- 1 mark for SELECT clause selecting `EmployeeName` and `CourseTitle` (with table aliases if needed).
- 1 mark for FROM clause containing necessary JOINs (or Cartesian product linking primary-foreign keys in WHERE clause).
- 1 mark for WHERE clause restricting `DateEnrolled > '2023-01-01'`.

(a) Packet switching steps:
1. The sender splits the data file into smaller chunks called packets.
2. A header is added to each packet containing metadata (source IP, destination IP, packet sequence number, and error-checking/checksum data).
3. Each packet is sent individually across the network.
4. Routers dynamically direct packets along the most efficient path; packets may take completely different routes based on congestion.
5. Packets arrive at the destination, potentially out of order.
6. The receiver uses sequence numbers in the headers to reassemble packets back into the original file, checking for errors and requesting retransmission of lost/corrupt packets.

(b) Differences between IPv4 and IPv6:
- IPv4 uses 32-bit addresses; IPv6 uses 128-bit addresses.
- IPv4 addresses are represented in denary/decimal format (separated by dots); IPv6 addresses are represented in hexadecimal format (separated by colons).
- IPv4 has about 4.3 billion possible unique addresses (leading to address exhaustion); IPv6 has over \(3.4 \times 10^{38}\) unique addresses.

(c)
- Public IP address: An address that is unique across the entire global internet and is directly accessible by other public devices on the internet.
- Private IP address: An address used inside a private local area network (LAN) that is not visible or routable on the public internet.
- Why private IPs are used: They conserve the limited pool of public IPv4 addresses (using Network Address Translation (NAT) to let a whole LAN share one public IP) and improve network security because local devices are shielded from direct external attacks.

(d)
1. The user inputs a human-readable URL (e.g., `www.example.com`) into their web browser.
2. The browser contacts a DNS server to search for the domain name in its distributed database.
3. The DNS server translates/resolves the domain name into its corresponding numerical public IP address and returns this IP address to the browser, allowing it to initiate a direct connection with the web server.

Part (a) [5 marks max]:
- 1 mark for stating that data is split into smaller units called packets.
- 1 mark for explaining that each packet gets a header containing source/destination IPs and sequence numbers.
- 1 mark for stating packets travel independently across the network.
- 1 mark for stating routers determine the optimal route for each packet dynamically.
- 1 mark for stating the destination uses sequence numbers to reassemble packets in order.
- 1 mark for stating that packet errors/losses prompt retransmission.

Part (b) [3 marks]:
- 1 mark per valid difference (address length, number base/notation, total address space size, security features) up to a maximum of 3 marks.

Part (c) [4 marks]:
- 1 mark for defining Public IP (globally unique, accessible over internet).
- 1 mark for defining Private IP (local LAN scope only, not publically routable).
- 1 mark for stating private IPs allow conservation of public IPv4 addresses via NAT.
- 1 mark for stating private IPs enhance security by masking internal network structure.

Part (d) [3 marks]:
- 1 mark for stating DNS maintains a directory of domain names mapped to IP addresses.
- 1 mark for stating that browser queries DNS with the domain name.
- 1 mark for stating DNS returns the IP address, allowing the browser to connect to the target web host.

Step 1: Apply De Morgan's Law to the first term \(\overline{A \cdot B}\):
\(X = (\overline{A} + \overline{B}) \cdot (\overline{A} + B) \cdot (B + \overline{C})\)

Step 2: Simplify the product of the first two terms \((\overline{A} + \overline{B}) \cdot (\overline{A} + B)\).
Using the Distributive Law in reverse:
\((\overline{A} + \overline{B}) \cdot (\overline{A} + B) = \overline{A} + (\overline{B} \cdot B)\)

Step 3: Apply the Complement Law (\(\overline{B} \cdot B = 0\)) and Identity Law (\(\overline{A} + 0 = \overline{A}\)):
\(\overline{A} + 0 = \overline{A}\)

Step 4: Substitute this back into the expression:
\(X = \overline{A} \cdot (B + \overline{C})\)

Step 5: Apply the Distributive Law to expand the expression into sum-of-products (SOP) form:
\(X = \overline{A}B + \overline{A}\overline{C}\)

- 1 mark: Correct application of De Morgan's Law to get \(\overline{A} + \overline{B}\).
- 1 mark: Correct expansion or distribution of \((\overline{A} + \overline{B}) \cdot (\overline{A} + B)\).
- 1 mark: Correctly simplifying \((\overline{A} + \overline{B}) \cdot (\overline{A} + B)\) to \(\overline{A}\) using Complement/Identity laws.
- 1 mark: Correctly stating at least two laws used (e.g., De Morgan's, Distributive, Complement, or Identity laws).
- 1 mark: Correct final simplified expression in either SOP form \(X = \overline{A}B + \overline{A}\overline{C}\) or factored form \(X = \overline{A}(B + \overline{C})\).

Part (a):
The Karnaugh Map has rows for A (0, 1) and columns for BC (00, 01, 11, 10):
- Row 0 (A = 0): Columns 00=0, 01=1, 11=1, 10=1
- Row 1 (A = 1): Columns 00=0, 01=1, 11=1, 10=0

Part (b):
- Group 1: A 2x2 group (quad) of 1s in columns 01 and 11 across both rows (A = 0 and A = 1). Since A changes (0 to 1) and B changes (0 to 1), only C remains constant at 1. This loop simplifies to \(C\).
- Group 2: A 1x2 group (pair) of 1s in row A = 0, columns 11 and 10. Since A is constant at 0, B is constant at 1, and C changes (1 to 0), this loop simplifies to \(\overline{A}B\).

Part (c):
Combining the terms gives the simplified sum-of-products expression:
\(Y = C + \overline{A}B\)

- 1 mark: Correctly mapping all five 1s to the K-map grid.
- 1 mark: Identifying the 2x2 group (quad) spanning columns 01 and 11 across both rows.
- 1 mark: Correctly simplifying the quad to \(C\).
- 1 mark: Identifying the 1x2 group (pair) in row 0, columns 11 and 10.
- 1 mark: Correctly simplifying the pair to \(\overline{A}B\) and stating the final expression \(Y = C + \overline{A}B\).

Part (a):
- Sum output: \(S = A \oplus B \oplus C_{in}\)
- Carry-out output: \(C_{out} = (A \cdot B) + (C_{in} \cdot (A \oplus B))\) (or equivalent algebraic form, such as \(C_{out} = AB + BC_{in} + AC_{in}\))

Part (b):
- First Half Adder: Takes external inputs \(A\) and \(B\). It outputs an intermediate sum \(S_1 = A \oplus B\) and an intermediate carry \(C_1 = A \cdot B\).
- Second Half Adder: Takes the intermediate sum \(S_1\) from the first Half Adder and the external Carry-in (\(C_{in}\)) as its inputs. It outputs the final Sum (\(S = S_1 \oplus C_{in}\)) and a second intermediate carry \(C_2 = S_1 \cdot C_{in}\).
- Additional Gate: An OR gate is used.
- Inputs to OR Gate: The intermediate carry outputs from both Half Adders (\(C_1\) and \(C_2\)). The output of this OR gate is the final Carry-out (\(C_{out} = C_1 + C_2\)).

- 1 mark: Correct Boolean expression for Sum (\(S\)) output.
- 1 mark: Correct Boolean expression for Carry-out (\(C_{out}\)) output.
- 1 mark: Correct description of the first Half Adder taking inputs \(A\) and \(B\) to produce intermediate sum and carry.
- 1 mark: Correct description of the second Half Adder taking the intermediate sum and \(C_{in}\) to produce the final Sum.
- 1 mark: Correct identification of the OR gate combining both intermediate carry signals to produce the final \(C_{out}\).

(a) Trace of CalcPower:
Initial: count = 0
- i = 1, j = 2: DataList[1] + DataList[2] = 2 + 3 = 5 <= 10. IF is False. j becomes 3.
- i = 1, j = 3: DataList[1] + DataList[3] = 2 + 5 = 7 <= 10. IF is False. j becomes 4.
- i = 1, j = 4: DataList[1] + DataList[4] = 2 + 5 = 7 <= 10. IF is False. j becomes 5.
- i = 1, j = 5: DataList[1] + DataList[5] = 2 + 8 = 10 <= 10. IF is True, count becomes 1. j becomes 6.
- i = 1, j = 6: DataList[1] + DataList[6] = 2 + 10 = 12 > 10. Loop terminates.

- i = 2, j = 3: DataList[2] + DataList[3] = 3 + 5 = 8 <= 10. IF is False. j becomes 4.
- i = 2, j = 4: DataList[2] + DataList[4] = 3 + 5 = 8 <= 10. IF is False. j becomes 5.
- i = 2, j = 5: DataList[2] + DataList[5] = 3 + 8 = 11 > 10. Loop terminates.

- i = 3, j = 4: DataList[3] + DataList[4] = 5 + 5 = 10 <= 10. IF is True, count becomes 2. j becomes 5.
- i = 3, j = 5: DataList[3] + DataList[5] = 5 + 8 = 13 > 10. Loop terminates.

- i = 4, j = 5: DataList[4] + DataList[5] = 5 + 8 = 13 > 10. Loop terminates.

- i = 5, j = 6: DataList[5] + DataList[6] = 8 + 10 = 18 > 10. Loop terminates.

Final returned value: 2.

(b) (i) The worst-case scenario occurs when the condition `(DataList[i] + DataList[j] <= Target)` is always true. This happens when the sum of any two elements in the array is less than or equal to the `Target`.

(ii) For N = 6, the inner loop runs N - i times for each i:
- i = 1: 5 times
- i = 2: 4 times
- i = 3: 3 times
- i = 4: 2 times
- i = 5: 1 time
Total iterations = 5 + 4 + 3 + 2 + 1 = 15.

In general, the number of comparison operations is \( \frac{N(N - 1)}{2} \), which gives a worst-case time complexity of \( O(N^2) \).

(a) Tracing (4 marks):
- 1 mark: Correctly tracing the first outer loop pass (i=1) showing j changing from 2 to 6 and count incrementing to 1.
- 1 mark: Correctly tracing the second outer loop pass (i=2) showing j changing from 3 to 5 and loop terminating when sum > 10.
- 1 mark: Correctly tracing the third outer loop pass (i=3) showing count incrementing to 2.
- 1 mark: Correctly tracing the remaining outer loop passes and identifying final returned value of 2.

(b) (i) Worst-Case Condition (1 mark):
- 1 mark: Identifying that the sum of any two elements must be <= Target (i.e., the loop condition is never False due to the sum comparison).

(ii) Iterations & Complexity (3 marks):
- 1 mark: Showing calculation of iterations: 5 + 4 + 3 + 2 + 1 = 15.
- 1 mark: Stating the general form: \( \frac{N(N-1)}{2} \).
- 1 mark: Correctly identifying Big O complexity as \( O(N^2) \).

(a) (i) Algorithm B (Binary Search) relies on the array being sorted because it divides the search space in half based on whether the target key is greater than or less than the midpoint element. If the array is unsorted, this logical division is invalid, and elements might be missed.
(ii) \(N\) comparisons (or 1024 if using the size in part b).
(iii) \( \frac{N + 1}{2} \) (or approximately \( \frac{N}{2} \)).

(b) (i) 1024 comparisons.
(ii) Binary search reduces the search space by half each time. The maximum number of comparisons is calculated using \( \lfloor \log_2(N) \rfloor + 1 \) (or \( \lceil \log_2(N+1) \rceil \)).
For \(N = 1024\):
- 1st comparison: size 1024 -> 512
- 2nd comparison: size 512 -> 256
- 3rd comparison: size 256 -> 128
- 4th comparison: size 128 -> 64
- 5th comparison: size 64 -> 32
- 6th comparison: size 32 -> 16
- 7th comparison: size 16 -> 8
- 8th comparison: size 8 -> 4
- 9th comparison: size 4 -> 2
- 10th comparison: size 2 -> 1
- 11th comparison: size 1 -> 0 (final check fails)
Therefore, the maximum number of comparisons is 11 (accept 10 if assuming immediate termination on finding single element in loop).

(iii) When the search target is located at the very first element of the array (index 1). Algorithm A would find it in 1 comparison, whereas Algorithm B would start searching from the middle of the array, requiring around 10 comparisons.

(a) Unsorted Array (3 marks):
- (i) 1 mark: Mentioning that Binary Search relies on the array being sorted to make a decision about which half to discard.
- (ii) 1 mark: Stating \(N\) comparisons.
- (iii) 1 mark: Stating \( \frac{N+1}{2} \) or \( \frac{N}{2} \).

(b) Sorted Array (5 marks):
- (i) 1 mark: 1024 comparisons.
- (ii) 3 marks:
- 1 mark: Stating the formula or relationship: \( \log_2(N) \) or dividing by 2 successively.
- 1 mark: Showing step-by-step reduction of search space (e.g., 1024 -> 512 -> ... -> 1).
- 1 mark: Correct final answer (11 or 10, depending on implementation/working shown).
- (iii) 1 mark: Stating that the target is at the beginning of the array / first element.

(a) Trace of CalcPower(3, 5):
- Call 1: CalcPower(3, 5) -> Exp is odd. Calls CalcPower(3, 4).
- Call 2: CalcPower(3, 4) -> Exp is even. Calls CalcPower(3, 2).
- Call 3: CalcPower(3, 2) -> Exp is even. Calls CalcPower(3, 1).
- Call 4: CalcPower(3, 1) -> Exp is odd. Calls CalcPower(3, 0).
- Call 5: CalcPower(3, 0) -> Exp is 0. Returns 1.

Unwinding the stack:
- Call 5 returns 1.
- Call 4 returns 3 * 1 = 3.
- Call 3 gets Temp = 3, returns 3 * 3 = 9.
- Call 2 gets Temp = 9, returns 9 * 9 = 81.
- Call 1 returns 3 * 81 = 243.

(b) (i) \( O(\log \text{Exp}) \)
(ii) The naive algorithm decrements the exponent by 1 at each step, resulting in a time complexity of \( O(\text{Exp}) \). The `CalcPower` algorithm halves the exponent (`Exp / 2`) whenever it is even. Since even/odd exponents alternate, the size of the exponent is halved at least every two steps. This reduces the number of recursive calls drastically, giving \( O(\log \text{Exp}) \) time complexity instead of \( O(\text{Exp}) \).
(iii) \( O(\log \text{Exp}) \) space complexity, as the height of the recursive call stack is proportional to the number of active activation records, which is bounded by \( O(\log \text{Exp}) \).

(a) Trace (4 marks):
- 1 mark: Show all recursive calls with correct arguments in sequence: (3, 5) -> (3, 4) -> (3, 2) -> (3, 1) -> (3, 0).
- 1 mark: Correct base case return value (returns 1 for Exp = 0).
- 1 mark: Correct intermediate values returned during unwinding (returns 3 for Exp=1, 9 for Exp=2, 81 for Exp=4).
- 1 mark: Correct final return value of 243.

(b) Efficiency (4 marks):
- (i) 1 mark: \( O(\log \text{Exp}) \).
- (ii) 2 marks:
- 1 mark: Identifying that naive is \( O(\text{Exp}) \) because it decrements by 1 each time.
- 1 mark: Explaining that this algorithm is \( O(\log \text{Exp}) \) because it halves the exponent size on even steps.
- (iii) 1 mark: \( O(\log \text{Exp}) \).

(a) Selection Sort

(b) (i) The outer loop runs with `i` from 1 to 4 (`N-1`). The inner loop runs with `j` from `i+1` to 5 (`N`).
- For i = 1: j runs 2 to 5 -> 4 comparisons.
- For i = 2: j runs 3 to 5 -> 3 comparisons.
- For i = 3: j runs 4 to 5 -> 2 comparisons.
- For i = 4: j runs 5 to 5 -> 1 comparison.
Total comparisons = 4 + 3 + 2 + 1 = 10.

(ii)
- Minimum swaps: 0. This occurs when the array is already sorted. The variable `minIndex` will always be equal to `i` at the end of the inner loop, so `minIndex <> i` is never true.
- Maximum swaps: 4 (or `N - 1`). This occurs when the minimum element is always at a different index from the current search index `i` on every step of the outer loop.

(iii) No, the initial order of elements does not affect the time complexity (specifically the number of comparisons). The nested loop structure runs through to completion regardless of whether the array is fully sorted, reverse-sorted, or random. The comparison count is always \( O(N^2) \).

(a) Identification (1 mark):
- 1 mark: Selection Sort.

(b) (i) Comparisons (3 marks):
- 1 mark: Identifying that the comparisons occur in the inner loop.
- 1 mark: Showing the sum sequence: 4 + 3 + 2 + 1.
- 1 mark: Correct total of 10 comparisons.

(ii) Swaps (2 marks):
- 1 mark: Minimum swaps = 0 (with explanation that no swaps happen when list is already sorted).
- 1 mark: Maximum swaps = 4 (with explanation that one swap occurs per outer loop step if minIndex changes).

(iii) Complexity Independence (2 marks):
- 1 mark: Stating that initial order does NOT affect time complexity / number of comparisons.
- 1 mark: Explaining that the loops always run to completion regardless of array values.

(a) Tracing the insertions:
1. Key 42: Hash(42) = 42 MOD 10 = 2. Slot 2 is empty -> Table[2] = 42.
2. Key 23: Hash(23) = 23 MOD 10 = 3. Slot 3 is empty -> Table[3] = 23.
3. Key 32: Hash(32) = 32 MOD 10 = 2. Slot 2 is full. Linear probe to Slot 3 (full), then to Slot 4. Slot 4 is empty -> Table[4] = 32.
4. Key 53: Hash(53) = 53 MOD 10 = 3. Slot 3 is full. Linear probe to Slot 4 (full), then to Slot 5. Slot 5 is empty -> Table[5] = 53.
5. Key 72: Hash(72) = 72 MOD 10 = 2. Slot 2 is full. Linear probe: Slot 3 (full), Slot 4 (full), Slot 5 (full), Slot 6 (empty) -> Table[6] = 72.

Final Hash Table:
- Index 0: Empty
- Index 1: Empty
- Index 2: 42
- Index 3: 23
- Index 4: 32
- Index 5: 53
- Index 6: 72
- Index 7: Empty
- Index 8: Empty
- Index 9: Empty

(b) (i) To search for 72:
- Hash(72) = 2.
- Compare with Table[2] (42) -> No match (1st comparison)
- Compare with Table[3] (23) -> No match (2nd comparison)
- Compare with Table[4] (32) -> No match (3rd comparison)
- Compare with Table[5] (53) -> No match (4th comparison)
- Compare with Table[6] (72) -> Match found (5th comparison)
Total comparisons = 5.

(ii) To search for 12:
- Hash(12) = 2.
- Compare with Table[2] (42) -> No match (1)
- Compare with Table[3] (23) -> No match (2)
- Compare with Table[4] (32) -> No match (3)
- Compare with Table[5] (53) -> No match (4)
- Compare with Table[6] (72) -> No match (5)
- Compare/Check Table[7] (Empty) -> Empty slot found (6)
The search stops immediately when an empty slot is reached because if 12 were in the table, it would have been inserted sequentially prior to encountering this first empty slot. Total comparisons/checks = 6.

(iii) Increase the size of the table (to reduce the load factor / ratio of filled slots to total slots).

(a) Table State (3 marks):
- 1 mark: Correct placement of 42 at Index 2 and 23 at Index 3.
- 1 mark: Correct placement of 32 at Index 4 and 53 at Index 5.
- 1 mark: Correct placement of 72 at Index 6 and showing all other slots as empty.

(b) (i) Search 72 (2 marks):
- 1 mark: Detailing the step-by-step sequential comparisons from index 2 to index 6.
- 1 mark: Correct final answer of 5 comparisons.

(ii) Search 12 (2 marks):
- 1 mark: Explaining that the search stops upon reaching the empty slot at index 7.
- 1 mark: Correct final answer of 6 comparisons/checks (or 5 comparisons with keys + 1 check for empty).

(iii) Reduction of Collisions (1 mark):
- 1 mark: Suggesting increasing the table size (reducing the load factor) or using a larger prime number for table size.

PROCEDURE ProcessTemperatures(TempData : ARRAY[1:50] OF REAL)
DECLARE Sum : REAL
DECLARE Average : REAL
DECLARE BelowCount, AboveCount : INTEGER
DECLARE CurrentSeq, MaxSeq : INTEGER
DECLARE i : INTEGER

// 1. Calculate Average
Sum <- 0.0
FOR i <- 1 TO 50
Sum <- Sum + TempData[i]
NEXT i
Average <- Sum / 50.0

// 2. Count Below and Above Average
BelowCount <- 0
AboveCount <- 0
FOR i <- 1 TO 50
IF TempData[i] < Average THEN
BelowCount <- BelowCount + 1
ELSE
IF TempData[i] > Average THEN
AboveCount <- AboveCount + 1
ENDIF
ENDIF
NEXT i

// 3. Find Longest Increasing Sequence
CurrentSeq <- 1
MaxSeq <- 1
FOR i <- 2 TO 50
IF TempData[i] > TempData[i - 1] THEN
CurrentSeq <- CurrentSeq + 1
ELSE
IF CurrentSeq > MaxSeq THEN
MaxSeq <- CurrentSeq
ENDIF
CurrentSeq <- 1
ENDIF
NEXT i

// Final check for sequence reaching end of array
IF CurrentSeq > MaxSeq THEN
MaxSeq <- CurrentSeq
ENDIF

// 4. Output results
OUTPUT "Average temperature: ", Average
OUTPUT "Days below average: ", BelowCount
OUTPUT "Days above average: ", AboveCount
OUTPUT "Longest increasing sequence: ", MaxSeq
ENDPROCEDURE

Award marks as follows:
- 1 Mark: Correct procedure header taking `TempData` as array parameter with type `ARRAY[1:50] OF REAL`.
- 1 Mark: Proper declarations of local variables with correct data types (`REAL`, `INTEGER`).
- 1 Mark: Correct iteration from 1 to 50 to sum the temperatures.
- 1 Mark: Correct calculation of average temperature (`Sum / 50.0`).
- 2 Marks: Loop to count strictly below and strictly above average temperatures (1 mark for loop, 1 mark for correct selection checking condition rules).
- 1 Mark: Initializing sequence counters `CurrentSeq` and `MaxSeq` to 1.
- 2 Marks: Iterating from index 2 to 50, correctly comparing the element at current index with the previous index and incrementing `CurrentSeq`.
- 1 Mark: Handling sequence break by comparing `CurrentSeq` with `MaxSeq`, updating `MaxSeq` if necessary, and resetting `CurrentSeq` to 1.
- 1 Mark: Correct post-loop check to handle sequence stretching to the last element.
- 1 Mark: Proper output statements with explanatory labels for all 4 computed values.

FUNCTION SummarizeTransactions(TargetUser : STRING) RETURNS REAL
DECLARE Line : STRING
DECLARE CurrentUser : STRING
DECLARE AmountStr : STRING
DECLARE AmountVal : REAL
DECLARE TotalAmount : REAL
DECLARE MaxAmount : REAL
DECLARE MaxTime : STRING
DECLARE Found : BOOLEAN

TotalAmount <- 0.0
MaxAmount <- -1.0
MaxTime <- ""
Found <- FALSE

OPENFILE "LogFile.txt" FOR READ
WHILE NOT EOF("LogFile.txt")
READFILE "LogFile.txt", Line
IF LENGTH(Line) >= 19 THEN
CurrentUser <- MID(Line, 12, 6)
IF CurrentUser = TargetUser THEN
Found <- TRUE
AmountStr <- MID(Line, 19, LENGTH(Line) - 18)
AmountVal <- STR_TO_NUM(AmountStr)
TotalAmount <- TotalAmount + AmountVal

IF AmountVal > MaxAmount THEN
MaxAmount <- AmountVal
MaxTime <- MID(Line, 1, 10)
ENDIF
ENDIF
ENDIF
ENDWHILE
CLOSEFILE "LogFile.txt"

IF Found = TRUE THEN
OUTPUT "Max Transaction: ", MaxAmount, " at ", MaxTime
ELSE
OUTPUT "No transactions found"
ENDIF

RETURN TotalAmount
ENDFUNCTION

Award marks as follows:
- 1 Mark: Correct function header with parameter definition and `RETURNS REAL`.
- 1 Mark: Correct use of `OPENFILE` and `CLOSEFILE` with appropriate file mode.
- 1 Mark: Appropriate variable initialization (total to 0, flag and max values initialized cleanly).
- 1 Mark: Correct loop syntax using `WHILE NOT EOF("LogFile.txt")`.
- 1 Mark: Extracting the `CurrentUser` using `MID(Line, 12, 6)`.
- 1 Mark: Comparing the extracted user ID to the input parameter `TargetUser`.
- 2 Marks: Extracting the amount substring using dynamic length `LENGTH(Line) - 18` starting at 19, and converting it to numeric form with `STR_TO_NUM` (1 mark for index, 1 mark for conversion).
- 1 Mark: Accumulating transaction values to a running sum.
- 1 Mark: Correct search algorithm implementation to find maximum transaction amount and record matching timestamp from index 1 to 10.
- 1 Mark: Handling condition where no records were matched with logical flag and outputting informative diagnostics.
- 1 Mark: Correct `RETURN` statement returning the total sum.

FUNCTION CountEnemiesInRange(Grid : ARRAY[1:8, 1:8] OF CHAR) RETURNS INTEGER
DECLARE PlayerRow, PlayerCol : INTEGER
DECLARE Row, Col : INTEGER
DECLARE EnemyCount : INTEGER
DECLARE r, c : INTEGER

PlayerRow <- 0
PlayerCol <- 0
EnemyCount <- 0

// 1. Locate player 'P'
FOR Row <- 1 TO 8
FOR Col <- 1 TO 8
IF Grid[Row, Col] = 'P' THEN
PlayerRow <- Row
PlayerCol <- Col
ENDIF
NEXT Col
NEXT Row

// If player is not found on the board
IF PlayerRow = 0 OR PlayerCol = 0 THEN
RETURN 0
ENDIF

// 2. Check 3x3 grid around player
FOR r <- PlayerRow - 1 TO PlayerRow + 1
FOR c <- PlayerCol - 1 TO PlayerCol + 1
// Check boundary conditions
IF r >= 1 AND r <= 8 AND c >= 1 AND c <= 8 THEN
// Ensure we do not count the player's own position
IF NOT (r = PlayerRow AND c = PlayerCol) THEN
IF Grid[r, c] = 'E' THEN
EnemyCount <- EnemyCount + 1
ENDIF
ENDIF
ENDIF
NEXT c
NEXT r

RETURN EnemyCount
ENDFUNCTION

Award marks as follows:
- 1 Mark: Correct function header taking 2D array parameter and returns integer.
- 2 Marks: Correct nested loops (1 to 8) to traverse the array to search for player `'P'`.
- 1 Mark: Identifying player `'P'` and capturing both current row and column coordinates.
- 1 Mark: Correctly initializing variable `EnemyCount` to 0.
- 2 Marks: Loop configuration or sequence of individual checks scanning rows from `PlayerRow - 1` to `PlayerRow + 1` and columns from `PlayerCol - 1` to `PlayerCol + 1`.
- 2 Marks: Proper boundary assertions checking that row coordinate `r` and column coordinate `c` are between 1 and 8 inclusive before accessing array.
- 1 Mark: Correct check to make sure the target cell coordinates do not match the player's own position `(PlayerRow, PlayerCol)`.
- 1 Mark: Incrementing `EnemyCount` when finding character `'E'`.
- 1 Mark: Returning the final count value correctly.

Step 1: Convert the Mantissa.
The mantissa is 1011010000. Since the MSB is 1, this represents a negative number in normalized form.
The binary point is after the first bit: 1.011010000.
Using two's complement conversion, the value is calculated as:
-1 + 0*(0.5) + 1*(0.25) + 1*(0.125) + 0*(0.0625) + 1*(0.03125) = -1 + 0.25 + 0.125 + 0.03125 = -0.59375.

Step 2: Convert the Exponent.
The exponent is 000110. Since the MSB is 0, this is a positive integer.
000110 in denary is 4 + 2 = 6.

Step 3: Calculate the Final Value.
Multiply the mantissa by 2 raised to the power of the exponent:
-0.59375 * 2^6 = -0.59375 * 64 = -38.

1 mark: Identifies the mantissa as a negative number starting with 1.0
1 mark: Shows correct conversion of mantissa fractional place values to denary (-0.59375 or -19/32)
1 mark: Correct mantissa denary value (-0.59375)
1 mark: Identifies exponent as positive 6
1 mark: Correct exponent denary value (6)
1 mark: Shows final step multiplying mantissa by 2^6
1 mark: Correct final denary result (-38)

Step 1: Set up the K-map with grey-code ordering (00, 01, 11, 10) for rows CD and columns AB.
The minterms from the expression are:
- not A and not B and C: covers cells 0010 (2) and 0011 (3)
- not A and B and C: covers cells 0110 (6) and 0111 (7)
- A and B and not D: covers cells 1100 (12) and 1110 (14)
- A and not B and not D: covers cells 1000 (8) and 1010 (10)

Placing 1s in these 8 cells in the K-map:
CD\AB | 00 | 01 | 11 | 10
00 | 0 | 0 | 1 | 1
01 | 0 | 0 | 0 | 0
11 | 1 | 1 | 0 | 0
10 | 1 | 1 | 1 | 1

Step 2: Form groups.
- Group 1: A 2x2 group of four 1s at the intersection of rows 11, 10 and columns 00, 01. This group represents (not A and C).
- Group 2: A 2x2 group of four 1s formed by wrapping the corners/edges, specifically rows 00, 10 and columns 11, 10. This group represents (A and not D).
(Note: The row 10 has a group of 4, but it is entirely redundant as its cells are fully covered by Group 1 and Group 2.)

Step 3: Simplified expression:
F = (not A and C) or (A and not D)

Part 1 (K-map):
1 mark: K-map template drawn with correct Grey code labels (00, 01, 11, 10) for rows/columns.
2 marks: All eight '1's placed in correct cells (lose 1 mark for any incorrect placement or extra/missing 1).

Part 2 (Grouping):
1 mark: Identifies first group of four cells in top-left/middle-left (representing not A and C).
1 mark: Identifies second group of four cells in top-right/bottom-right (representing A and not D) and states that the row of four is redundant.

Part 3 (Simplified Expression):
2 marks: Correct final expression (F = (not A and C) or (A and not D)). Allow equivalent notation like A'C + AD'.

Step 1: Calculate the output of hidden node H1 (a1).
Weighted sum z1 = (x1 * w11) + (x2 * w21) + b1
z1 = (0.8 * 0.5) + (0.5 * -0.2) + (-0.1)
z1 = 0.4 - 0.1 - 0.1 = 0.2
Since z1 > 0, the output a1 = ReLU(z1) = 0.2.

Step 2: Calculate the output of hidden node H2 (a2).
Weighted sum z2 = (x1 * w12) + (x2 * w22) + b2
z2 = (0.8 * -0.4) + (0.5 * 0.6) + 0.2
z2 = -0.32 + 0.3 + 0.2 = 0.18
Since z2 > 0, the output a2 = ReLU(z2) = 0.18.

Step 3: Calculate the output of node Y (aY).
Weighted sum zY = (a1 * v1) + (a2 * v2) + bY
zY = (0.2 * 0.8) + (0.18 * 1.5) + (-0.3)
zY = 0.16 + 0.27 - 0.3
zY = 0.43 - 0.3 = 0.13
Since zY > 0, the output aY = ReLU(zY) = 0.13.

1 mark: Correct weighted sum calculation for H1 (0.2).
1 mark: Correct output for H1 after applying ReLU (0.2).
1 mark: Correct weighted sum calculation for H2 (0.18).
1 mark: Correct output for H2 after applying ReLU (0.18).
1 mark: Correct formula for output node Y (using outputs from H1 and H2 as inputs).
1 mark: Correct weighted sum for Y (0.13).
1 mark: Correct final output value of Y after applying ReLU (0.13).

Part 1: Convert to RPN
- Bracket 1: (X - Y) becomes: X Y -
- Bracket 2: (Z + W) becomes: Z W +
- Multiply the two bracket results: X Y - Z W + *
- Division: U / V becomes: U V /
- Subtract the division from the product: X Y - Z W + * U V / -

Part 2: Stack Evaluation of RPN Expression
- Push 12, Push 4.
- Operation '-': Pop 4, Pop 12. Evaluate 12 - 4 = 8. Push 8. Stack: [8]
- Push 3, Push 2.
- Operation '+': Pop 2, Pop 3. Evaluate 3 + 2 = 5. Push 5. Stack: [8, 5]
- Operation '*': Pop 5, Pop 8. Evaluate 8 * 5 = 40. Push 40. Stack: [40]
- Push 15, Push 5.
- Operation '/': Pop 5, Pop 15. Evaluate 15 / 5 = 3. Push 3. Stack: [40, 3]
- Operation '-': Pop 3, Pop 40. Evaluate 40 - 3 = 37. Push 37. Stack: [37]

Part 1:
1 mark: Correct RPN for brackets: X Y - and Z W +
1 mark: Correct division part: U V /
1 mark: Correct final combined expression: X Y - Z W + * U V / -

Part 2:
1 mark: Shows stack contains [8] after the first '-' operation.
1 mark: Shows stack contains [40] after the '*' operation.
1 mark: Shows stack contains [40, 3] after the '/' operation.
1 mark: Correct final answer of 37 after the final '-' operation.

Part 1: Alice's public value A
Formula: A = g^a mod p
A = 5^4 mod 23
5^4 = 625
625 / 23 = 27.1739...
27 * 23 = 621
625 - 621 = 4
A = 4

Part 2: Bob's public value B
Formula: B = g^b mod p
B = 5^3 mod 23
5^3 = 125
125 / 23 = 5.4347...
5 * 23 = 115
125 - 115 = 10
B = 10

Part 3: Shared secret key K from Bob's perspective
Formula: K = A^b mod p
K = 4^3 mod 23
4^3 = 64
64 / 23 = 2.7826...
2 * 23 = 46
64 - 46 = 18
K = 18

(Verification from Alice's side: K = B^a mod p = 10^4 mod 23 = 10000 mod 23 = 18.)

Part 1:
1 mark: Correct substitution into the formula: 5^4 mod 23.
1 mark: Correct final calculation of A = 4.

Part 2:
1 mark: Correct substitution into the formula: 5^3 mod 23.
1 mark: Correct final calculation of B = 10.

Part 3:
1 mark: Correct formula from Bob's perspective: A^b mod 23.
1 mark: Correct substitution: 4^3 mod 23.
1 mark: Correct final calculation of K = 18.

Part 1: Largest positive value
- To maximize a positive normalized floating-point number, we use the largest positive normalized mantissa and the largest exponent.
- Max mantissa (6 bits): 0.11111
- Denary value of mantissa: 0.5 + 0.25 + 0.125 + 0.0625 + 0.03125 = 0.96875 (or 31/32)
- Max exponent (4 bits): 0111 (since MSB is sign bit 0, max value is 7)
- Denary value of exponent: 7
- Final value: 0.96875 * 2^7 = 0.96875 * 128 = 124 (or 31/32 * 128 = 124)

Part 2: Smallest positive non-zero value
- To minimize a positive normalized floating-point number, we use the smallest positive normalized mantissa and the most negative exponent.
- Smallest normalized positive mantissa (6 bits): 0.10000
- Denary value of mantissa: 0.5 (or 1/2)
- Most negative exponent (4 bits): 1000 (representing -8 in two's complement)
- Denary value of exponent: -8
- Final value: 0.5 * 2^-8 = 1/2 * 1/256 = 1/512 = 0.001953125

Part 3: Underflow
- Floating-point underflow (or underflow).

Part 1:
1 mark: Correct binary mantissa (0.11111) and exponent (0111).
1 mark: Correct denary translation of mantissa (0.96875 or 31/32) and exponent (7).
1 mark: Correct final calculation resulting in 124.

Part 2:
1 mark: Correct binary mantissa (0.10000) and exponent (1000).
1 mark: Correct denary translation of mantissa (0.5 or 1/2) and exponent (-8).
1 mark: Correct final calculation resulting in 1/512 (or 0.001953125).

Part 3:
1 mark: Correctly identifies the term as '(floating-point) underflow'.

Just-In-Time (JIT) compilation is a method used by virtual machines to execute intermediate code efficiently. Instead of interpreting each instruction every time it is encountered, the JIT compiler translates blocks of bytecode into native machine code on the fly, immediately before execution. The VM typically monitors the running program to detect 'hot spots' (such as loops or frequently called methods) and compiles only those parts to optimize performance.

Advantages of JIT compilation compared to pure interpretation:
1. Execution speed: Once code is compiled to native machine code, it runs directly on the hardware's CPU, making it significantly faster than line-by-line interpretation.
2. Dynamic Optimization: The compiler can use actual runtime profile information (e.g., branch statistics, types of objects passing through) to optimize the generated machine code dynamically.

Disadvantages of JIT compilation:
1. Runtime Overhead: Compilation takes place while the program is running, which can cause an initial startup delay or temporary pauses during execution.
2. Memory Footprint: The compiled native code must be cached in the system's random-access memory (RAM), leading to higher memory consumption than pure interpretation.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- JIT compiles intermediate bytecode into native machine code at runtime [1 mark]
- It compiles code 'on the fly' just before execution / focuses on frequently executed 'hot spots' [1 mark]
- Advantage: Much faster execution speed than pure interpretation once compiled [1 mark]
- Advantage: Allows dynamic optimization using real-time profiling data [1 mark]
- Disadvantage: Causes startup delay / runtime compilation overhead [1 mark]
- Disadvantage: Increases memory usage because compiled native code must be cached in RAM [1 mark]

When establishing a secure HTTPS connection, the validation process is as follows:
1. The web browser requests a secure connection, and the server (sender) responds by sending its digital certificate.
2. The digital certificate contains the server's public key, identify details of the owner, and a digital signature.
3. The digital signature is created by the Certificate Authority (CA) by hashing the certificate details and encrypting this hash with the CA's private key.
4. The browser has a built-in list of trusted CAs and their corresponding public keys. It uses the correct CA's public key to decrypt the digital signature, which reveals the original hash calculated by the CA.
5. The browser then independently hashes the certificate details itself using the same hashing algorithm.
6. Finally, the browser compares its calculated hash with the decrypted hash. If they are identical, it proves that the certificate was indeed issued by the trusted CA and has not been altered in transit, thus validating the server's public key.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- Browser receives the certificate containing the server's public key and the CA's digital signature [1 mark]
- The digital signature is created by encrypting the certificate hash using the CA's private key [1 mark]
- The browser retrieves the CA's public key from its built-in trusted store [1 mark]
- The browser decrypts the digital signature using the CA's public key to reveal the original hash [1 mark]
- The browser independently calculates a new hash of the received certificate's details [1 mark]
- The browser compares both hashes; a match verifies integrity and authenticity [1 mark]

During the training of an Artificial Neural Network (ANN):

1. Loss Function:
- The loss function (or cost function) is a mathematical metric that evaluates the network's performance. It compares the predicted output generated by the network during forward propagation with the actual target (ground truth) output.
- It outputs a single scalar value representing the error. The goal of training is to minimize this error value.

2. Backpropagation:
- Backpropagation (backward propagation of errors) is the algorithm used to calculate the gradients of the loss function with respect to the network's weights.
- Starting at the output layer, it calculates the error gradient and propagates it backward through each hidden layer toward the input layer.
- It utilizes the chain rule of calculus to compute how much each individual weight contributed to the total loss.
- The calculated gradients are then passed to an optimization algorithm (such as Gradient Descent) which updates the weights in the direction that reduces the loss. This process repeats over many training epochs until the error is minimized to an acceptable level.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- Loss function calculates the mathematical error/difference between the predicted and target outputs [1 mark]
- Backpropagation calculates the gradients of the loss function with respect to the weights [1 mark]
- It propagates errors backward from the output layer through the hidden layers [1 mark]
- Uses the chain rule of calculus to determine each weight's contribution to the error [1 mark]
- Gradients are used by an optimizer (e.g., Gradient Descent) to update the weights [1 mark]
- The process is iterative, repeating over multiple epochs to minimize the overall loss [1 mark]

Dynamic routing allows routers to automatically discover network paths and update their routing tables to adapt to changes such as link failures or congestion.

1. Distance-Vector Routing:
- Routers determine the distance (metric, such as hop count) and direction (vector, the next-hop router) to destination networks.
- Routers periodically share their entire routing tables, but only with their directly connected immediate neighbors.
- It is simple to configure but suffers from slow convergence and can lead to routing loops (e.g., count-to-infinity problem).

2. Link-State Routing:
- Routers do not share entire tables; instead, they flood link-state packets (LSPs) containing status information of their immediate interfaces to all routers in the routing domain.
- Every router receives these updates and builds an identical, complete database of the network's topology (the link-state database).
- Each router independently runs the Shortest Path First (SPF) algorithm, such as Dijkstra's algorithm, to calculate the optimal path to each destination.
- It converges much faster than Distance-Vector but requires more processing power and memory on routers.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- Dynamic routing tables are populated using automated protocols that share network topology status [1 mark]
- Distance-Vector: Routers periodically send their complete routing tables [1 mark]
- Distance-Vector: Information is shared only with directly connected neighbors [1 mark]
- Link-State: Routers flood status of their local links to all other routers in the network [1 mark]
- Link-State: Every router constructs a complete and identical map of the entire network topology [1 mark]
- Link-State: Routers run Dijkstra's algorithm (or SPF) to calculate optimal paths [1 mark]

Syntax analysis (parsing) is the second stage of compilation:

1. Input:
- The syntax analyzer receives a linear stream of tokens generated during lexical analysis.

2. Context-Free Grammar (CFG) and BNF:
- A context-free grammar, often expressed using Backus-Naur Form (BNF), defines the complete set of structural rules (syntax) of the programming language (e.g., how statements, loops, and expressions must be structured).

3. Parse Tree Construction:
- The syntax analyzer attempts to parse the token stream by grouping tokens into grammatical phrases. It builds a hierarchical structure called a parse tree.
- In a parse tree, leaf nodes represent terminal tokens (such as identifiers or operators) and internal nodes represent non-terminal grammatical rules (such as expressions or statements).

4. Verification and Error Detection:
- If the sequence of tokens can be completely mapped to the grammar rules, a complete parse tree is successfully built, indicating the source code is syntactically correct.
- If a token does not match any allowed grammatical rules at a given position, the parse tree construction fails. The compiler detects this mismatch as a syntax error, records the location (line number/token), and outputs an appropriate error message to assist the programmer.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- Parser takes the output token stream from the lexical analysis phase [1 mark]
- Context-free grammars (such as BNF) define the structural syntax rules of the programming language [1 mark]
- The syntax analyzer attempts to organize tokens into a hierarchical parse tree [1 mark]
- Success in constructing a complete parse tree verifies that the code syntax is correct [1 mark]
- If tokens violate the grammatical rules, a parse tree cannot be fully constructed [1 mark]
- The parser identifies the point of failure, stops/recovers, and reports a syntax error with position details [1 mark]

1. Purpose of Normalization:
- Normalization standardizes floating-point numbers so they always begin with the format '0.1...' for positive numbers (in sign-and-magnitude or two's complement where the first two bits are '01') and '1.0...' for negative numbers (where the first two bits are '10' in two's complement).
- Unique Representation: It ensures that each real number has one, and only one, unique representation in memory. This simplifies operations like comparisons.
- Maximum Precision: By shifting the mantissa to eliminate leading redundant zeros (or ones) and adjusting the exponent accordingly, it ensures that the maximum number of significant bits is preserved within the allocated mantissa size.

2. Bit Allocation Trade-Offs (with a fixed total word size):
- There is a zero-sum relationship because the total number of bits is fixed.
- More bits to Mantissa, fewer to Exponent: This increases the precision of the represented numbers because more significant figures can be stored, reducing rounding errors. However, it severely limits the range of numbers that can be represented because the maximum and minimum exponent values are smaller.
- More bits to Exponent, fewer to Mantissa: This increases the range of numbers that can be represented, allowing extremely large or extremely small numbers to be stored. However, it decreases the precision because fewer bits are available to represent the fractional portion of the number, leading to greater rounding errors.

Award 1 mark per valid point up to a maximum of 5.5 marks:
- Normalization formats the mantissa to begin with distinct bits ('01' for positive, '10' for negative in two's complement) [1 mark]
- It ensures a unique binary representation for each numerical value, preventing duplicate representations [1 mark]
- It maximizes precision by removing leading redundant bits, utilizing all available mantissa bits [1 mark]
- The trade-offs apply under a fixed overall word size constraint [1 mark]
- Increasing mantissa bits (at the expense of exponent bits) improves precision but reduces the range of values [1 mark]
- Increasing exponent bits (at the expense of mantissa bits) broadens the range of values but reduces precision [1 mark]

### Python Implementation

```python
class Job:
def __init__(self, job_id, priority, duration):
self.__job_id = job_id
self.__priority = priority
self.__duration = duration

def get_job_id(self):
return self.__job_id

def get_priority(self):
return self.__priority

def get_duration(self):
return self.__duration

class PrintQueue:
def __init__(self):
self.__queue = [None] * 10
self.__head = 0
self.__tail = -1
self.__num_items = 0

def enqueue(self, new_job):
if self.__num_items == 10:
return False

self.__tail = (self.__tail + 1) % 10
self.__queue[self.__tail] = new_job
self.__num_items += 1
return True

def dequeue(self):
if self.__num_items == 0:
return None

removed_job = self.__queue[self.__head]
self.__queue[self.__head] = None
self.__head = (self.__head + 1) % 10
self.__num_items -= 1
return removed_job

def print_state(self):
print(f\"Head: {self.__head}, Tail: {self.__tail}, NumItems: {self.__num_items}\")

# Main Program
if __name__ == \"__main__\":
my_queue = PrintQueue()

j1 = Job(\"J101\", 3, 120)
j2 = Job(\"J102\", 5, 45)
j3 = Job(\"J103\", 2, 300)

print(\"Enqueuing J101:\", my_queue.enqueue(j1))
print(\"Enqueuing J102:\", my_queue.enqueue(j2))
print(\"Enqueuing J103:\", my_queue.enqueue(j3))

my_queue.print_state()

dequeued = my_queue.dequeue()
if dequeued is not None:
print(f\"Dequeued Job: {dequeued.get_job_id()} | Priority: {dequeued.get_priority()} | Duration: {dequeued.get_duration()}s\")

my_queue.print_state()
```

### Marking Scheme (25 Marks Total)

**1. Class `Job` Definition [6 Marks]**
- Declaring and encapsulating private variables: `JobID`, `Priority`, `Duration`. (2 marks)
- Constructor correctly accepting parameters and initialising attributes. (2 marks)
- Implementing three correct getter methods. (2 marks)

**2. Class `PrintQueue` Constructor & State [4 Marks]**
- Setting array `Queue` of size 10 to standard default/None/null elements. (1 mark)
- Initialising `Head` to 0, `Tail` to -1, and `NumItems` to 0. (3 marks)

**3. `Enqueue` Method logic [6 Marks]**
- Check for queue full check (`NumItems == 10`) returning False. (2 marks)
- Correctly updating pointer with wrap-around calculation: `(Tail + 1) % 10`. (2 marks)
- Inserting job, incrementing `NumItems`, and returning `True`. (2 marks)

**4. `Dequeue` Method logic [5 Marks]**
- Checking if empty (`NumItems == 0`) returning None/null. (1 mark)
- Storing reference to job at `Head`. (1 mark)
- Updating `Head` pointer with wrap-around logic: `(Head + 1) % 10`. (2 marks)
- Decrementing `NumItems` and returning the retrieved job object. (1 mark)

**5. Main Program & Testing [4 Marks]**
- Correctly instantiating objects and testing operations sequentially. (2 marks)
- Outputting values indicating expected state (`Head` moves to 1, `Tail` at 2, `NumItems` becomes 2 after dequeue). (2 marks)

### Python Implementation

```python
class TreeNode:
def __init__(self, node_data):
self.Data = node_data
self.LeftPointer = -1
self.RightPointer = -1

Tree = [TreeNode(\"\") for _ in range(15)]
RootPointer = -1
FreePointer = 0

def InsertNode(NewData):
global RootPointer, FreePointer, Tree

if FreePointer >= 15:
print(\"Tree is full\")
return

# Setup the new node at the free slot
Tree[FreePointer] = TreeNode(NewData)

if RootPointer == -1:
RootPointer = FreePointer
FreePointer += 1
else:
Current = RootPointer
Inserted = False
while not Inserted:
if NewData < Tree[Current].Data:
if Tree[Current].LeftPointer == -1:
Tree[Current].LeftPointer = FreePointer
Inserted = True
else:
Current = Tree[Current].LeftPointer
else:
if Tree[Current].RightPointer == -1:
Tree[Current].RightPointer = FreePointer
Inserted = True
else:
Current = Tree[Current].RightPointer
FreePointer += 1

def InOrder(Pointer):
global Tree
if Pointer != -1:
InOrder(Tree[Pointer].LeftPointer)
print(Tree[Pointer].Data)
InOrder(Tree[Pointer].RightPointer)

# Main Execution
if __name__ == \"__main__\":
InsertNode(\"Mango\")
InsertNode(\"Apple\")
InsertNode(\"Peach\")
InsertNode(\"Banana\")
InsertNode(\"Cherry\")

print(\"In-Order Traversal Contents:\")
InOrder(RootPointer)
```

### Marking Scheme (25 Marks Total)

**1. Class `TreeNode` Implementation [4 Marks]**
- Attributes declared correctly as specified (Data, LeftPointer, RightPointer). (2 marks)
- Constructor initialises attributes with default values of pointers to -1. (2 marks)

**2. Setup Array and Pointers [4 Marks]**
- Global declaration of `Tree` with size 15. (2 marks)
- Setting `RootPointer` to -1 and `FreePointer` to 0. (2 marks)

**3. `InsertNode` Procedure Logic [10 Marks]**
- Checking array limits to ensure no out-of-bounds error. (1 mark)
- Assigning the new element at the current free space correctly. (2 marks)
- Checking if tree is empty (`RootPointer == -1`) and setting root. (2 marks)
- Iterative loop traversal logic using left/right pointer directions based on data values. (3 marks)
- Storing the reference index and updating `FreePointer` index by increment. (2 marks)

**4. Recursive `InOrder` Traversal [4 Marks]**
- Base condition checking for null pointers (`Pointer != -1`). (1 mark)
- Correct recursive call order (Left branch first, action on node, Right branch next). (3 marks)

**5. Main Execution and Testing [3 Marks]**
- Calling insert methods in the exact sequence requested. (1 mark)
- Outputs the expected alphabetical ordered strings: Apple, Banana, Cherry, Mango, Peach. (2 marks)

### Python Implementation

```python
import os

class StudentRecord:
def __init__(self, name, score):
self.__name = name
self.__score = score

def get_name(self):
return self.__name

def get_score(self):
return self.__score

RecordArray = [None] * 30

def ReadResults(filename):
global RecordArray
count = 0
try:
with open(filename, 'r') as file:
for line in file:
if count >= 30:
break
parts = line.strip().split(',')
if len(parts) == 2:
name = parts[0]
score = int(parts[1])
RecordArray[count] = StudentRecord(name, score)
count += 1
return count
except IOError:
print(\"Error: File could not be opened.\")
return 0

def InsertionSort(record_count):
global RecordArray
for i in range(1, record_count):
key_item = RecordArray[i]
j = i - 1
# Sorting by descending score value
while j >= 0 and RecordArray[j].get_score() < key_item.get_score():
RecordArray[j + 1] = RecordArray[j]
j -= 1
RecordArray[j + 1] = key_item

def BinarySearch(name_target, low, high):
global RecordArray
if low > high:
return -1
mid = (low + high) // 2
if RecordArray[mid].get_name() == name_target:
return mid
elif RecordArray[mid].get_name() > name_target:
return BinarySearch(name_target, low, mid - 1)
else:
return BinarySearch(name_target, mid + 1, high)

# Main Setup and Execution
if __name__ == \"__main__\":
# Create sample results.txt for test compatibility
with open(\"results.txt\", \"w\") as f:
f.write(\"David,87\
Alice,95\
Charlie,72\
Bob,90\
\")

records_loaded = ReadResults(\"results.txt\")
print(f\"Loaded {records_loaded} records.\")

InsertionSort(records_loaded)
print(\"Sorted Records (Descending Scores):\")
for idx in range(records_loaded):
rec = RecordArray[idx]
print(f\"{rec.get_name()}: {rec.get_score()}\")

# Sort array alphabetically to perform Binary Search on Name
# Note: Binary search requires sorted keys
# In exams, ensure arrays are correctly prepared before binary searching
# Let's simple-sort the names to verify binary search logic
RecordArray[:records_loaded] = sorted(RecordArray[:records_loaded], key=lambda x: x.get_name())
print(\"\
Sorted alphabetically for Binary Search:\")
for idx in range(records_loaded):
rec = RecordArray[idx]
print(f\"Index {idx}: {rec.get_name()}\")

found_idx = BinarySearch(\"Charlie\", 0, records_loaded - 1)
print(f\"\
Searching for 'Charlie'. Found at index: {found_idx}\")
```

### Marking Scheme (25 Marks Total)

**1. Class implementation [4 Marks]**
- Attributes declared private and initialised in constructor. (2 marks)
- Getters properly declared and returning correct attributes. (2 marks)

**2. File Reader Logic [6 Marks]**
- Attempting to open file with structural try-except constructs. (2 marks)
- Correctly parsing/splitting CSV string types, converting scores to int. (2 marks)
- Safe bounds handling avoiding exceeding index index 30. (1 mark)
- Keeping counter tracking size, and returning active record load size. (1 mark)

**3. Insertion Sort Implementation [6 Marks]**
- Correctly nested outer and inner loop iteration layout. (2 marks)
- Standard shifting element mechanics matching target item swap bounds. (2 marks)
- Directional check inequality ensuring descending sorting behavior (`RecordArray[j].get_score() < key_item.get_score()`). (2 marks)

**4. Recursive Binary Search [6 Marks]**
- Correct calculation of middle index using division base index arithmetic. (1 mark)
- Base terminal check for values not present returning -1 when limits collide. (1 mark)
- Comparison logic checking target key relative to dynamic array values. (2 marks)
- Recursive calls passing appropriate range variations (`mid - 1` and `mid + 1`). (2 marks)

**5. Complete Main testing logic [3 Marks]**
- Calling the operations, executing program print statements, demonstrating sorted result array metrics. (3 marks)