MetadataPastPaper.sampleTitle

Perform the subtraction of the denary number 54 from the denary number -43 using 8-bit two's complement binary addition. That is, calculate \(-43 - 54\).

Show all your working by converting both numbers into 8-bit two's complement representation, adding them, and state whether an overflow error has occurred with a suitable justification.

The fetch stage of the Fetch-Execute cycle can be described using Register Transfer Notation (RTN).

(a) Write down the four main steps of the fetch stage using Register Transfer Notation (RTN). [4]
(b) Describe how the Program Counter (PC) and the Memory Address Register (MAR) cooperate during the very first step of this stage. [1]

A student database table, `STUDENT_ENROLMENT`, contains the following attributes:
`StudentID`, `StudentName`, `CourseCode`, `CourseTitle`, `TutorName`, `TutorOffice`

The primary key is the composite key `(StudentID, CourseCode)`.
Each student has only one name. Each course has a single course title and is taught by exactly one tutor who has one office.

(a) Explain why this table is in First Normal Form (1NF). [1]
(b) Identify the partial key dependencies in this table and explain how they violate Second Normal Form (2NF). [2]
(c) Describe the table structures (including primary keys) resulting from converting this relation into 2NF. [2]

An IP address is given as `192.168.45.138` with a subnet mask of `255.255.255.224`.

(a) Write the subnet mask `255.255.255.224` in 32-bit binary notation (grouped as four 8-bit octets). [1]
(b) Calculate the Network ID (subnet address) for this IP address. Show your working by demonstrating the bitwise AND process on the last octet in binary. [3]
(c) State the address class of the IP address `192.168.45.138`. [1]

### Part (a)
Compare the ASCII and Unicode character representation standards. Your answer should explain why Unicode was developed and the impact of using Unicode on data transmission and storage. [5]

### Part (b)
An analogue audio signal is converted into a digital format.
Describe how the sampling rate and sampling resolution affect:
1. the quality of the recorded sound.
2. the size of the resulting audio file. [5]

### Part (c)
An audio engineer records a 40-second audio track.
The track is stereo (2 channels).
The audio is sampled at a frequency of 48 kHz.
Each sample is encoded using a 16-bit resolution.

Calculate the file size of the uncompressed audio recording in Megabytes (MB). Assume \(1 \text{ MB} = 1,000,000 \text{ bytes}\). Show all your working. [3.75]

### Part (a)
The Fetch-Execute (F-E) cycle is the foundational process of a CPU.
Describe the role and changes in contents of the following registers during the **fetch** phase of the cycle:
1. Program Counter (PC)
2. Memory Address Register (MAR)
3. Memory Data Register (MDR) [6]

### Part (b)
The system bus consists of the Address Bus, Data Bus, and Control Bus.
1. Explain how the width of the **Address Bus** affects the computer's memory capacity. [2]
2. Explain how the width of the **Data Bus** affects system performance. [2]

### Part (c)
In assembly language, different addressing modes are used to access data.
Consider the following two addressing modes:
- **Direct Addressing** (e.g., `LDD 200`)
- **Indirect Addressing** (e.g., `LDI 200`)

Describe the difference between these two addressing modes in terms of how the actual data is retrieved from memory, and identify how many memory read operations are required for each mode to obtain the operand value. [3.75]

### Part (a)
A school database stores student enrollment information in a single, unnormalized table:
`EnrollmentSummary(StudentID, StudentName, CourseID, CourseTitle, Instructor, Grade)`

The composite primary key for this table is `(StudentID, CourseID)`.

1. Explain why this table is in First Normal Form (1NF) but **not** in Second Normal Form (2NF). Refer to specific fields in your explanation. [3]
2. Describe the steps required to normalize this table to 2NF. Show the resulting table structures, clearly identifying the primary keys and foreign keys. [3]

### Part (b)
In relational databases:
1. Define the term **referential integrity** and explain how it is enforced using foreign keys. [2]
2. Explain the difference between a **primary key** and a **candidate key**. [2]

