2022 AQA A-Level Computer Science 7517 Practice Paper with Answers

mystery [4, 7, 2, 9, 3] is evaluated as follows:
- 4 is even, so mystery [7, 2, 9, 3] is called.
- 7 is odd, so 7 + mystery [2, 9, 3] is evaluated.
- 2 is even, so mystery [9, 3] is called.
- 9 is odd, so 9 + mystery [3] is evaluated.
- 3 is odd, so 3 + mystery [] is evaluated.
- mystery [] returns 0.

Adding these up: 7 + 9 + 3 + 0 = 19.

- 1 mark: Correctly trace that even numbers (4, 2) are ignored / skipped.
- 1 mark: Show addition of odd numbers (7 + 9 + 3).
- 1 mark: Correct final answer (19).

To convert \((12 - 4) \times (5 + 3) \div 2\) to Reverse Polish notation:
1. Convert the first brackets: (12 - 4) becomes 12 4 -
2. Convert the second brackets: (5 + 3) becomes 5 3 +
3. Multiply these two terms: 12 4 - 5 3 + *
4. Divide by 2: 12 4 - 5 3 + * 2 /

- 1 mark: Correct conversion of brackets to '12 4 -' or '5 3 +'.
- 1 mark: Correct ordering of multiplication '12 4 - 5 3 + *'.
- 1 mark: Correct final expression '12 4 - 5 3 + * 2 /'.

