Computer Science 9618/33 — May/June 2025

Background Concept

A user-defined data type is created by the programmer when the built-in types alone are not enough to describe the data clearly. In this syllabus, one important kind is a composite user-defined type: a single structure that groups several related fields together.

Here, one VideoLibrary item needs to store several different pieces of information about one video, so a composite type is appropriate. Each field inside it should use the most suitable basic type:

• STRING for text or mixed letters and numbers
• INTEGER for whole numbers
• DATE for calendar dates

The aim is to model the real-world data accurately and make later program processing easier.

Understanding the Question

The question asks for pseudocode declarations for a composite data type called VideoLibrary. It is not asking for variables, input statements or an array of videos. It wants the type definition itself.

The fields required are:

• identity code
• title
• year released
• date purchased
• format
• running time in minutes

The key clue is "composite data type", which means one structure containing multiple named fields.

Approach

The best approach is:

1. Start a type definition called VideoLibrary.
2. Add one declaration line for each required field.
3. Choose the most appropriate type for each field.
4. Close the type definition.

For the types:

• identity code can contain letters and numbers, so STRING
• title is text, so STRING
• year released is a whole number, so INTEGER
• date purchased is a date, so DATE
• format is text such as DVD or MP4, so STRING
• running time is counted in whole minutes, so INTEGER

Step-by-Step Reasoning

TYPE VideoLibrary

• This begins the declaration of a new user-defined type called VideoLibrary.

DECLARE IdentityCode : STRING

• The identity code may include both letters and numbers.
• Because it is not purely numeric data for calculation, STRING is the best choice.

DECLARE Title : STRING

• A title is text, possibly multiple words, so STRING is appropriate.

DECLARE YearReleased : INTEGER

• A year such as 1999 or 2024 is a whole number.
• No decimal places are needed, so INTEGER is suitable.

DECLARE DatePurchased : DATE

• This is specifically a calendar date, so DATE is the most appropriate type.
• Using DATE is better than a plain string when the language supports it, because it reflects the meaning of the data more accurately.

DECLARE Format : STRING

• Values such as DVD, Blu-ray, 4K and MP4 are text labels.
• So STRING is acceptable here.
• In the next part of the question, this is also the field most likely to be improved further using an enumerated type.

DECLARE RunningTime : INTEGER

• Running time is given in minutes.
• Minutes are counted as whole numbers, so INTEGER is appropriate.

ENDTYPE

• This closes the composite type definition.

That gives a complete declaration of a structured type that can hold all the required details for one video.

Key Takeaways

• A composite user-defined type groups related fields into one structure.
• Each field should use the data type that best matches the data stored.
• Textual data usually uses STRING; whole-number quantities use INTEGER; dates use DATE.
• In CIE pseudocode, a user-defined type is written using TYPE ... ENDTYPE.

Common Mistakes

• Using CHAR instead of STRING for fields like title or identity code. CHAR stores only one character.
• Declaring year released or running time as STRING instead of INTEGER.
• Forgetting ENDTYPE, which makes the type definition incomplete.
• Writing a variable declaration instead of a type definition.
• Treating the identity code as an INTEGER, even though it may contain letters.

Things to Be Careful About

• Match the required name VideoLibrary exactly.
• Make sure all six fields are included.
• Use pseudocode declaration format consistently: DECLARE FieldName : TYPE.
• Remember that an identity code may look numeric but is usually better stored as text if it is an identifier rather than a value to calculate with.
• Do not add unnecessary program statements such as INPUT, OUTPUT or loops, because the question only asks for the type declaration.

Background Concept

An enumerated data type is a user-defined type that lists a fixed set of allowed values. Instead of allowing any text or number, it restricts the data to one value from that predefined list.

For example, if a field can only be one of a few known options, an enumerated type is useful because:

• only valid values are allowed
• the data can often be stored more efficiently internally
• the meaning of the data is clearer

An enumerated type is best when the possible values are limited and known in advance.

Understanding the Question

The question asks for one field from VideoLibrary that could be stored efficiently as an enumerated type, and it asks for a reason.

So you need to:

1. choose a field from the structure
2. decide whether it has a small fixed set of possible values
3. explain why that makes an enumerated type suitable

The field that stands out most clearly is Format, because examples are already given: DVD, Blu-ray, 4K, MP4.

Approach

Look through the fields and ask: which one has a limited set of valid choices?

• identity code: no, this could be many different combinations
• title: no, almost unlimited possibilities
• year released: no, many possible years
• date purchased: no, many possible dates
• format: yes, usually one of a fixed list
• running time: no, many possible numbers

So Format is the best answer.

Then explain the reason: enumerated types are efficient and suitable when there is a small, predefined set of values.

Step-by-Step Reasoning

The field Format can take values such as:

• DVD
• Blu-ray
• 4K
• MP4

These are not arbitrary text entries chosen freely by the user. They come from a known set of allowed categories.

That means Format fits an enumerated type well. Instead of storing any possible string, the program can define a fixed list of legal values. This has two advantages relevant to the question:

• it is efficient, because the values can be represented internally in a compact way
• it improves validity, because only one of the listed formats can be chosen

A short exam answer only needs one reason, and the safest reason is that the field has a limited predefined set of possible values.

Key Takeaways

• Use an enumerated type when a field can only take one value from a fixed list.
• Format is a strong example because the possible values are known in advance.
• Enumerated types help with both efficiency and validation.

Common Mistakes

• Choosing Title or IdentityCode as an enumerated type. These do not come from a small fixed set.
• Giving the field name but no reason.
• Saying only "because it is text". Being text does not make something suitable for an enumerated type.
• Confusing an enumerated type with a general STRING field.

Things to Be Careful About

• The question asks for one field, so do not list several unless needed.
• Your reason should mention the limited predefined set of values.
• If you mention efficiency, make sure it is linked to the fixed list of options.
• Keep the answer focused on suitability for an enumerated type, not just a description of the field.

Background Concept

In this floating-point system, the number is stored as:

• an 8-bit mantissa
• an 8-bit exponent
• both in two's complement

For Cambridge binary floating-point questions, the mantissa is treated as a signed fractional value with the binary point immediately after the sign bit. That means:

• positive normalised mantissas begin 01
• negative normalised mantissas begin 10

Normalisation matters because it ensures the mantissa uses the available bits efficiently and gives a unique standard form.

In two's complement, the largest positive 8-bit integer pattern is 01111111, which is 127 in denary. For a mantissa, that same bit pattern represents 0.1111111 because the binary point is after the sign bit.

Understanding the Question

The question asks for the largest positive normalised number this system can store.

So we need the combination of:

• the largest possible positive normalised mantissa
• the largest possible positive exponent

Then we must give both:

• the binary floating-point representation
• the denary value, written using powers of 2

The key clue is the word normalised. That means we cannot just choose any positive mantissa; it must start with 01.

Approach

To make the stored value as large as possible:

1. Use the largest positive normalised mantissa.
2. Use the largest positive exponent.
3. Interpret the mantissa as a binary fraction.
4. Multiply that fraction by 2^exponent.
5. Rewrite the result as a sum of powers of 2.

Step-by-Step Reasoning

First, choose the largest positive normalised mantissa.

A positive normalised mantissa must begin 01. To make it as large as possible, every remaining bit should be 1:

01111111

With the binary point after the sign bit, this means:

0.1111111

Next, choose the largest positive exponent that can be stored in 8-bit two's complement:

01111111 = 127

So the largest stored value is:

0.1111111 × 2^127

Now expand 0.1111111 as powers of 2:

0.1111111 = 2^-1 + 2^-2 + 2^-3 + 2^-4 + 2^-5 + 2^-6 + 2^-7

Multiplying by 2^127 gives:

• 2^-1 × 2^127 = 2^126
• 2^-2 × 2^127 = 2^125
• 2^-3 × 2^127 = 2^124
• 2^-4 × 2^127 = 2^123
• 2^-5 × 2^127 = 2^122
• 2^-6 × 2^127 = 2^121
• 2^-7 × 2^127 = 2^120

So the denary value is:

2^126 + 2^125 + 2^124 + 2^123 + 2^122 + 2^121 + 2^120

Key Takeaways

• In this syllabus, a normalised positive two's complement mantissa starts 01.
• The largest positive 8-bit two's complement exponent is 01111111 = 127.
• To convert a floating-point value to denary, interpret the mantissa correctly as a fraction, then apply the exponent.

Common Mistakes

• Using mantissa 11111111 for the largest value. This is wrong because that is negative in two's complement.
• Forgetting normalisation and choosing a mantissa that does not start 01.
• Treating the mantissa as an 8-bit integer instead of a fractional value.
• Giving only 2^127 as the denary value. That ignores the actual fractional mantissa 0.1111111.

Things to Be Careful About

• The mantissa and exponent are both in two's complement, but they are interpreted differently: the mantissa is fractional, the exponent is an integer power.
• The binary point is immediately after the sign bit for the mantissa.
• For positive normalised values, the first two bits must be 01, not just any pattern beginning with 0.
• The question asks for the denary value in terms of powers of 2, so a powers-of-2 expression is the safest final form.

Background Concept

A binary floating-point number is stored as:

mantissa × 2^exponent

In this question:

• the mantissa has 8 bits
• the exponent has 8 bits
• both use two's complement

The mantissa is a signed fractional value, with the binary point immediately after the sign bit. A normalised mantissa must begin:

• 01 for positive values
• 10 for negative values

That rule makes sure the value is stored in a standard form and uses as much precision as possible.

For negative numbers, you do not just put a minus sign in front of the bit pattern. You must store the mantissa itself in two's complement.

Understanding the Question

We must store -3.59375 in this floating-point system.

That means we need to:

1. convert 3.59375 into binary
2. write it in normalised form
3. make the mantissa negative using two's complement
4. store the exponent in 8-bit two's complement

The question also says show your working, so the conversion and normalisation steps matter, not just the final bit patterns.

Approach

The most reliable route is:

1. Split the denary number into integer part and fractional part.
2. Convert each part to binary.
3. Combine them.
4. Shift the binary point until the mantissa is normalised.
5. Count the shift to get the exponent.
6. Write the mantissa in 8 bits.
7. Because the number is negative, convert that mantissa to its two's complement form.
8. Write the exponent as an 8-bit two's complement integer.

Step-by-Step Reasoning

Start with the positive magnitude 3.59375.

1. Convert the integer part

3 in binary is 11.

2. Convert the fractional part

0.59375 can be written as:

• 0.5 = 2^-1
• 0.0625 = 2^-4
• 0.03125 = 2^-5

So:

0.59375 = .10011 in binary.

Therefore:

3.59375 = 11.10011

So:

-3.59375 = -11.10011

3. Normalise the number

We want the mantissa to be a signed fraction. Move the binary point left two places:

11.10011 = 0.1110011 × 2^2

So:

-11.10011 = -0.1110011 × 2^2

The exponent is therefore 2.

4. Write the positive mantissa in 8 bits

The positive mantissa 0.1110011 fits exactly into 8 bits including the sign bit:

01110011

This is positive because the sign bit is 0.

5. Convert the mantissa to negative using two's complement

To store -0.1110011, take the two's complement of 01110011:

Invert the bits:

10001100

Add 1:

10001101

So the negative mantissa is:

10001101

This is also correctly normalised for a negative number because it begins 10.

6. Store the exponent

The exponent is +2, so in 8-bit two's complement that is:

00000010

7. Final representation

• Mantissa: 10001101
• Exponent: 00000010

Key Takeaways

• Convert the denary number to binary first before thinking about the bit boxes.
• Normalisation means shifting the binary point so the mantissa is in standard signed fractional form.
• In this format, a negative mantissa must be stored using two's complement, not by attaching a minus sign.
• Always check that the final negative normalised mantissa begins 10.

Common Mistakes

• Writing the mantissa as 11100110 or another sign-magnitude style pattern. The mantissa must be in two's complement.
• Forgetting to normalise before encoding the mantissa and exponent.
• Using the wrong exponent because the binary point was shifted the wrong number of places.
• Converting 3.59375 incorrectly, especially the fractional part .59375.
• Giving exponent 00000011 because of miscounting the shift.