### Part (c)
Write a SQL query to display the `StudentID`, `StudentName`, and `Grade` for all students who scored a grade of 'A' or 'A+' in the course with `CourseTitle` equal to 'Computer Science'.
You must use the normalized 2NF tables:
- `STUDENT(StudentID, StudentName)`
- `COURSE(CourseID, CourseTitle, Instructor)`
- `ENROLLMENT(StudentID, CourseID, Grade)` [3.75]

### Part (a)
An IP address is used to identify a device on a network.
1. Describe the structure of an IPv4 address, explaining the role of the **network ID** and **host ID** parts of the address. [3]
2. An organization is assigned the classless IP block `192.168.10.0/26`. Explain the purpose of the `/26` CIDR notation (subnet mask) and calculate how many unique host addresses are available for use in this subnet. [3]

### Part (b)
When data is transmitted across the internet, packet switching is used.
Describe the role of a **router** in a packet-switched network, including how it uses routing tables and headers to direct packets to their destination. [4]

### Part (c)
Compare the **Client-Server** and **Peer-to-Peer (P2P)** network models. State **one** advantage and **one** disadvantage of using a Peer-to-Peer model instead of a Client-Server model. [3.75]

A meteorology station records daily temperatures in a 1D array of Real values. You are required to write a pseudocode function `LongestRisingStreak` to find the longest continuous sequence of days where the temperature strictly increases from one day to the next.

The function takes two parameters:
1. `TempArray`: A 1D array of Real numbers.
2. `NumDays`: An Integer representing the total number of elements in the array.

The function must return an Integer representing the length of the longest streak. A streak is defined as the number of days in the continuous sequence (for example, if temperatures are `[12.5, 13.0, 14.2, 11.0]`, the temperatures increase from 12.5 to 13.0, and 13.0 to 14.2, which is a streak of 3 days. A single day on its own has a streak of 1).

If the array has fewer than 1 element, the function should return 0.

Assume 1-based indexing for the array.

Write the pseudocode for the function `LongestRisingStreak`.

A program contains a sorted 1D array of strings named `NameList` of size 100 (indexed 1 to 100).

Write a recursive pseudocode function `RecursiveSearch` that searches for a specific string target in the array.

The function takes three parameters:
1. `Target` : the String to find.
2. `Low` : the starting index of the search range (Integer).
3. `High` : the ending index of the search range (Integer).

The function must return the Integer index of the target string if found, or -1 if the target string is not in the array.

You may assume `NameList` is globally accessible and already declared and populated with sorted strings.

Write the pseudocode for the recursive function `RecursiveSearch`.

A circular queue is implemented using a 1D array `QueueData` of size 10 (indexed 1 to 10). The following global pointers and variables are used:
- `HeadPointer` : Integer pointing to the index of the first item in the queue.
- `TailPointer` : Integer pointing to the index of the last item in the queue.
- `NumItems` : Integer representing the current number of items in the queue.
- `MaxItems` : Integer constant initialized to 10.

When the queue is empty, `NumItems` is 0, `HeadPointer` is 0, and `TailPointer` is 0.

Write a pseudocode procedure `Enqueue` that takes a string parameter `NewItem` and attempts to add it to the circular queue.

The procedure must:
1. Check if the queue is full. If it is full, display an appropriate error message and do not add the item.
2. If the queue is empty, update both pointers correctly to insert the first element.
3. If the queue is not empty and not full, update `TailPointer` correctly (handling circular wrap-around) and insert the item.
4. Increment `NumItems` accordingly.

Write the pseudocode for the procedure `Enqueue`.

A software application stores employee data in a text file named `"Employees.txt"`. Each line of the file contains the record for one employee in comma-separated value (CSV) format: `EmployeeID,Department,Salary` (for example, `"1094,Finance,52000"`).

Write a pseudocode procedure `FilterDepartment` that takes a string parameter `DeptName`.

The procedure must:
1. Open the file `"Employees.txt"` for reading.
2. Create or overwrite a text file named `DeptName & ".txt"` (for example, if `DeptName` is `"Finance"`, the file created is `"Finance.txt"`) to store the filtered results.
3. Read `"Employees.txt"` line by line until the end of the file is reached.
4. Extract the individual fields (`EmployeeID`, `Department`, `Salary`) from each line. You may assume a pre-existing function `GetField(Line : STRING, FieldNum : INTEGER) RETURNS STRING` is available, which returns the specified field (1 for ID, 2 for Department, 3 for Salary) from a comma-separated string.
5. If the extracted department matches `DeptName` (case-sensitive), write a new line to the output file containing only the `EmployeeID` and `Salary` separated by a comma.
6. Close both files.