1. Convert the mantissa (two's complement): 10110000 binary represents a value of -1 * 2^0 + 0 * 2^-1 + 1 * 2^-2 + 1 * 2^-3 = -1 + 0.25 + 0.125 = -0.625.
2. Convert the exponent (two's complement): 0011 binary represents +3 in denary.
3. Multiply the mantissa by 2 raised to the exponent: -0.625 * 2^3 = -0.625 * 8 = -5.

- 1 mark: Correctly converting the mantissa to -0.625 (or -5/8).
- 1 mark: Correctly converting the exponent to 3.
- 1 mark: Calculating the correct denary result of -5.

1. Expand brackets: A . (B + C) = A . B + A . C and B . (B + C) = B . B + B . C = B + B . C.
2. Simplify B + B . C: using absorption law, B + B . C = B.
3. Substitute back: Q = A . B + A . B + A . C + B.
4. Simplify identical terms: A . B + A . B = A . B. Thus Q = A . B + A . C + B.
5. Combine terms with B: Q = B + A . B + A . C. Since B + A . B = B, we get Q = B + A . C.

- 1 mark: Expand terms to obtain A . B + A . C + B . B + B . C.
- 1 mark: Apply the absorption law or factorisation to simplify B . B + B . C to B.
- 1 mark: Produce the correct final simplified expression B + A . C.

- push 'K': Stack = [K], top = 0
- push 'R': Stack = [K, R], top = 1
- pop: returns R, Stack = [K], top = 0
- push 'M': Stack = [K, M], top = 1
- push 'P': Stack = [K, M, P], top = 2
- pop: returns P, Stack = [K, M], top = 1
- push 'W': Stack = [K, M, W], top = 2

- 1 mark: Showing stack contents after first pop are [K] and top is 0.
- 1 mark: Showing stack contents after second pop are [K, M] and top is 1.
- 1 mark: Correct final stack [K, M, W] (bottom to top) and top pointer index 2.

The BST structure is:
- Root: 50
- Left subtree: 30 (left child 20, right child 40)
- Right subtree: 70 (left child 60, right child 80)

Post-order traversal visits: Left, Right, Root.
- Left child of 30 is 20.
- Right child of 30 is 40.
- Node 30 itself.
- Left child of 70 is 60.
- Right child of 70 is 80.
- Node 70 itself.
- Root node 50 itself.
Order: 20, 40, 30, 60, 80, 70, 50.

- 1 mark: Correctly sketching or representing the BST structure.
- 1 mark: Correctly traversing the left subtree as 20, 40, 30.
- 1 mark: Correctly listing the complete traversal: 20, 40, 30, 60, 80, 70, 50.

The regular expression specifies a string starting with 'a', followed by zero or more repetitions of 'b' or 'c' in any order, and ending with 'd'.
- 'ad': accepted (0 occurrences of b/c).
- 'abbcd': accepted ('b', 'b', 'c').
- 'abcad': rejected (contains 'a' in the middle).
- 'abcd': accepted ('b', 'c').
- 'abd': accepted ('b').

- 1 mark: Correctly identifying 'ad' and 'abd' as accepted.
- 1 mark: Correctly identifying 'abbcd' and 'abcd' as accepted.
- 1 mark: Correctly identifying 'abcad' as rejected.

- routine(14, 4) -> 14 is not < 4, calls routine(10, 4) + 1
- routine(10, 4) -> 10 is not < 4, calls routine(6, 4) + 1
- routine(6, 4) -> 6 is not < 4, calls routine(2, 4) + 1
- routine(2, 4) -> 2 < 4, returns 2
- Back-substitution:
- routine(6, 4) returns 2 + 1 = 3
- routine(10, 4) returns 3 + 1 = 4
- routine(14, 4) returns 4 + 1 = 5.

- 1 mark: Correctly identifying the recursive calls made: routine(10,4), routine(6,4), and routine(2,4).
- 1 mark: Correctly evaluating the base case routine(2,4) to 2.
- 1 mark: Correctly calculating the final returned value of 5.

The execution of mystery [3, 4, 5, 2] proceeds as follows:
1. mystery [3, 4, 5, 2]: x = 3 (odd), returns 3 + mystery [4, 5, 2]
2. mystery [4, 5, 2]: x = 4 (even), returns mystery [5, 2] - 4
3. mystery [5, 2]: x = 5 (odd), returns 5 + mystery [2]
4. mystery [2]: x = 2 (even), returns mystery [] - 2
5. mystery []: returns 0

Substituting back:
- mystery [2] = 0 - 2 = -2
- mystery [5, 2] = 5 + (-2) = 3
- mystery [4, 5, 2] = 3 - 4 = -1
- mystery [3, 4, 5, 2] = 3 + (-1) = 2

1 mark for correctly evaluating mystery [] = 0 and mystery [2] = -2.
1 mark for correctly evaluating mystery [5, 2] = 3 and mystery [4, 5, 2] = -1.
1.33 marks for the final correct output of 2.

We process the tokens from left to right:
- Push 8, then 3. Stack: [8, 3]
- Operator '-': Pop 3, Pop 8. Calculate 8 - 3 = 5. Push 5. Stack: [5]
- Push 4. Stack: [5, 4]
- Operator '*': Pop 4, Pop 5. Calculate 5 * 4 = 20. Push 20. Stack: [20]
- Push 6, then 2. Stack: [20, 6, 2]
- Operator '/': Pop 2, Pop 6. Calculate 6 / 2 = 3. Push 3. Stack: [20, 3]
- Operator '+': Pop 3, Pop 20. Calculate 20 + 3 = 23. Push 23. Stack: [23]

1 mark for correctly showing the intermediate stack state after first two operations [5] and [20].
1 mark for correctly showing the intermediate stack state after division [20, 3].
1.33 marks for the final correct value of 23.

1. Separate mantissa and exponent:
- Mantissa: 10110000
- Exponent: 0011

2. Calculate the exponent:
- Exponent is 0011 in binary, which is +3 in decimal.

3. Calculate the mantissa:
- Mantissa is 1.0110000 in normalized binary fraction.
- Since the sign bit is 1, it represents a negative number.
- Converting 1.0110000 from two's complement:
Weight of MSB is -1.
Value = -1 * 1 + 0 * 0.5 + 1 * 0.25 + 1 * 0.125 = -1 + 0.375 = -0.625.

4. Calculate final decimal value:
- Value = mantissa * 2^exponent = -0.625 * 2^3 = -0.625 * 8 = -5.

1 mark for correctly identifying the exponent as +3.
1 mark for correctly converting the mantissa to -0.625 (or showing equivalent correct fractional working).
1.33 marks for the final correct decimal value of -5.

A post-order traversal visits left subtree, right subtree, then the root node.
- Left subtree of M is rooted at H:
- Left subtree of H is D (leaf): visits D
- Right subtree of H is rooted at K:
- Left subtree of K is I (leaf): visits I
- Right subtree of K is empty
- Root of K subtree: visits K
- Root of H subtree: visits H
- So left subtree sequence: D, I, K, H
- Right subtree of M is rooted at T:
- Left subtree of T is empty
- Right subtree of T is rooted at W:
- Left subtree of W is U (leaf): visits U
- Right subtree of W is empty
- Root of W subtree: visits W
- Root of T subtree: visits T
- So right subtree sequence: U, W, T
- Finally, root of the tree: visits M
Combined sequence: D, I, K, H, U, W, T, M.

1 mark for correctly traversing the left subtree (D, I, K, H).
1 mark for correctly traversing the right subtree (U, W, T).
1.33 marks for the complete correct sequence ending in M.

Below is a complete implementation in Python:

def calculate_check_digit(num_str):
weights = [7, 6, 5, 4, 3, 2]
total_sum = 0
for i in range(6):
total_sum += int(num_str[i]) * weights[i]
remainder = total_sum % 11
check_val = 11 - remainder
if check_val == 10:
return 'X'
elif check_val == 11:
return '0'
else:
return str(check_val)

while True:
user_input = input('Enter 6-digit code or EXIT: ').strip()
if user_input.upper() == 'EXIT':
break
if len(user_input) != 6 or not user_input.isdigit():
print('Invalid Input')
continue
check_digit = calculate_check_digit(user_input)
print('Output:', user_input + check_digit)

Testing execution traces:
1. Input: '410000' -> Sum = (4*7)+(1*6)+0 = 34. 34 % 11 = 1. 11 - 1 = 10. Check digit = 'X'. Output: 410000X.
2. Input: '482015' -> Sum = (4*7)+(8*6)+(2*5)+(0*4)+(1*3)+(5*2) = 28+48+10+0+3+10 = 99. 99 % 11 = 0. 11 - 0 = 11. Check digit = '0'. Output: 4820150.

Total Marks: 6.5
- 1.5 Marks: User input loop terminates correctly on 'EXIT' (case-insensitive) and validates that input is exactly a 6-digit numeric string.
- 1.5 Marks: Correct implementation of the weighted sum multiplication algorithm using weights [7, 6, 5, 4, 3, 2].
- 2.0 Marks: Modulo-11 logic correctly handles remainder subtraction and maps 10 to 'X' and 11 to '0' as required.
- 1.5 Marks: Screenshot evidence showing the program successfully receiving '410000' and '482015' as inputs and outputting '410000X' and '4820150' respectively.

Below is a complete implementation in Python:

queue = [None] * 5
front = 0
rear = 0
size = 0

while True:
cmd = input('Enter command (ENQUEUE / DEQUEUE / EXIT): ').strip().split()
if not cmd:
continue
op = cmd[0].upper()
if op == 'EXIT':
break
elif op == 'ENQUEUE':
if size == 5:
print('Queue Full')
else:
val = cmd[1]
queue[rear] = val
rear = (rear + 1) % 5
size += 1
elif op == 'DEQUEUE':
if size == 0:
print('Queue Empty')
else:
val = queue[front]
queue[front] = None
front = (front + 1) % 5
size -= 1
print('Dequeued:', val)
print(f'Queue: {queue} | Front Pointer: {front} | Rear Pointer: {rear} | Size: {size}')

Expected console state changes during test execution sequence:
1. ENQUEUE A -> Queue: ['A', None, None, None, None] | Front: 0 | Rear: 1 | Size: 1
2. ENQUEUE B -> Queue: ['A', 'B', None, None, None] | Front: 0 | Rear: 2 | Size: 2
3. ENQUEUE C -> Queue: ['A', 'B', 'C', None, None] | Front: 0 | Rear: 3 | Size: 3
4. DEQUEUE -> Dequeued: A. Queue: [None, 'B', 'C', None, None] | Front: 1 | Rear: 3 | Size: 2
5. ENQUEUE D -> Queue: [None, 'B', 'C', 'D', None] | Front: 1 | Rear: 4 | Size: 3

Total Marks: 6.5
- 1.5 Marks: Circular Queue initialization of the array structure (size 5) and front, rear, and size management tracking.
- 2.0 Marks: Correct circular pointer updates using modulo operations (`(index + 1) % 5`) for both enqueueing and dequeueing.
- 1.5 Marks: Robust error handling displaying 'Queue Full' when size reaches 5 and 'Queue Empty' when size is 0.
- 1.5 Marks: Screenshot evidence of the designated command sequence (Enqueue A, B, C, Dequeue, Enqueue D) confirming matching circular pointers and array outputs.

1. Identifies 'Move' as the method overriding the parent method. (0.5 marks)
2. Explains that the keyword 'super' (or superclass reference) is used to call the base class constructor. (1.0 mark)
3. States that this passes the arguments RobotName, StartX, and StartY to initialize Name, XPosition, YPosition, and BatteryLevel attributes defined in Robot before the subclass-specific attribute ShieldPower is set. (1.0 mark)

Max 2.5 marks:
- 0.5 marks: Correctly naming the method Move.
- 1.0 mark: Explains that super.Create (or calling the parent constructor) is used to invoke the parent class constructor.
- 1.0 mark: Explains that this initializes the inherited attributes (Name, XPosition, YPosition, BatteryLevel) defined in the Robot superclass.

1. Mentions that the attributes (Name, XPosition, YPosition, BatteryLevel) are marked with the private access modifier, restricting external access. (1.0 mark)
2. Explains that access to these values is controlled through public methods. (0.5 marks)
3. Explains that GetBattery is a public getter (accessor) method that allows other classes to read the value of BatteryLevel without being able to modify it directly, thereby maintaining data integrity. (1.0 mark)

Max 2.5 marks:
- 1.0 mark: For identifying that attributes are declared as private to hide the inner state / prevent direct access from outside the class.
- 0.5 marks: For stating that public methods are used as interfaces to access or modify private state.
- 1.0 mark: For identifying GetBattery as a getter/accessor method providing read-only access to BatteryLevel and protecting it from unauthorized modification.

1. Creation of MyBot: Name is set to "Sentry1", XPosition to 5, YPosition to 10. BatteryLevel is set to 100 in the parent constructor. ShieldPower is set to 20.
2. Execution of MyBot.Move(2, -3):
- This calls the overridden Move(2, -3) in SecurityRobot.
- SecurityRobot.Move first calls super.Move(2, -3).
- super.Move(2, -3) updates: XPosition = 5 + 2 = 7; YPosition = 10 + (-3) = 7; BatteryLevel = 100 - 5 = 95.
- SecurityRobot.Move then updates ShieldPower = 20 - 1 = 19.

Therefore, the final values are:
- XPosition: 7
- YPosition: 7
- BatteryLevel: 95
- ShieldPower: 19

Max 2.5 marks:
- 0.5 marks: Correctly calculating XPosition as 7.
- 0.5 marks: Correctly calculating YPosition as 7.
- 0.5 marks: Correctly calculating BatteryLevel as 95.
- 0.5 marks: Correctly calculating ShieldPower as 19.
- 0.5 marks: Awarded for showing correct working indicating both the superclass and subclass method steps were executed.

1. Selects Aggregation as the correct relationship. (0.5 marks)
2. Explains that aggregation represents an association where the lifetime of the contained objects (Robot) is not dependent on the container (Fleet) (i.e., a 'has-a' relationship with weak ownership). (1.0 mark)
3. Contrasts this with composition, where the lifetime of Robot would be strictly bound to Fleet (if Fleet is destroyed, its robots would also be destroyed), which violates the requirement that robots can exist independently and be transferred. (1.0 mark)

Max 2.5 marks:
- 0.5 marks: Explicitly selecting 'Aggregation' (or equivalent description of aggregation).
- 1.0 mark: Explaining that under aggregation, the lifecycle of the Robot objects is independent of the Fleet object (destroying the Fleet does not destroy the Robots).
- 1.0 mark: Explaining why composition is inappropriate (it would tightly couple lifecycles and prevent transfer or independent existence of robots).

Implementation details:

1. Variable Declaration in Breakthrough class:
```python
self.__Player1Moves = 0
self.__Player2Moves = 0
self.__Player1Captures = 0
self.__Player2Captures = 0
```

2. Updating variables in the MakeMove / PlayGame method:
```python
# Inside the move execution block
if CurrentPlayer == 1:
self.__Player1Moves += 1
if IsCapture:
self.__Player1Captures += 1
elif CurrentPlayer == 2:
self.__Player2Moves += 1
if IsCapture:
self.__Player2Captures += 1
```

3. Displaying statistics at game end:
```python
p1_rate = (self.__Player1Captures / self.__Player1Moves * 100) if self.__Player1Moves > 0 else 0.0
p2_rate = (self.__Player2Captures / self.__Player2Moves * 100) if self.__Player2Moves > 0 else 0.0
print(f\"Player 1: {self.__Player1Moves} moves, {self.__Player1Captures} captures (Capture Rate: {p1_rate:.1f}%)\")
print(f\"Player 2: {self.__Player2Moves} moves, {self.__Player2Captures} captures (Capture Rate: {p2_rate:.1f}%)\")
```

Expected Output Screen:
Player 1: 5 moves, 2 captures (Capture Rate: 40.0%)
Player 2: 4 moves, 1 captures (Capture Rate: 25.0%)

- 2 marks: Correctly declaring and initializing tracking variables for both players.
- 3 marks: Correctly incrementing moves and captures in the appropriate location in code.
- 2 marks: Correctly calculating capture rate with guard against division-by-zero, formatted to 1 decimal place.
- 2.25 marks: Accurate test output matching the requested scenario.

Implementation details:

Modify validation logic:
```python
def IsValidMove(self, StartRow, StartCol, EndRow, EndCol):
# ... existing coordinate range checks ...
RowDiff = EndRow - StartRow
ColDiff = abs(EndCol - StartCol)

# Determine direction of player movement
# (Assuming Player 1 moves down (+1) and Player 2 moves up (-1))
Direction = 1 if self.__CurrentPlayer == 1 else -1

if RowDiff != Direction:
return False

TargetPiece = self.__Board[EndRow][EndCol]

# Rule 1: Straight forward move
if ColDiff == 0:
return TargetPiece == ' '

# Rule 2: Diagonal move
elif ColDiff == 1:
return TargetPiece != ' ' and self.IsOpponentPiece(TargetPiece)

return False
```

Test Cases:
1. Test Case 1 (Diagonal No Capture):
- Start: (3, 3) containing Player 1 piece. End: (4, 4) which is empty.
- Expected output: False (invalid because diagonal move target is empty).
2. Test Case 2 (Straight Capture Attempt):
- Start: (3, 3) containing Player 1 piece. End: (4, 3) containing Player 2 piece.
- Expected output: False (invalid because straight move target is not empty).

- 3 marks: Ensuring straight-forward moves are only valid if target tile is empty.
- 3 marks: Ensuring diagonal moves are only valid if target tile contains an opponent's piece.
- 3.25 marks: Providing two complete test cases with clear inputs, expected boolean outputs, and reasoning.

Implementation details:

1. Initialization in `__init__`:
```python
import copy
self.__HistoryStack = []
```

2. Pushing state before a move:
```python
def MakeMove(self, ...):
# Save current state
BoardCopy = copy.deepcopy(self.__Board)
self.__HistoryStack.append((BoardCopy, self.__CurrentPlayer))
# ... apply move ...
```

3. Handling UNDO command:
```python
if PlayerInput.upper() == 'UNDO':
if len(self.__HistoryStack) == 0:
print(\"No moves to undo!\")
else:
PreviousBoard, PreviousPlayer = self.__HistoryStack.pop()
self.__Board = PreviousBoard
self.__CurrentPlayer = PreviousPlayer
print(\"Undo successful!\")
```

Console output at start of game:
Command: UNDO
No moves to undo!

- 2 marks: Correctly importing `copy` and initializing an empty list/stack for history.
- 3 marks: Performing a deep copy of the board and pushing it alongside player turn information onto the stack before each valid move.
- 3 marks: Correctly popping, restoring the board grid, reverting the active player, and handling the empty stack check.
- 1.25 marks: Correct console output showing the 'No moves to undo!' message when starting game.

Implementation details:

1. Modify Board Setup:
```python
import random
# After setting up starting pieces for both players:
ObstaclesPlaced = 0
while ObstaclesPlaced < 3:
Row = random.randint(3, 4)
Col = random.randint(0, 7)
if self.__Board[Row][Col] == ' ':
self.__Board[Row][Col] = '#'
ObstaclesPlaced += 1
```

2. Modify Validation Logic:
```python
def IsValidMove(self, StartRow, StartCol, EndRow, EndCol):
# ... standard checks ...
if self.__Board[EndRow][EndCol] == '#':
return False
# ... rest of validation ...
```

3. Sample ASCII Board layout:
```
0 P2 P2 P2 P2 P2 P2 P2 P2
1 P2 P2 P2 P2 P2 P2 P2 P2
2 . . . . . . . .
3 . # . . # . . .
4 . . . # . . . .
5 . . . . . . . .
6 P1 P1 P1 P1 P1 P1 P1 P1
7 P1 P1 P1 P1 P1 P1 P1 P1
```

- 3 marks: Correctly placing exactly 3 obstacles in middle rows (3 and 4) randomly and ensuring no player pieces are overwritten.
- 3 marks: Adding validation to ensure moves to a target containing '#' are invalid.
- 3.25 marks: Clear sample ASCII representation of the board demonstrating the 3 obstacles correctly positioned in the middle rows.

1. Convert the absolute denary value \(6.75\) to binary:
\(6.75 = 4 + 2 + 0.5 + 0.25 = 110.11_{2}\).

2. Represent \(-6.75\) in two's complement with sufficient headroom:
Start with positive value: \(0110.1100_{2}\)
Invert the bits: \(1001.0011_{2}\)
Add 1: \(1001.0100_{2}\) (This represents \(-8 + 1 + 0.25 = -6.75\)).

3. Normalize the binary number. A negative normalized floating-point number must start with bits `10`:
Our binary value is \(1001.0100\). To format this with the binary point after the first bit (sign bit), we write it as \(1.0010100\).
Moving the binary point 3 places to the left means we must multiply by \(2^{3}\) to maintain the value: \(1.0010100 \times 2^{3}\).

4. Extract Mantissa and Exponent:
- Mantissa (8 bits): `10010100`
- Exponent (4 bits): \(3\) in binary is `0011`.

5. Combine to form the 12-bit representation: `100101000011`.

- **1 Mark**: Correctly converting positive \(6.75\) to binary (\(110.11\)).
- **2 Marks**: Correctly converting to negative fixed-point two's complement (\(1001.0100\)).
- **1.5 Marks**: Correct normalization of mantissa to 8 bits (\(10010100\)).
- **1.36 Marks**: Correct exponent representation of \(3\) in 4 bits (\(0011\)) resulting in final correct 12-bit answer: `100101000011`.

Step 1: Simplify the first term \(\overline{\overline{A \cdot B} + C}\) using De Morgan's Law:
\(\overline{\overline{A \cdot B}} \cdot \overline{C} = (A \cdot B) \cdot \overline{C} = A \cdot B \cdot \overline{C}\).

Step 2: Simplify the second term \(\overline{B \cdot \overline{C}}\) using De Morgan's Law:
\(\overline{B} + \overline{\overline{C}} = \overline{B} + C\).

Step 3: Combine the simplified terms:
\(Q = (A \cdot B \cdot \overline{C}) \cdot (\overline{B} + C)\).

Step 4: Distribute the terms:
\(Q = (A \cdot B \cdot \overline{C} \cdot \overline{B}) + (A \cdot B \cdot \overline{C} \cdot C)\).

Step 5: Apply the Complement Law (\(X \cdot \overline{X} = 0\)):
Since \(B \cdot \overline{B} = 0\), the first term becomes \(A \cdot 0 \cdot \overline{C} = 0\).
Since \(\overline{C} \cdot C = 0\), the second term becomes \(A \cdot B \cdot 0 = 0\).

Step 6: Combine results:
\(Q = 0 + 0 = 0\).

- **2 Marks**: Correct application of De Morgan's Law on the first term to get \(A \cdot B \cdot \overline{C}\).
- **1.5 Marks**: Correct application of De Morgan's Law on the second term to get \(\overline{B} + C\).
- **1.5 Marks**: Correctly distributing the expression to show products containing \(B \cdot \overline{B}\) and \(C \cdot \overline{C}\).
- **0.86 Marks**: Correct final simplification to `0` (or `False`).

Let us analyze the regular expression structure. It consists of two alternatives separated by the `|` symbol:
- Alternative 1: `[a-z]{2}\d[A-Z]?` requires exactly 2 lowercase letters, followed by exactly 1 digit, and optionally 1 uppercase letter.
- Alternative 2: `test_\d{3}` requires the literal string `test_` followed by exactly 3 digits.

Now we evaluate each string:
1. `ab3`: Matches Alternative 1. `ab` (2 lowercase letters), `3` (1 digit), and no trailing uppercase letter (since it is optional). **Valid**
2. `xy4W`: Matches Alternative 1. `xy` (2 lowercase letters), `4` (1 digit), and `W` (1 uppercase letter). **Valid**
3. `test_10`: Fails both. It starts with `test_` but has only 2 digits (`10`), not 3. **Invalid**
4. `test_952`: Matches Alternative 2. Literal `test_` followed by exactly 3 digits (`952`). **Valid**
5. `a1B`: Fails both. It only has 1 lowercase letter (`a`) instead of the required 2 for Alternative 1. **Invalid**

The matching strings are 1, 2, and 4.

- **2 Marks**: For correctly identifying string 1 as a match and explaining why (optional uppercase matches).
- **1.5 Marks**: For correctly identifying string 2 as a match and explaining why.
- **1.5 Marks**: For correctly identifying string 4 as a match and explaining why (exactly three digits constraint).
- **0.86 Marks**: For identifying strings 3 and 5 as non-matches with valid reasons.

1. Convert Infix to RPN:
- Evaluate parentheses first: `(12 - 4)` becomes `12 4 -`.
- Multiply by 3: `12 4 - 3 *`.
- Next, process `16 / 4`: `16 4 /`.
- Finally, add the two parts: `12 4 - 3 * 16 4 / +`.

2. Stack Evaluation Step-by-Step:
- Push `12`: `[12]`
- Push `4`: `[12, 4]`
- Operator `-`: Pop `4`, Pop `12`. Evaluate \(12 - 4 = 8\). Push `8`: `[8]`
- Push `3`: `[8, 3]`
- Operator `*`: Pop `3`, Pop `8`. Evaluate \(8 \times 3 = 24\). Push `24`: `[24]`
- Push `16`: `[24, 16]`
- Push `4`: `[24, 16, 4]`
- Operator `/`: Pop `4`, Pop `16`. Evaluate \(16 / 4 = 4\). Push `4`: `[24, 4]`
- Operator `+`: Pop `4`, Pop `24`. Evaluate \(24 + 4 = 28\). Push `28`: `[28]`

Final RPN Expression: `12 4 - 3 * 16 4 / +` with a final evaluated result of `28`.

- **2.5 Marks**: Correct conversion of the expression to RPN (`12 4 - 3 * 16 4 / +`). Deduct 1 mark for minor operator placement errors.
- **2.5 Marks**: Complete and correct step-by-step trace showing stack content changes.
- **0.86 Marks**: Correct final evaluated answer of `28`.

To implement this query, we need to join both tables and filter by country, group by name, and then apply a filter on the aggregated sum:

```sql
SELECT Customer.FirstName, Customer.LastName, SUM(Orders.TotalAmount) AS TotalSpent
FROM Customer
INNER JOIN Orders ON Customer.CustomerID = Orders.CustomerID
WHERE Customer.Country = 'UK'
GROUP BY Customer.FirstName, Customer.LastName
HAVING SUM(Orders.TotalAmount) > 150;
```

- **1.5 Marks**: Correctly selecting the columns `Customer.FirstName`, `Customer.LastName` and establishing the aggregate `SUM(Orders.TotalAmount) AS TotalSpent`.
- **1.5 Marks**: Correct implementation of the `INNER JOIN` (or implicit join) linking `Customer` and `Orders` on `CustomerID`.
- **1 Mark**: Correct `WHERE` clause filtering by `Customer.Country = 'UK'`.
- **1 Mark**: Correct `GROUP BY` clause on both `Customer.FirstName` and `Customer.LastName`.
- **0.86 Marks**: Correct `HAVING` clause containing `SUM(Orders.TotalAmount) > 150` (Note: using the alias in HAVING is invalid in standard ANSI SQL, so the aggregate function must be used).

1. Calculate the dot product:
\[ \mathbf{u} \cdot \mathbf{v} = (u_1 \times v_1) + (u_2 \times v_2) + (u_3 \times v_3) \]
\[ \mathbf{u} \cdot \mathbf{v} = (2 \times 3) + (-1 \times 2) + (4 \times -1) \]
\[ \mathbf{u} \cdot \mathbf{v} = 6 - 2 - 4 = 0 \]

2. Relationship to the angle:
The dot product is related to the angle \(\theta\) between two vectors by the equation:
\[ \mathbf{u} \cdot \mathbf{v} = |\mathbf{u}| |\mathbf{v}| \cos(\theta) \]
Since the dot product is exactly \(0\), and neither vector is a zero vector, \(\cos(\theta) = 0\), which means \(\theta = 90^\circ\) (or \(\pi/2\) radians). Thus, the angle is right-angled (orthogonal).

- **3 Marks**: Correct step-by-step arithmetic to calculate the dot product value of `0`.
- **1.5 Marks**: Correctly identifying that the vectors are right-angled / orthogonal.
- **1.36 Marks**: Clear mathematical justification referring to \(\cos(\theta) = 0\) or the property that a dot product of zero indicates perpendicularity.

1. Convert `/22` to a subnet mask:
A `/22` prefix means the first 22 bits of the subnet mask are set to 1, and the remaining 10 bits are set to 0.
- First octet: `11111111` = 255
- Second octet: `11111111` = 255
- Third octet: `11111100` = 252 (since \(128 + 64 + 32 + 16 + 8 + 4 = 252\))
- Fourth octet: `00000000` = 0
Resulting subnet mask: `255.255.252.0`.

2. Calculate usable host IP addresses:
- The total number of bits in an IPv4 address is 32.
- Host bits = \(32 - 22 = 10\).
- Total possible IP addresses = \(2^{10} = 1024\).
- Subtract 2 for the network address (all host bits 0) and the directed broadcast address (all host bits 1).
- Usable host IP addresses = \(1024 - 2 = 1022\).

- **3 Marks**: Correct binary expansion and calculation of the dotted-decimal subnet mask `255.255.252.0` (award 1 mark per correct octet starting from the third).
- **2 Marks**: Correct calculation of host bits (10) and total addresses (1024).
- **0.86 Marks**: Correctly subtracting 2 to give the final usable host count of `1022`.

Let's perform the operations step-by-step:

1. **Step 1: Bitwise AND** (`AND R3, R1, R2`)
- `R1`: `0011 1100`
- `R2`: `0101 1010`
- Perform AND on each column:
```
0011 1100
AND 0101 1010
-------------
0001 1000 (R3)
```

2. **Step 2: Logical Shift Left by 2** (`LSL R4, R3, #2`)
- `R3`: `0001 1000`
- Shift left by 2 bits, padding with zeros on the right:
- Shift 1: `0011 0000`
- Shift 2: `0110 0000`
- `R4` value: `0110 0000`

3. **Step 3: Bitwise OR** (`ORR R1, R4, R2`)
- `R4`: `0110 0000`
- `R2`: `0101 1010`
- Perform OR on each column:
```
0110 0000
OR 0101 1010
-------------
0111 1010 (R1)
```

Final 8-bit binary value in `R1` is `01111010`.

- **2 Marks**: Correctly performing the bitwise AND operation to get R3 = `00011000`.
- **2 Marks**: Correctly performing the logical shift left by 2 positions to get R4 = `01100000`.
- **1.86 Marks**: Correctly performing the final bitwise OR operation to get R1 = `01111010`.

The mantissa is \(10101000_2\). Since it is in two's complement, the MSB has a value of \(-1\). Mantissa = \(-1 + 0.25 + 0.0625 = -0.6875\). The exponent is \(0011_2\) which represents \(+3\) in denary. Therefore, the value is calculated as \(-0.6875 \times 2^3 = -0.6875 \times 8 = -5.5\).

[1 Mark] Identifying the exponent as +3. [1 Mark] Identifying the mantissa MSB as representing -1. [1 Mark] Showing the correct fractional values of the mantissa (0.25 and 0.0625). [1 Mark] Correct calculation of the mantissa as -0.6875. [1.86 Marks] Correct final denary value of -5.5.

1. Expand the terms: \(A \cdot B + A \cdot B + A \cdot C + B \cdot B + B \cdot C\). 2. Apply the Idempotent Law (\(A \cdot B + A \cdot B = A \cdot B\) and \(B \cdot B = B\)) to get: \(A \cdot B + A \cdot C + B + B \cdot C\). 3. Apply the Absorption Law (\(B + B \cdot C = B\)) to get: \(A \cdot B + A \cdot C + B\). 4. Apply the Absorption Law again (\(B + A \cdot B = B\)) to get the final simplified expression: \(B + A \cdot C\).

[1 Mark] Correct expansion of the initial expression terms. [1 Mark] Application of the Idempotent Law to simplify terms. [1 Mark] Application of the Absorption Law to simplify B + B.C. [1 Mark] Application of the Absorption Law to simplify B + A.B. [1.86 Marks] Correct final simplified expression (accept B + AC).

The first three octets of the subnet mask are 255, so the network prefix remains \(192.168.75\). For the fourth octet: \(142\) in binary is \(10001110_2\). The mask \(224\) in binary is \(11100000_2\). Performing a bitwise AND operation: \(10001110 \text{ AND } 11100000 = 10000000_2\), which is \(128\) in denary. Combining these gives the network address of \(192.168.75.128\).

[1 Mark] Correct conversion of host octet 142 to binary (10001110). [1 Mark] Correct conversion of mask octet 224 to binary (11100000). [1 Mark] Stating that a bitwise AND operation is performed between the host and mask. [1 Mark] Correctly calculating the resulting binary octet as 10000000. [1.86 Marks] Correct final dotted decimal address: 192.168.75.128.

Convert individual parenthesized sub-expressions first: \((A + B) \rightarrow A\,B\,+\), \((C - D) \rightarrow C\,D\,-\), and \((E + F) \rightarrow E\,F\,+\). Next, apply the multiplication operator to the first two results: \((A\,B\,+) * (C\,D\,-) \rightarrow A\,B\,+\,C\,D\,-\,*\). Finally, apply the division operator with the third result: \((A\,B\,+\,C\,D\,-\,*) / (E\,F\,+) \rightarrow A\,B\,+\,C\,D\,-\,*\,E\,F\,+\,/\).

[1 Mark] Converting (A + B) to postfix (AB+). [1 Mark] Converting (C - D) to postfix (CD-) and (E + F) to postfix (EF+). [1 Mark] Correctly applying the multiplication operator to get AB+CD-*. [1 Mark] Correctly placing the division operator at the end. [1.86 Marks] Fully correct final Reverse Polish Notation expression: A B + C D - * E F + /

The dot product formula is \(\mathbf{a} \cdot \mathbf{b} = (a_1 \times b_1) + (a_2 \times b_2) + (a_3 \times b_3)\). Substituting the values: \(5 \times (-3) + (-2) \times 6 + 4 \times 1 = -15 - 12 + 4 = -23\).

[1 Mark] Recalling or demonstrating the correct dot product formula. [1 Mark] Calculating the product of the first elements as -15. [1 Mark] Calculating the product of the second elements as -12. [1 Mark] Calculating the product of the third elements as 4. [1.86 Marks] Correct final summed integer value of -23.

Stage 1: Perform the bitwise AND of R1 (01101100) and R2 (10101010), which yields R3 = 00101000. Stage 2: Perform Logical Shift Left (LSL) by 2 bits on R3. Shifting 00101000 left by 2 positions yields R4 = 10100000, with zeroes padded on the right.

[1 Mark] Correctly calculating the first half of the AND operation. [1 Mark] Correctly calculating the second half of the AND operation. [1 Mark] Identifying R3 as 00101000. [1 Mark] Correctly shifting the bits left by 2 positions. [1.86 Marks] Providing the correct final 8-bit binary string: 10100000.

In 1NF, CourseName and Instructor depend only on CourseID (part of the composite key), which represents a partial key dependency. To convert to 2NF, we remove these attributes into a new relation. This results in: 1. \(\text{StudentGrade}(\underline{\text{StudentID}}, \underline{\text{CourseID}}, \text{Grade})\) and 2. \(\text{Course}(\underline{\text{CourseID}}, \text{CourseName}, \text{Instructor})\).

[1 Mark] Identifying that CourseName and Instructor have a partial key dependency. [1 Mark] Defining the StudentGrade relation with the composite primary key. [1 Mark] Including Grade in the StudentGrade relation as it depends on both keys. [1 Mark] Defining the Course relation with CourseID as its primary key. [1.86 Marks] Listing both fully correct 2NF table schemas with keys correctly indicated.

### Part 1: ACID Properties in the Ticketing Scenario
- **Atomicity**: This ensures that all operations within a ticket booking transaction are treated as a single, indivisible unit of work. For instance, the sequence of reserving seat 12B, processing the payment, and sending the confirmation email must either complete in its entirety or not happen at all. If the payment fails mid-way, Atomicity ensures the seat reservation is rolled back, preventing orphaned 'reserved' seats that have not been paid for.
- **Consistency**: This ensures that a transaction can only transition the database from one valid state to another, maintaining all predefined schema rules and constraints. In this scenario, a consistency rule might be: 'A seat cannot have more than one paid ticket associated with it.' If a transaction attempts to write a second ticket for seat 12B, the database system must reject the transaction to preserve consistency.
- **Isolation**: In a highly concurrent environment, many users are booking tickets simultaneously. Isolation ensures that concurrent transactions execute as if they were running sequentially. For example, while Customer A's transaction is actively processing the payment for seat 12B, Customer B's query should not be able to read that seat as 'available' or 'partially reserved' until Customer A's transaction is fully committed or rolled back.
- **Durability**: Once a ticket reservation transaction is confirmed and committed, the changes are written to non-volatile storage (such as solid-state drives with transactional logging). If the database server suffers a sudden power failure or crash immediately after the customer receives their confirmation screen, Durability guarantees that their booking is not lost when the server boots back up.

### Part 2: Concurrency Conflicts and Record Locking
- **The Lost Update Problem**: This occurs when two transactions read the same data concurrently, modify it, and write it back. For example:
1. Customer A reads seat 12B status (Available).
2. Customer B reads seat 12B status (Available).
3. Customer A marks seat 12B as 'Reserved' and saves.
4. Customer B marks seat 12B as 'Reserved' and saves, overwriting Customer A's update. Both customers believe they have booked the seat.
- **How Record Locking Resolves This**: When a transaction begins modifying a record, a lock is applied, blocking other transactions from accessing that record until the lock is released.
- **Shared Locks (Read Locks)**: Multiple transactions can hold a shared lock on a record simultaneously, allowing them to read the seat's status (e.g., multiple users checking seat availability). However, no transaction can write to or modify the record while a shared lock exists.
- **Exclusive Locks (Write Locks)**: When a transaction wishes to update the seat status to 'Reserved', it must acquire an exclusive lock. Only one transaction can hold an exclusive lock on a record at a time. It prevents any other transactions from reading or writing to that record. If Customer A acquires an exclusive lock on seat 12B, Customer B's transaction must wait until Customer A's transaction finishes and releases the lock.

### Part 3: Operational Challenges (Deadlocks and Mitigations)
- **The Deadlock Problem**: Extensive use of exclusive record locking can lead to deadlocks. This occurs when two or more transactions are waiting for each other to release locks. For example:
- Transaction 1 locks Seat A and requests a lock on Seat B.
- Transaction 2 locks Seat B and requests a lock on Seat A.
Neither transaction can proceed, causing the system to freeze or hang indefinitely.
- **Deadlock Mitigation and Resolution Strategies**:
- **Deadlock Detection**: The database engine runs background processes to construct a resource allocation graph. If a cycle (loop) is detected, the database engine aborts one of the transactions (the 'victim'), rolls back its changes, releases its locks, and allows the other transaction to complete.
- **Deadlock Prevention (Lock Ordering)**: The system can require all transactions to lock resources in a strictly defined, sequential order (e.g., always lock seats in alphabetical/numerical order: Seat A first, then Seat B). If Transaction 2 is forced to lock Seat A before Seat B, the deadlock situation cannot arise.
- **Lock Timeouts**: Every lock request is given a maximum wait time (timeout). If Transaction 1 cannot acquire the lock on Seat B within 5 seconds, it aborts, releases its lock on Seat A, and retries later, preventing a permanent freeze.

### Level of Response marking grid:

- **Level 3 (9-12 marks)**: The candidate provides a detailed, coherent, and highly technical response. All four ACID properties are clearly explained and accurately applied to the ticket booking system. The mechanics of the lost update problem and record locking (clearly distinguishing shared and exclusive locks) are accurately described. The deadlock scenario is correctly explained, and at least two practical mitigation/prevention methods (e.g., lock ordering, detection/rollback, or timeouts) are analyzed. Technical vocabulary is used correctly throughout.
- **Level 2 (5-8 marks)**: The candidate provides a mostly structured response. At least three ACID properties are correctly explained with some application to the context. Record locking and its role in resolving concurrency issues is understood, though the distinction between shared and exclusive locks may be weak or incomplete. The candidate identifies deadlocks but provides limited explanation of mitigation strategies.
- **Level 1 (1-4 marks)**: The candidate provides a basic or superficial response. They may define some ACID terms in isolation without clear application to the scenario. There is a primitive understanding of locking (e.g., 'it stops others from using it') but lacks technical detail. Deadlocks may be mentioned but without clear explanation or resolution.

### Indicative Content:
- **Atomicity**: Complete transaction or nothing; tickets aren't charged without being booked.
- **Consistency**: Preserves database rules; no double booking of the exact same primary key/seat.
- **Isolation**: Concurrent transactions do not interfere; temporary states are invisible.
- **Durability**: Commits survive crashes; saved to non-volatile disk logs.
- **Lost Update**: Interleaved read-modify-write sequences leading to overwritten data.
- **Shared Locks**: Multi-reader, zero-writer block.
- **Exclusive Locks**: Single-writer, zero-reader block.
- **Deadlock**: Circular wait conditions (T1 waits for T2, T2 waits for T1).
- **Deadlock Solutions**: Deadlock detection & rollback, lock ordering, or lock timeouts.