Things to Be Careful About

• The exponent is positive here, so it stays as ordinary 8-bit two's complement 00000010.
• The mantissa is 8 bits total, not 8 bits after the sign bit.
• When taking two's complement, invert all bits and add 1; do not stop after inversion.
• After conversion, make sure the mantissa is still normalised. For a negative value, the first two bits should be 10.
• Do not lose trailing precision bits unnecessarily if the value already fits exactly, as it does here.

Background Concept

A sum-of-products expression is formed by listing every input combination that makes the output equal to 1.

• Each row with output 1 becomes one product term.
• In a product term, a variable is written uncomplemented if its value is 1 in that row.
• A variable is complemented if its value is 0 in that row.
• All these product terms are then added together with OR.

For example, if a row is A = 0, B = 1, C = 1, D = 0, the matching product term is A'.B.C.D'.

This gives the canonical sum-of-products form, because every term contains all input variables.

Understanding the Question

You are given a complete truth table for inputs A, B, C and D, and output Z. Part (a) asks for the Boolean expression directly from that table as a sum-of-products.

So the task is not to simplify yet. You simply need to:

1. Find every row where Z = 1.
2. Turn each of those rows into a product term.
3. Join the terms with + (OR).

Approach

Scan the truth table row by row and only keep the rows where the output is 1. For each of those rows:

• write A or A' depending on whether A is 1 or 0
• do the same for B, C and D
• multiply the literals together to make one minterm

Then combine all the minterms with OR.

Step-by-Step Reasoning

The rows where Z = 1 are:

• A=0, B=0, C=1, D=0
• A=0, B=0, C=1, D=1
• A=0, B=1, C=0, D=0
• A=1, B=0, C=1, D=0
• A=1, B=0, C=1, D=1
• A=1, B=1, C=0, D=0

Now convert each row.

1. Row 0 0 1 0

   • A is 0, so use A'
   • B is 0, so use B'
   • C is 1, so use C
   • D is 0, so use D'
   • term: A'.B'.C.D'

2. Row 0 0 1 1

   • term: A'.B'.C.D

3. Row 0 1 0 0

   • term: A'.B.C'.D'

4. Row 1 0 1 0

   • term: A.B'.C.D'

5. Row 1 0 1 1

   • term: A.B'.C.D

6. Row 1 1 0 0

   • term: A.B.C'.D'

Finally OR them together:

Z = A'.B'.C.D' + A'.B'.C.D + A'.B.C'.D' + A.B'.C.D' + A.B'.C.D + A.B.C'.D'

That is the required sum-of-products directly from the truth table.

Key Takeaways

• Canonical sum-of-products uses one product term for every row where the output is 1.
• A 0 in the truth table gives a complemented variable.
• A 1 in the truth table gives an uncomplemented variable.
• In canonical SOP, every term contains every input variable.

Common Mistakes

• Using rows where Z = 0 instead of rows where Z = 1.
• Forgetting to include all four variables in each product term.
• Complementing the wrong literals, for example writing A instead of A' when A = 0.
• Accidentally simplifying the expression here; part (a) only asks for the sum-of-products from the truth table.

Things to Be Careful About

• Keep the variable order consistent as A, B, C, D.
• Use one term per true row, no more and no less.
• Do not miss repeated patterns: two rows may look similar, but if D changes then the terms are different.
• Make sure the + signs separate product terms and the dots show AND within each term.

Background Concept

The TCP/IP protocol suite is organised into layers. Each layer has a particular job, and together the layers allow data to move from one application on one computer to another application on another computer.

A layered approach is used because it separates responsibilities:

• higher layers deal with application data
• middle layers deal with end-to-end and network delivery
• lower layers deal with the actual local transmission on hardware

For this question, the two relevant layers are:

• Internet layer: responsible for getting packets across one or more networks to the correct destination
• Link layer: responsible for moving data across a single local link or network segment

The Internet layer is concerned with logical addressing and routing. Logical addressing means IP addresses are used so that devices can be identified across many connected networks.

The Link layer is concerned with local delivery. It deals with the way data is packaged for the local network technology and passed across the physical connection to the next device.

Understanding the Question

The question asks for the purpose of each layer, not a full explanation of every protocol inside the layer.

So you need to state what each layer is there to do:

• for the Internet layer, explain that it is about sending packets between networks using addressing and routing
• for the Link layer, explain that it is about sending data over the local network/media to the next device

A common trap is to describe both layers too vaguely as just "sending data". The key distinction is:

• Internet layer = across networks
• Link layer = across one local link/network segment

Approach

A good way to answer is to compare the two layers directly.

1. Identify the scope of each layer.
   • Internet layer: wider network-to-network delivery
   • Link layer: immediate local transmission
2. Name the main mechanism each one uses.
   • Internet layer: IP addressing and routing
   • Link layer: frames, network hardware, local delivery
3. Phrase each as a purpose statement.

That gives a focused answer that matches what examiners want.

Step-by-Step Reasoning

For the Internet layer:

• Data must sometimes travel through many different networks before reaching its destination.
• A system is needed to identify where the data is going in a way that works beyond a single local network.
• This is done using IP addresses, which are logical addresses.
• The Internet layer uses these addresses to help decide how packets should travel.
• Routers work with this layer to move packets from one network to another.
• So the purpose of the Internet layer is to provide addressing and routing between networks.

For the Link layer:

• Once a packet is ready to travel on a particular network segment, it has to be sent using the local network technology.
• The data is prepared for the network hardware and the transmission medium.
• This often involves placing the data into frames suitable for that local network.
• The Link layer handles delivery from one device to the next on the same local network or direct connection.
• So the purpose of the Link layer is local transmission over the network link.

The difference can be thought of like this:

• Internet layer: "Which network should this packet go through next?"
• Link layer: "How do I actually send this frame across this local connection?"

Key Takeaways

• The Internet layer is responsible for logical addressing and routing across networks.
• The Link layer is responsible for local delivery over the physical/local network link.
• In layered protocols, different layers solve different parts of the communication problem.

Common Mistakes