Use the standard Cambridge pseudocode file-handling operations:
- `OPENFILE FOR READ`
- `OPENFILE FOR WRITE`
- `READFILE , `
- `WRITEFILE , `
- `CLOSEFILE `
- `EOF()`

Write the pseudocode for the procedure `FilterDepartment`.

Run-length encoding (RLE) is a basic data compression technique where consecutive identical characters are recorded as a single character value and a count of its repetitions.

Write a pseudocode function `CompressString` that takes a single string parameter `InputStr` consisting only of uppercase letters (for example, `"AAAAABBBCCDA"`). The function must return the compressed version of the string where each consecutive run of a character is replaced by the number of occurrences followed immediately by that character (for example, `"5A3B2C1D1A"`).

If `InputStr` is empty, the function must return an empty string.

You can use the following standard string functions:
- `LENGTH(s : STRING) RETURNS INTEGER` : returns the number of characters in string `s`.
- `SUBSTR(s : STRING, start : INTEGER, length : INTEGER) RETURNS STRING` : returns a substring from `s` starting at position `start` (1-indexed) with the specified `length`.
- `NUM_TO_STR(n : NUMERIC) RETURNS STRING` : converts a numeric value to its string representation.

Write the pseudocode for the function `CompressString`.

A system is designed to manage library book returns. A modular program is planned using a Structure Chart.

The module `ProcessReturns` performs the following steps:
1. Calls `GetBookDetails` which prompts the user for the `BookID`. It returns `BookID` (String) and a boolean flag `IsValid`.
2. If the book is valid (determined by `IsValid`), it calls `CalculateFine` which takes `BookID` as an input parameter and returns a real value `FineAmount` and a boolean flag `IsOverdue`.
3. If the book is overdue (determined by `IsOverdue`), it calls `UpdateRecords` which takes `BookID` and `FineAmount` as parameters.
4. Finally, it calls `PrintReceipt` which takes `BookID` and `FineAmount` as parameters.

(a) Complete the following interface table for the parameters passed between modules. For each entry, specify the module calling, the module called, the parameter name, the data type, and the direction (In, Out, or Both).

(b) Describe how selection (conditional module execution) is represented visually in a Structure Chart.

(c) State the difference between a 'data couple' and a 'control couple' in a Structure Chart. Give an example of a control couple used in this library system.

A programmer designs the following flowchart to count how many operations it takes to reduce a positive integer \( N \) to 1.

```
[Start]
|
V
[Read N]
|
V
[Count <- 0]
|
+--->+
| |
| V
| < N > 1 > ----(No)----> [Print Count] ---> [Stop]
| |
| (Yes)
| |
| V
| < N MOD 2 = 0 > ---(Yes)---> [N <- N / 2]
| | |
| (No) |
| | V
| +-----------------------> [Count <- Count + 1]
| |
+----------------------------------+
```

(a) Complete the trace table below for the input value \( N = 4 \).

| N | Count | N > 1 | N MOD 2 = 0 |
|---|-------|-------|-------------|
| | | | |

(b) Identify the critical logical error that occurs when an odd value of \( N \) (such as \( N = 5 \)) is processed, and explain why this error happens.

(c) Describe how the flowchart should be modified to resolve this issue, ensuring that odd numbers are decremented by 1 (to make them even) before dividing by 2 on the next loop iteration, while counting each decrement as an operation.

A state transition diagram is used to design a compiler's lexical analyzer that validates variable names.

The rules for a valid variable name are:
1. It must start with a lowercase or uppercase letter (character class Letter).
2. It can be followed by any number of letters or digits (character class Digit).
3. It must end with a single underscore '_' character.
4. Any input containing characters outside these classes, or additional characters after the underscore, must transition to an error state SE.