• Saying both layers just transmit data: this is too vague and does not show the difference in purpose.
• Confusing IP addressing with hardware/MAC addressing: IP belongs to the Internet layer; local hardware delivery belongs to the Link layer.
• Describing the Physical layer: TCP/IP is being asked here, so keep the answer to the named TCP/IP layers, not generic OSI descriptions.
• Talking about applications like HTTP or SMTP: those belong to a different layer and do not answer this question.

Things to Be Careful About

• Use the wording between networks for the Internet layer.
• Use the wording local link or local network segment for the Link layer.
• Make sure the two purposes are clearly distinct.
• If you mention frames for the Link layer, that is helpful, but do not replace the main idea of local delivery with only a technical term.

Background Concept

In packet switching, data is broken into packets. Each packet can be sent through the network independently. This means packets do not need a single fixed path for the whole message.

A router is the device that connects networks together and decides where packets should go next. Its job is not simply to pass data on blindly. It examines addressing information and makes a forwarding decision.

Routers mainly work with:

• the packet's destination IP address
• a routing table, which contains information about where to send packets next
• the idea of a next hop, meaning the next router or network on the route

Because packet-switched networks are flexible, different packets from the same message may sometimes follow different paths.

Understanding the Question

The question asks for the function of a router in packet switching.

That means you should explain what a router actually does when a packet arrives:

• receive the packet
• inspect the address information
• decide the route
• send it onward

It is not asking for a general definition of a router only, and it is not asking for a comparison with switches or hubs. The phrase in packet switching is the clue that you should mention routing packets individually and possibly different routes being used.

Approach

The clearest way to answer is to follow a packet through the router.

1. A packet arrives.
2. The router reads the destination address.
3. The router checks its routing information.
4. It decides the best next hop.
5. It forwards the packet.
6. In packet switching, this can happen separately for each packet.

This sequence naturally gives the explanation the examiner wants.

Step-by-Step Reasoning

• First, a packet reaches one of the router's interfaces.
• The router examines the header, especially the destination IP address.
• It compares that destination with entries in its routing table.
• The routing table tells the router which interface or neighbouring router should be used next.
• The router then forwards the packet to that next hop.
• This process repeats at other routers until the packet reaches the destination network.

Why this matters in packet switching:

• Packets are treated individually.
• The router can choose a route based on the network information it has.
• If a route is busy or unavailable, a different route may be used.
• This is one reason packet switching is flexible and robust.

So the router's function is essentially to direct packets between networks by reading their destination addresses and forwarding them along an appropriate route.

Key Takeaways

• A router connects networks and forwards packets between them.
• It makes decisions using the destination IP address and a routing table.
• In packet switching, packets can be routed independently, so different packets may take different paths.

Common Mistakes

• Saying a router just boosts or repeats signals: that describes other networking hardware, not a router's main function.
• Confusing routers with switches: switches mainly deal with local network forwarding, while routers forward between networks using IP addresses.
• Forgetting the routing table: the router does not guess; it uses stored routing information.
• Describing circuit switching instead: in packet switching there is no single permanently reserved path for the whole message.

Things to Be Careful About

• Mention destination IP address, not just "address" if you can be specific.
• Say the router chooses the next hop or best route, not necessarily the complete route all at once.
• Keep the focus on packet switching, where packets may travel separately.
• Do not drift into unrelated protocol details unless they support the routing explanation.

Background Concept

Process scheduling is an operating system function that decides which process should use the CPU next. In a multitasking system, many processes can exist at once, but a single processor core can execute only one instruction stream at a time. Even with multiple cores, there are usually more runnable processes than available cores.

The operating system therefore keeps track of processes in states such as ready, running and waiting, and uses a scheduling algorithm to choose from the ready processes. Scheduling is needed to keep the system efficient, responsive and fair.

Understanding the Question

This part asks for one reason scheduling is necessary in process management. The key idea is not to name a scheduling method, but to explain why the operating system needs scheduling at all.

The clue is the phrase "necessary in process management". That means you should think about what problem exists if the OS does not schedule: multiple processes want to run, but processor time is limited.

Approach

A strong answer needs:

1. the problem: several processes may need the CPU at the same time
2. the consequence: the OS must choose which process runs and for how long

That gives both the reason and the explanation that earns the marks.

Step-by-Step Reasoning

The CPU is a limited resource. If many processes are active, they cannot all run on the same core simultaneously.

So the operating system must:

• decide which ready process gets the CPU next
• decide when that process should stop or be interrupted
• make sure CPU time is distributed sensibly

Without scheduling, one process could keep the CPU for too long, other processes would wait unnecessarily, and overall system performance and responsiveness would suffer.

That is why a valid answer says scheduling is necessary because processes compete for CPU time, and the OS must manage that competition.

Key Takeaways

• Scheduling is about allocating CPU time to processes.
• It is necessary because runnable processes outnumber available processor time.
• Good scheduling improves fairness, efficiency and responsiveness.

Common Mistakes

• Saying only "to make the computer faster". This is too vague and does not explain the scheduling need.
• Talking about memory management instead of CPU allocation. This question is specifically about process scheduling.
• Naming a scheduling method, such as round robin, without explaining why scheduling is needed in general.

Things to Be Careful About

• Focus on processor time, not storage or files.
• Mention that there can be multiple ready processes but limited CPU availability.
• For a "describe one reason" question, one clearly explained reason is better than several brief undeveloped points.

Background Concept

Round robin is a pre-emptive scheduling algorithm used by operating systems. "Pre-emptive" means the operating system can interrupt a running process. In round robin, each process in the ready queue is given a fixed amount of CPU time called a time slice or time quantum.

The scheduler works through the ready queue in order:

• the first process runs for one time slice
• if it finishes, it leaves the queue
• if it does not finish, it is interrupted when the time slice ends
• it is then placed at the back of the queue
• the next ready process gets its turn

This continues repeatedly, forming a cycle or "round robin" pattern.

Understanding the Question

This part has two separate demands:

1. explain the function of round robin scheduling
2. give one benefit of using it

So the answer must say how it works, not just name it, and then add an advantage. The function needs the key operational details: fixed time slice, processes taken in turn, pre-emption, and rejoining the queue if unfinished.