The system has four states:
- S0: Start State
- S1: Variable Name Body (after first letter read)
- S2: Terminal / Accept State (after valid underscore)
- SE: Error State (invalid sequence/character)

(a) Complete the State Transition Table below by writing the next state for each combination of current state and input type.

| Current State | Input: Letter | Input: Digit | Input: Underscore | Input: Other |
|---------------|---------------|--------------|-------------------|--------------|
| S0 | | | | |
| S1 | | | | |
| S2 | | | | |
| SE | | | | |

(b) Trace the state transitions for the following two inputs, starting from state S0. List each state transitioned through (e.g., S0 -> ...):
1. Input string: "x3_"
2. Input string: "7a_"

(c) Explain why this system is classified as a Deterministic Finite Automaton (DFA) / Finite State Machine (FSM).

A logic programming system contains the following database of facts and rules:

`parent(arthur, bill).`
`parent(bill, charlie).`
`parent(bill, diana).`
`ancestor(X, Y) :- parent(X, Y).`
`ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).`

Explain, with reference to the facts and rules provided, how the logic interpreter uses backtracking and unification to resolve the query:
`?- ancestor(arthur, diana).`

In the context of database management systems (DBMS), describe the structural differences and operational roles of:
(a) Entity Integrity vs. Referential Integrity.
(b) Explain how the DBMS checks and maintains referential integrity when an instruction is executed to delete a record from a parent table that has corresponding records in a child table.

Many modern development environments compile source code into intermediate code (such as Java bytecode or Common Intermediate Language) rather than native machine code.

(a) Explain two distinct benefits of using intermediate code.
(b) Describe how a Virtual Machine (VM) utilizes this intermediate code to run the program on a specific target computer, and explain how Just-In-Time (JIT) compilation improves execution speed.

Compare the imperative programming paradigm with the declarative programming paradigm.

(a) Describe how execution control and state management differ between the two paradigms.
(b) Consider the list format `[Head | Tail]` in declarative programming (Prolog). Explain how recursion is used to process lists, and construct a logical rule `list_length(List, Length)` that recursively calculates the size of a list.

A relational database table is defined with the following schema to store details of training sessions:
`TrainingSession(SessionID, TrainerID, TrainerName, VenueID, VenueAddress, Date)`

The following functional dependencies exist in the relation:
- `SessionID -> TrainerID, VenueID, Date`
- `TrainerID -> TrainerName`
- `VenueID -> VenueAddress`

(a) Explain why this relation is not in Third Normal Form (3NF).
(b) Normalize the schema into 3NF, clearly identifying the primary keys and foreign keys for each resulting table.

A virtual machine (VM) can provide hardware emulation or process-level isolation.

(a) Explain the difference between a Type 1 (bare-metal) hypervisor and a Type 2 (hosted) hypervisor.
(b) Analyze the advantages and disadvantages of using a Virtual Machine to run legacy system software on modern computer hardware.

In Object-Oriented Programming (OOP):

(a) Explain how dynamic binding operates and state how it supports the implementation of polymorphism.
(b) Describe how the runtime environment utilizes a Virtual Method Table (VMT) to resolve polymorphic method calls during execution.

Consider this Prolog program designed to process lists and match elements:

`member(X, [X | _]).`
`member(X, [_ | Tail]) :- member(X, Tail).`

(a) Explain the purpose and operation of the anonymous variable `_` in both rules.
(b) Walk through the step-by-step execution and search tree of the query:
`?- member(green, [red, blue, green]).`
Explicitly mention where unification succeeds or fails, and where recursion occurs.

A declarative programming database contains the following facts and rules regarding university courses and student progress:

```prolog
course(101, basic_programming).
course(102, algorithms_1).
course(201, algorithms_2).
course(301, expert_systems).

prereq(101, 102).
prereq(102, 201).
prereq(201, 301).

completed(lucas, 101).
completed(lucas, 102).
completed(anaya, 101).

can_take(Student, Course) :-
prereq(Pre, Course),
completed(Student, Pre).
```

(a) State the goal/query that would find all courses that `lucas` is eligible to take, and describe how backtracking is used by the interpreter to resolve this query. [3.8 marks]

(b) Define a recursive rule `deep_prereq(X, Y)` that is true if course `Y` is a direct or indirect prerequisite of course `X`. [3 marks]