Approach

To answer fully, describe the mechanism first:

• there is a ready queue
• each process gets a turn
• each turn lasts for a fixed time slice
• unfinished processes are moved to the back

Then give a benefit that follows directly from that mechanism. The clearest benefit is fairness: every process gets CPU time regularly, so starvation is avoided.

Step-by-Step Reasoning

Suppose several processes are waiting in the ready queue.

1. The scheduler selects the process at the front of the queue.
2. That process runs for a fixed time quantum.
3. If the process completes before the time quantum ends, it leaves the system or moves to the appropriate finished/waiting state.
4. If it is still not complete when the quantum ends, the OS interrupts it.
5. The process is placed at the back of the ready queue.
6. The next process at the front is then given the CPU.

This repeats again and again.

Why is this useful? Because every ready process gets a turn. That means:

• no single process can keep the CPU forever
• response time is better for interactive users
• starvation is avoided or greatly reduced because each process gets regular access

For this question, one clearly stated benefit is enough. The safest benefit is fairness or prevention of starvation.

Key Takeaways

• Round robin is a pre-emptive scheduling method.
• It uses a fixed time slice for each process.
• Unfinished processes go to the back of the ready queue.
• Its main benefit is fair CPU sharing and good responsiveness.

Common Mistakes

• Saying only "processes take turns" without mentioning the fixed time slice. The time slice is central to round robin.
• Forgetting that an unfinished process is pre-empted and returned to the queue.
• Giving a vague benefit such as "it is better" without explaining why.
• Confusing round robin with first come first served, where a process may keep the CPU until it finishes.

Things to Be Careful About

• Use the idea of a fixed time slice or time quantum explicitly.
• Make clear that the scheduler moves through the ready queue in turn.
• For the benefit, choose something directly caused by the algorithm, such as fairness, no starvation, or improved response time.
• Keep function and benefit separate, because the question labels them separately.

Background Concept

A syntax diagram shows the valid structure of a string. You follow the path from left to right, and each box or choice tells you what kind of symbol is allowed at that position.

In this question:

• upper means one character chosen from the upper diagram.
• lower means one character chosen from the lower diagram.
• digit means one character chosen from the digit diagram.

A passcode is valid only if every character matches the rule at its position.

Understanding the Question

You are given the syntax diagram for passcode.

From the diagram, the passcode has four characters:

1. first character: upper
2. second character: lower or digit
3. third character: lower or digit
4. fourth character: digit

The question asks why JJ90 is not valid. So we compare each character with the rule for its position.

Approach

Read the passcode from left to right and test each character against the syntax diagram:

• character 1 against upper
• character 2 against lower or digit
• character 3 against lower or digit
• character 4 against digit

As soon as one position breaks the rule, the whole passcode is invalid.

Step-by-Step Reasoning

The passcode is JJ90.

• First character = J
  • J is in the upper diagram, so this is valid.
• Second character = J
  • The second position must be lower or digit.
  • J is uppercase, so it is not from the lower set and it is not a digit.
  • Therefore this position is invalid.

Once the second character fails, the whole passcode is not valid. You do not need any further reason.

Key Takeaways

• Follow a syntax diagram one position at a time.
• Each position has its own rule.
• One invalid character at any position makes the whole string invalid.

Common Mistakes

• Saying the first J is invalid. It is actually valid because the first position must be upper.
• Saying the whole passcode is wrong without identifying which rule is broken.
• Forgetting that the second position allows either lower or digit, not upper.

Things to Be Careful About

• Check positions carefully; do not mix up second, third and fourth characters.
• Use the symbol classes exactly as defined by the diagram.
• A character being a letter is not enough; it must be the correct kind of letter for that position.

Background Concept

Backus-Naur Form (BNF) is a way of writing grammar rules textually instead of drawing them as syntax diagrams.

In BNF:

• a non-terminal is written inside angle brackets, such as <upper> or <passcode>
• ::= means “can be defined as”
• | means “or”
• writing symbols next to each other means they occur in sequence

A syntax diagram and a BNF definition describe the same set of valid strings, just in different forms.

Understanding the Question

You are asked to convert parts of the syntax diagrams into BNF.

From the diagrams:

• <upper> can be any one of J, K, L, V, X, Z
• <passcode> starts with <upper>
• then the second character is either <lower> or <digit>
• then the third character is either <lower> or <digit>
• then the fourth character is <digit>

So the main task is to write:

1. one BNF rule for <upper>
2. a BNF rule for <passcode> covering all allowed combinations of the two branches

Approach

For <upper>, list every possible terminal using |.

For <passcode>, the diagram has two independent branch points:

• second character: 2 choices
• third character: 2 choices

That gives $2 \times 2 = 4$ valid patterns. In BNF, the clearest way is to write all four alternatives explicitly.

Step-by-Step Reasoning

First convert the upper diagram.

The diagram shows a choice of six single terminals:

• J
• K
• L
• V
• X
• Z

So:

<upper> ::= J | K | L | V | X | Z

Now convert passcode.

The structure is:

• first: <upper>
• second: <lower> or <digit>
• third: <lower> or <digit>
• fourth: <digit>

List all combinations of the second and third positions:

1. second <lower>, third <lower>
   • <upper><lower><lower><digit>
2. second <lower>, third <digit>
   • <upper><lower><digit><digit>
3. second <digit>, third <lower>
   • <upper><digit><lower><digit>
4. second <digit>, third <digit>
   • <upper><digit><digit><digit>

So the full BNF rule is:

<passcode> ::= <upper><lower><lower><digit>
             | <upper><lower><digit><digit>
             | <upper><digit><lower><digit>
             | <upper><digit><digit><digit>

This matches the original syntax diagram exactly.

Key Takeaways

• A list of branches in a syntax diagram becomes alternatives using | in BNF.
• A route through several boxes becomes a sequence written side by side.
• If a diagram has multiple branch points, you often need to write all valid combinations.

Common Mistakes