An instruction pipeline has five stages:
1. Instruction Fetch (IF)
2. Instruction Decode (ID)
3. Operand Fetch (OF)
4. Instruction Execute (EX)
5. Write Back (WB)

(a) Explain how instruction pipelining improves processor performance and describe what is meant by a "pipeline hazard" (specifically a data hazard). [3.8 marks]

(b) Consider the following sequence of instructions:
```assembly
ADD R1, R2, R3 ; R1 <- R2 + R3
SUB R4, R1, R5 ; R4 <- R1 - R5
```
Explain the specific pipelining problem that occurs with this sequence of instructions and describe one software or hardware solution to resolve it. [3 marks]

In database transaction management, concurrency control is essential to ensure data integrity when multiple users access the database simultaneously.

(a) Explain what is meant by a "dirty read" (uncommitted dependency) in database transactions, and describe how the use of a lock can prevent this problem. [3.8 marks]

(b) Explain how the use of database locks can lead to a "deadlock", and describe one technique used by a Database Management System (DBMS) to resolve a deadlock. [3 marks]

Create a new project in your chosen programming language (Python, Java, or Visual Basic). Save your source files.

### Task 1: Object-Oriented Programming (OOP) implementation

You are implementing a computerized library management system. Write code to represent the resources held by the library.

1. Define a base class `Resource` with the following:
- Private attributes:
- `ResourceID` of type String
- `Title` of type String
- A constructor that accepts the resource ID and title as parameters.
- Public getter methods `GetResourceID()` and `GetTitle()` that return their respective values.
- An abstract or virtual method `CalculateFine(DaysOverdue : Integer)` which returns a real value representing the penalty fee.

2. Define a subclass `Book` that inherits from `Resource` and includes:
- An additional private attribute `Author` of type String.
- A constructor that accepts resource ID, title, and author. It must call the parent constructor with the appropriate arguments.
- An overridden version of the method `CalculateFine(DaysOverdue : Integer)`. The fine is calculated as $0.50 per day overdue. Returns the fine as a real number.

3. Define a subclass `Journal` that inherits from `Resource` and includes:
- An additional private attribute `IssueNumber` of type Integer.
- A constructor that accepts resource ID, title, and issue number. It must call the parent constructor with the appropriate arguments.
- An overridden version of the method `CalculateFine(DaysOverdue : Integer)`. The fine is calculated as a flat fee of $2.00, plus $1.00 for every day overdue. Returns the fine as a real number.

### Task 2: Main Program and Output Demonstration

Write main program code to perform the following operations:

1. Declare a 1D array or list named `ResourceList` containing 4 elements of type `Resource`.
2. Instantiate the following objects and store them in the array:
- `Book` with ID: "B01", Title: "Algorithms", Author: "T. Cormen"
- `Book` with ID: "B02", Title: "Computer Networks", Author: "A. Tanenbaum"
- `Journal` with ID: "J01", Title: "IEEE Software", Issue Number: 42
- `Journal` with ID: "J02", Title: "ACM Transactions", Issue Number: 109
3. Write a procedure `DisplayFines(Days : Integer)` which:
- Iterates through each object in `ResourceList`.
- Outputs the `ResourceID`, the `Title`, and the calculated fine for that resource given the number of days overdue. Format the fine to 2 decimal places.
4. From the main program, call `DisplayFines` passing `5` as the parameter.

Take a screenshot of the main program's output showing the calculated fines.

Create a new project in your chosen programming language (Python, Java, or Visual Basic). Save your source files.

### Task 1: Node Representation of Binary Search Tree

You need to implement a Binary Search Tree (BST) using a static array of nodes to store string values.

1. Define a class `Node` with the following private attributes:
- `Data` of type String
- `LeftPointer` of type Integer
- `RightPointer` of type Integer
It must have:
- A constructor that accepts a String parameter to initialize `Data`. `LeftPointer` and `RightPointer` must be initialized to -1.
- Public getter and setter methods for all three attributes: `GetData()`, `SetData()`, `GetLeft()`, `SetLeft()`, `GetRight()`, `SetRight()`.