• Writing only one or two passcode alternatives instead of all four.
• Using commas or words like “or” instead of the BNF symbol |.
• Forgetting that the last character must always be <digit>.
• Mixing terminal symbols and non-terminals incorrectly, for example writing upper instead of <upper>.

Things to Be Careful About

• Keep angle brackets around non-terminals such as <upper> and <passcode>.
• Do not miss any branch combination.
• Preserve the order of symbols exactly as shown by the diagram.
• Make sure <upper> is the first symbol in every <passcode> alternative.

Background Concept

Syntax diagrams can show three important grammar ideas visually:

• sequence: items placed one after another on the main line
• choice: a branch where one of several paths may be taken
• repetition: a loop that returns to an earlier point so an item can occur again

If the rule says something may occur one or more times, the first occurrence stays on the main path and then a loop allows extra repetitions.

Understanding the Question

The original passcode diagram means:

• first character: upper
• second character: lower or digit
• third character: lower or digit
• final character: digit

The question changes two rules:

1. the third character may also be upper
2. the final character may be repeated one or more times

So you must edit the original diagram, not redesign the whole thing from scratch.

Approach

Keep the parts that do not change:

• first upper
• second character branch between lower and digit

Then apply the two changes:

• at the third-character branch, add a third option: upper
• at the final digit, add a feedback loop from its exit back to its entrance so at least one digit is present and more digits are allowed

Step-by-Step Reasoning

Start with the original structure:

• upper
• choice of lower or digit
• choice of lower or digit
• digit

Change 1: third character may also be upper

The third character was originally a two-way choice:

• lower
• digit

Now it becomes a three-way choice:

• lower
• digit
• upper

So in the second branching section of the syntax diagram, add another parallel path labelled upper.

Change 2: final character may be repeated one or more times

The original final character was a single digit box.

“One or more times” means:

• there must be at least one digit
• after that, more digit characters are allowed

In a syntax diagram, that is shown by leaving one digit on the main path and drawing a loop from the exit of that digit back to its input. Each time the loop is taken, another digit is matched.

So the completed passcode rule becomes, in effect:

• one upper
• then lower or digit
• then lower or digit or upper
• then at least one digit

The completed diagram is:

Key Takeaways

• Add a new allowed symbol in a syntax diagram by adding another branch.
• Show “one or more” with a compulsory first item and a loop for extra copies.
• When modifying a grammar, change only the required parts and keep the rest unchanged.

Common Mistakes

• Adding upper to the wrong character position, such as the second instead of the third.
• Drawing the repetition loop around too much of the diagram instead of just the final digit.
• Showing zero-or-more digits by making the final digit optional. The rule says one or more, so at least one digit must remain compulsory.
• Removing the original lower and digit options from the third position instead of adding upper as an extra choice.

Things to Be Careful About

• The second character is still only lower or digit.
• The third character is the one that changes to lower, digit or upper.
• The repetition applies only to the final digit section.
• The loop must return to the entrance of the final digit box so the extra repeated item is also a digit.

Background Concept

A* and Dijkstra's are graph-search algorithms. A graph is made of nodes joined by edges, and the edges may have costs or weights. In many problems, we want the path from one node to another with the smallest total cost. This might mean the fewest distance units, the least time, or the lowest combined weight.

Dijkstra's algorithm solves the shortest-path problem by repeatedly choosing the unexplored node with the smallest known distance from the start. A* is also used for shortest-path search, but it adds a heuristic estimate of how far a node is from the goal so that the search is guided more directly toward the destination.

Understanding the Question

This part asks for the purpose of both A* and Dijkstra's. Since it is only 1 mark, the examiner is looking for the main shared purpose, not the difference between them. The key idea is shortest-path or least-cost path finding in a graph.

Approach

For a 1-mark "state" question, give one precise sentence that names what both algorithms are used for. Do not spend time describing how they work, because that belongs to a later part.

Step-by-Step Reasoning

The question names two algorithms:

• Dijkstra's
• A*

Although they work differently, they have the same broad purpose:

• they search a weighted graph
• they aim to find a path
• the path found is the one with minimum total cost

So the correct exam-style answer is that they are used to find the shortest or least-cost path between nodes in a graph.

Key Takeaways

• Both A* and Dijkstra's are path-finding algorithms.
• Their shared purpose is shortest-path or least-cost path search in a graph.
• In a 1-mark state question, focus on the central idea only.

Common Mistakes

• Saying only "they search graphs". That is too vague because many algorithms search graphs.
• Saying "they sort data" or "they search arrays". These algorithms are for graphs, not list searching or sorting.
• Describing only one algorithm instead of the shared purpose of both.

Things to Be Careful About

• Include the idea of shortest path, least-cost path, or minimum-cost route.
• Mention that the search is through a graph or between nodes.
• Do not drift into explaining heuristics here; that difference belongs in part (b).

Background Concept

The key difference between A* and Dijkstra's is how they decide which node to examine next.

Dijkstra's algorithm keeps track of the shortest known distance from the start node to every reachable node. At each step, it selects the unexplored node with the smallest current distance from the start. Because of this, it systematically spreads out from the source.

A* also keeps a cost from the start, but it combines this with a heuristic. A heuristic is an estimate of the remaining cost from the current node to the goal. This lets A* prefer nodes that seem likely to lead more directly to the destination.

A common way to describe A* is:

• $g(n)$ = exact cost from the start to node $n$
• $h(n)$ = estimated cost from node $n$ to the goal
• $f(n) = g(n) + h(n)$

Dijkstra's effectively uses only the known cost from the start.

Understanding the Question

This part asks for the difference, not the purpose. So the answer must compare them. The most important distinction is the heuristic used by A*. A second useful contrast is that Dijkstra's explores based only on known distances from the source, while A* is guided toward a specific goal.

Approach

A 2-mark "outline the difference" question usually needs two concise points. The best structure is:

• say what A* uses
• say what Dijkstra's does not use and how it chooses nodes instead

That gives a direct side-by-side comparison.

Step-by-Step Reasoning

Start by asking: how does each algorithm choose the next node?

For Dijkstra's:

• It knows the current best distances from the start node.
• It picks the unexplored node with the smallest known distance.
• It does not try to guess which node is closer to the destination.

For A*:

• It also uses the cost already travelled from the start.
• But it adds a heuristic estimate of the remaining cost to the target.
• This means the search is goal-directed rather than just spreading outward uniformly.

So a strong answer is:

• A* uses a heuristic estimate to guide the search toward the goal.
• Dijkstra's does not use a heuristic and selects nodes only by shortest known distance from the start.

If you want to think of it intuitively, Dijkstra's is more general and methodical, while A* is more focused on reaching one destination efficiently.

Key Takeaways

• A* = shortest-path search with a heuristic.
• Dijkstra's = shortest-path search without a heuristic.
• A* is usually more goal-directed because it estimates how close a node is to the target.

Common Mistakes

• Saying A* is "faster" without explaining why. Speed alone is not the core difference.
• Saying Dijkstra's finds only one path. It can be used to determine shortest paths from the start to other nodes as well.
• Forgetting to mention the heuristic when describing A*.
• Claiming Dijkstra's uses a heuristic too. It does not.

Things to Be Careful About

• Use the word heuristic correctly: it is an estimate, not an exact distance.
• Do not say A* always gives a better answer; the difference is in the method of choosing nodes.
• Keep the comparison precise and paired: what A* uses, what Dijkstra's does not use.

Background Concept

Machine learning is a method where a computer system improves its behaviour by learning from data instead of being given every rule explicitly.

There are two major contrasting ideas here:

• Supervised learning: the training data includes the correct answers, often called labels or target outputs.
• Unsupervised learning: the training data does not include correct answers.

In unsupervised learning, the system must inspect the data and discover structure by itself. Typical outcomes include:

• clustering similar items together
• finding patterns or associations
• identifying groups, trends or anomalies

So the defining feature is that the computer is not told what the right category or output should be.

Understanding the Question

The question asks how unsupervised learning takes place. That means it wants the process, not just a one-line definition. For 3 marks, a complete answer should include:

• the kind of data used
• what the system does with that data
• the kind of result produced

The key clues are the words "unsupervised learning", which strongly suggest no labelled outputs and no teacher telling the system the correct answer.

Approach

A good structure is to explain the process in three stages:

1. start with unlabelled data
2. analyse the data to detect patterns or similarities
3. form groups or relationships without external guidance

That sequence naturally matches a 3-mark explanation.

Step-by-Step Reasoning

First, identify what makes this learning "unsupervised":

• The training data has no labels.
• There is no column saying what the correct class is.
• There is no human trainer marking each example as right or wrong during the learning stage.

Next, consider what the algorithm must do instead:

• It compares items in the data.
• It measures similarity, closeness, or related features.
• It searches for repeated patterns or underlying structure.

Then, think about the output:

• items with similar characteristics may be placed into the same cluster
• unusual items may stand out as anomalies
• relationships between attributes may be discovered

So the learning happens because the machine processes the raw unlabelled data and organises it based on patterns it finds internally, not because it is told the correct output.

A concise exam answer therefore says:

• unlabelled data is provided
• the system finds patterns or similarities itself
• it groups or clusters similar data without being given correct answers

Key Takeaways

• Unsupervised learning does not use labelled target outputs.
• The system discovers patterns, structure, or clusters for itself.
• A strong explanation should describe the data, the analysis, and the result.

Common Mistakes

• Confusing unsupervised learning with supervised learning by mentioning known correct answers.
• Saying the computer is "taught" the right category for each item. That is supervised learning, not unsupervised.
• Giving only the word "clustering" without explaining that it comes from analysing unlabelled data.
• Describing reinforcement learning instead, which involves rewards and penalties.

Things to Be Careful About

• Use "unlabelled data" or "no expected outputs" clearly.
• Make sure the answer explains that the machine finds patterns by itself.
• If you mention clusters, link them to similarity between data items.
• Do not imply a person is correcting the system during training, because that would not be unsupervised learning.

Background Concept

An Abstract Data Type (ADT) is a way of describing a data structure by its behaviour and operations rather than by its implementation details. In other words, an ADT defines what the structure does, not exactly how it is stored in memory.

Common ADTs include:

• stack
• queue
• list / linked list
• tree
• graph
• array

For example, a stack is defined by operations such as push, pop and peek, and its key rule is last in, first out (LIFO). A queue is defined by operations such as enqueue and dequeue, and its rule is first in, first out (FIFO).

Understanding the Question

The question tells you that an array is an ADT and asks you to identify two others. This is not asking for descriptions or operations, just names of two valid ADTs.

Because it is only worth 1 mark, the examiner is simply checking that you know examples of ADTs.

Approach

Use recall. Choose any two standard ADTs from the syllabus. The safest answers are very common ones such as stack and queue.

Step-by-Step Reasoning

The question asks for two other ADTs besides an array.

Valid examples include:

• stack
• queue
• linked list
• tree
• graph

So a full-mark answer can simply name any two of these. For example:

• Stack
• Queue

No explanation is needed because the command word is "Identify".

Key Takeaways

• An ADT describes a data structure in terms of its operations and behaviour.
• You should be able to recognise common ADTs such as stacks, queues, lists and trees.
• Short "identify" questions usually need only the correct term, not a full definition.

Common Mistakes

• Giving an operation instead of an ADT, such as push or dequeue.
• Naming a general programming feature rather than a data type, such as "loop" or "class".
• Repeating "array" even though the question asks for other ADTs.

Things to Be Careful About

• Only give examples that are actually data structures or ADTs.
• Do not waste time writing definitions unless the question asks for them.
• If asked for two, make sure you clearly provide two separate answers.

Background Concept

Insertion sort builds a sorted section of the array from left to right. At each step, it takes the next unsorted value, compares it with earlier values, shifts any larger values one place to the right, and then inserts the saved value into the correct position.

The main idea is:

• treat the first element as already sorted
• take the next value
• move left through the sorted section
• shift larger items right
• insert the value into the gap left behind

For an ascending sort, smaller values must end up nearer the start of the array, so while moving left we keep shifting elements that are greater than the value being inserted.

Understanding the Question

The array DataArray contains integer values and must be sorted into ascending order. The question specifically asks for pseudocode for an insertion sort, not any other sorting algorithm.