2. Define a class `BinaryTree` with the following private attributes:
- `Tree` as an array of 10 `Node` elements
- `RootPointer` of type Integer
- `FreePointer` of type Integer

The constructor of `BinaryTree` must:
- Initialize `RootPointer` to -1.
- Initialize `FreePointer` to 0.
- Instantiate all 10 nodes in the array with empty data `""`.
- Programmatically set the `LeftPointer` of each node to link to the index of the next node (index 0 links to 1, index 1 to 2, ..., index 8 to 9, and index 9 to -1). This forms the free list structure. (The `RightPointer` of each node should remain -1).

3. Write a public method `Insert(NewData : String)` inside `BinaryTree` which:
- Checks if there are no free nodes (i.e., `FreePointer` is -1). If so, prints "Tree is full" and returns False.
- Retrieves the node at index `FreePointer` to store `NewData`.
- Updates `FreePointer` to point to the `LeftPointer` of the node being used.
- Initializes the used node's `LeftPointer` and `RightPointer` to -1.
- If `RootPointer` is -1, set `RootPointer` to this node index and return True.
- Otherwise, traversers the tree iteratively from `RootPointer` to find the correct insertion position based on standard BST behavior (if `NewData` < current node's data, go left; else go right) and links the parent node to this node index. Returns True.

4. Write a recursive helper method `InOrderTraversal(NodePointer : Integer)` that performs an in-order print of the elements.
5. Write a public method `PrintAll()` which starts the recursive `InOrderTraversal` from `RootPointer`.

### Task 2: Main Program and Output Demonstration

Write main program code to perform the following:
1. Instantiate a `BinaryTree` object.
2. Insert the following 6 values in this precise order: "Mango", "Apple", "Peach", "Banana", "Cherry", "Plum".
3. Call `PrintAll()` to print the contents of the tree.

Take a screenshot of the main program's output showing the items sorted alphabetically.

Create a new project in your chosen programming language (Python, Java, or Visual Basic). Save your source files.

### Task 1: Stack Abstract Data Type (ADT) with Search

You need to implement a static array-based stack class named `CargoStack` with custom recursive search properties.

1. Define a class `CargoStack` with the following private attributes:
- `StackData` : an array of 8 String elements
- `TopPointer` : Integer representing the top index of the stack.

2. Write a constructor that:
- Initializes `TopPointer` to -1.
- Initializes all elements of the `StackData` array to empty strings `""`.

3. Write the following public methods inside `CargoStack`:
- `Push(Item : String)` which returns a Boolean:
- If the stack is full (holds 8 elements), returns False.
- Otherwise, increments `TopPointer`, saves `Item` to that position in the array, and returns True.
- `Pop()` which returns a String:
- If the stack is empty, returns an empty string `""`.
- Otherwise, retrieves the string at `TopPointer`, replaces that stack slot with an empty string `""`, decrements `TopPointer`, and returns the retrieved string.
- `RecursiveSearch(Item : String, CurrentIndex : Integer)` which returns an Integer:
- A recursive search method that checks for `Item` starting from `CurrentIndex` (initially called with `TopPointer`) going down to index 0.
- If `CurrentIndex < 0`, it means the item was not found; return -1.
- If the element in `StackData[CurrentIndex]` matches `Item`, return `CurrentIndex`.
- Otherwise, return the result of recursively calling `RecursiveSearch` with the same `Item` and `CurrentIndex - 1`.

### Task 2: Demonstration and Output Capture

Write main program code to perform the following operations in sequence:

1. Create an instance of `CargoStack`.
2. Attempt to push the following strings sequentially into the stack: "Cargo_A", "Cargo_B", "Cargo_C", "Cargo_D", "Cargo_E", "Cargo_F". Print the returned boolean value for each push attempt to confirm success.
3. Perform a recursive search for "Cargo_C" starting from the current `TopPointer`. Print whether it was found and its array index.
4. Perform a recursive search for "Cargo_Z" starting from the current `TopPointer`. Print whether it was found.
5. Call `Pop()` three times, printing the popped values.
6. Search for "Cargo_E" again after the pop operations. Print whether it is still found.

Take a screenshot of your main program's terminal output.