Important clues:

• "insertion sort" tells you exactly which algorithm to write
• "ascending order" tells you the comparison must move larger values rightwards
• the identifiers Index, Position, DataArray and Value must be used exactly as given
• the first line FOR Index ← 2 TO 1000 is already provided, so the algorithm should continue from there
• the question says declarations are not needed, so do not add DECLARE statements

Approach

Follow the standard insertion sort pattern:

1. Start from the second element, because the first element on its own is already sorted.
2. Save the current array value in Value.
3. Set Position to the current index.
4. While the element before Position is larger than Value, shift that element right.
5. Decrease Position each time you shift.
6. When the correct place is found, insert Value.
7. Repeat for every element from position 2 to 1000.

This matches the definition of insertion sort exactly.

Step-by-Step Reasoning

The given first line is:

FOR Index ← 2 TO 1000

Why start at 2? Because insertion sort assumes the first element is already in a sorted section of length 1.

Next:

Value ← DataArray[Index]

This saves the current element before any shifting happens. If you do not save it, it may be overwritten.

Then:

Position ← Index

This sets the insertion position to the current element's location. We will move it left if needed.

Now the inner loop:

WHILE Position > 1 AND DataArray[Position - 1] > Value

This condition does two jobs:

• Position > 1 stops the algorithm going beyond the start of the array
• DataArray[Position - 1] > Value checks whether the previous element is too large and therefore needs shifting right

Because the sort is ascending, only larger values should be shifted.

Inside the loop:

DataArray[Position] ← DataArray[Position - 1]

This copies the larger value one place to the right.

Then:

Position ← Position - 1

After shifting, the possible insertion point moves one place left.

When the WHILE loop finishes, one of two things is true:

• the start of the array has been reached, or
• the previous element is no longer larger than Value

So the correct insertion statement is:

DataArray[Position] ← Value

This places the saved value into the gap created by the shifting.

Finally:

NEXT Index

This repeats the process for every remaining element.

The completed algorithm is therefore:

FOR Index ← 2 TO 1000
   Value ← DataArray[Index]
   Position ← Index
   WHILE Position > 1 AND DataArray[Position - 1] > Value
      DataArray[Position] ← DataArray[Position - 1]
      Position ← Position - 1
   ENDWHILE
   DataArray[Position] ← Value
NEXT Index

A common alternative version starts with Position ← Index - 1 and inserts into Position + 1. That is also a valid insertion sort pattern, but here the chosen version fits neatly with the given identifier meaning of "insertion position".

Key Takeaways

• Insertion sort grows a sorted section one item at a time.
• You must save the current value before shifting elements.
• For ascending order, shift elements while they are greater than the saved value.
• The inner loop needs a boundary check so the array is not accessed before its first element.

Common Mistakes

• Writing bubble sort instead of insertion sort.
• Forgetting to store the current element in Value before shifting.
• Using the wrong comparison, such as < instead of > for an ascending insertion sort.
• Forgetting to decrease Position, causing an infinite loop.
• Forgetting the final insertion DataArray[Position] ← Value.
• Accessing DataArray[0] by not checking Position > 1 first.

Things to Be Careful About

• Use the exact identifiers from the table: Index, Position, DataArray, Value.
• Use CIE pseudocode conventions: FOR, WHILE, ENDWHILE, NEXT, and the assignment arrow ←.
• The array here is treated as 1-indexed, so the first valid element is position 1.
• The outer loop starts at 2 because the first item alone is already sorted.
• Make sure the sort is ascending, so larger previous values move right.

Background Concept

The performance of a sorting routine means how efficiently it runs, usually measured by factors such as execution time, number of comparisons, and number of data moves or swaps.

A sorting algorithm's performance is not determined only by the algorithm itself. It is also affected by the data it is sorting. Two important data-related factors are:

• the size of the data set
• the initial arrangement of the values

For example, insertion sort is much faster when the array is already nearly sorted than when it is in reverse order, because fewer elements need to be shifted.

Understanding the Question

The question asks for two ways in which the performance of a sort routine is affected by the data to be sorted. So it is not asking you to name sorting algorithms or define Big O notation. It wants features of the input data that change how long the sort takes or how much work it must do.

The most standard answers are:

1. how many items are being sorted
2. how ordered or unordered the items already are

Approach

Choose two clear characteristics of the input data and explain how each changes the amount of work done by the sort.

A good exam answer should link each factor to performance by saying something like:

• more comparisons
• more swaps or shifts
• less time
• more time

That explanation is what turns a vague point into a mark-scoring description.

Step-by-Step Reasoning

First factor: number of items.

If the list contains more values, the sort routine must process more elements. In most sorts this means:

• more loop iterations
• more comparisons between values
• more swaps or shifts of data
• longer execution time

So larger input size reduces performance.

Second factor: initial order of the data.

Some sorts, especially insertion sort and bubble sort, are affected strongly by how sorted the data already is.

If the data is already sorted or nearly sorted:

• fewer comparisons may be needed
• fewer swaps or shifts are needed
• the algorithm finishes more quickly

If the data is in reverse order or highly unsorted:

• many more comparisons are needed
• many more swaps or shifts are needed
• the sort takes longer

That is why the "state" of the input data changes the routine's performance even when the same algorithm is used.

Key Takeaways

• Sorting performance depends on both the algorithm and the input data.
• More items usually means more work and longer run time.
• Data that is already nearly sorted can make some algorithms much faster.
• Strong answers explain why performance changes, not just what factor changes.

Common Mistakes

• Naming a sort method, such as "bubble sort", instead of describing a property of the data.
• Saying only "size" or "order" without explaining the effect on comparisons, swaps or time.
• Giving two answers that are really the same point written differently.
• Talking about storage space or memory when the question is clearly about performance of the sort routine.

Things to Be Careful About

• The question asks for ways the data affects performance, so focus on input characteristics.
• Make each point distinct: one about quantity of data, one about arrangement of data is a safe choice.
• Link each characteristic to a direct consequence such as more comparisons, more shifts, or longer time.
• Avoid vague statements like "it is less efficient" without saying why.