Computer Science 9618/32 — May/June 2024

Background Concept

A floating-point number stores a value in two parts:

• the mantissa (sometimes called the significand), which holds the significant digits of the number
• the exponent, which shows how far the binary point is shifted

This is similar to scientific notation. In binary, a number is stored in the form:

The mantissa controls how accurately the number itself is stored. More mantissa bits means more binary digits of the value can be kept, so the stored number is closer to the real value.

The exponent controls how large or small the overall number can be. More exponent bits means more possible exponent values, so a wider range of magnitudes can be represented.

With a fixed total number of bits, increasing one part must decrease the other. So there is always a trade-off between precision and range.

Understanding the Question

The question is not asking for a calculation. It is asking what happens if, in a floating-point format with the same overall size, you change how many bits go to the mantissa and how many go to the exponent.

So you must describe both directions of the trade-off:

• more mantissa bits
  n- more exponent bits

For 2 marks, the examiner will expect both effects, not just one.

Approach

Think separately about the job of each field:

1. What does the mantissa affect? → precision.
2. What does the exponent affect? → range.
3. Because the total number of bits is fixed, giving more bits to one field means taking bits away from the other.

That gives the two required statements.

Step-by-Step Reasoning

If more bits are allocated to the mantissa:

• the mantissa can store more binary digits of the value
• this means the number can be represented more accurately
• so precision increases
• but fewer bits are left for the exponent
• so there are fewer possible exponent values
• therefore the range decreases

If more bits are allocated to the exponent:

• more exponent values can be stored
• so much larger and much smaller numbers can be represented
• therefore the range increases
• but fewer bits are left for the mantissa
• so fewer significant binary digits are stored
• therefore precision decreases

That is exactly the trade-off the question wants.

Key Takeaways

• The mantissa mainly affects precision.
• The exponent mainly affects range.
• In a fixed-size floating-point format, improving one usually worsens the other.

Common Mistakes

• Saying only that "more bits is better" without stating what improves.
• Mixing up the roles of mantissa and exponent.
• Forgetting that the total number of bits is fixed, so one field only grows by shrinking the other.
• Using the word "accuracy" loosely without linking it clearly to the mantissa.

Things to Be Careful About

• Use the term precision for the mantissa and range for the exponent.
• Make sure both halves of the trade-off are given, because one statement alone would not usually gain full marks.
• Do not describe normalisation here; this part is about bit allocation, not the normalising process itself.

Background Concept

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

• a 12-bit mantissa
• a 4-bit exponent
• two's complement for both parts

For Cambridge floating-point questions, the mantissa is treated as a signed binary fraction, so the binary point is immediately after the sign bit. A positive normalised mantissa therefore begins 01..., while a negative normalised mantissa begins 10....

A floating-point value is stored in the form:

To normalise the mantissa, the value must be shifted so that it uses the largest possible place value without wasting leading bits. In two's complement floating-point, this means the first two bits of the mantissa should be different:

• positive normalised numbers start 01
• negative normalised numbers start 10

The exponent records how many places the binary point was shifted.

Understanding the Question

The question gives a real number, $+54.8125$, and asks for its normalised floating-point representation in a very specific format.

You are told:

• 12 bits must be used for the mantissa
• 4 bits must be used for the exponent
• both are in two's complement

So you must:

1. convert $54.8125$ to binary
2. normalise it into mantissa and exponent form
3. make the mantissa exactly 12 bits long
4. write the exponent as a 4-bit two's complement integer

The figure with the empty bit boxes is just where the final mantissa and exponent bits would be written.

Approach

The safest method is:

1. Convert the integer part and fractional part separately to binary.
2. Combine them into one binary number.
3. Shift the binary point left until the mantissa is in normalised form beginning 01.
4. Count the shift amount to get the exponent.
5. Pad the mantissa with trailing zeros if needed so it fills all 12 bits.
6. Convert the exponent to 4-bit two's complement.

Because the value is positive, the mantissa sign bit will be 0.

Step-by-Step Reasoning

First convert the integer part:

Now convert the fractional part $0.8125$:

So the full binary value is:

Now normalise it. We want the binary point immediately after the sign bit in the mantissa, so for a positive number the mantissa should look like 0.1....

Move the binary point 6 places left:

That gives the correct normalised value. Since the mantissa must have 12 bits total, and one of those bits is the sign bit, we need 11 bits after the binary point.

At the moment we have:

• sign bit 0
• fractional bits 1101101101

That is only 10 fractional bits, so add one trailing zero:

Now write the mantissa as 12 stored bits, without showing the binary point explicitly:

• sign bit: 0
• remaining 11 bits: 11011011010

So the mantissa is:

011011011010

Next the exponent is $+6$. In 4-bit two's complement, positive values are written as ordinary binary with leading zero:

So the exponent is:

0110

Therefore the final floating-point representation is:

• Mantissa: 011011011010
• Exponent: 0110

Key Takeaways

• Convert the denary number to binary before trying to normalise it.
• In two's complement floating-point, a positive normalised mantissa starts 01.
• The exponent is the number of places the binary point is shifted.
• Always fit the answer exactly into the stated bit lengths by padding if necessary.

Common Mistakes

• Writing the unnormalised binary number directly into the mantissa boxes.
• Using the wrong normalisation rule, for example trying to make the mantissa start 1. instead of using the two's complement fractional format.
• Forgetting that the mantissa must contain exactly 12 bits.
• Using the wrong exponent because the number of shifts was miscounted.
• Converting the exponent incorrectly from denary to two's complement.

Things to Be Careful About

• The mantissa and exponent are separate values, each with its own bit width.
• The binary point in the mantissa is not stored as a bit; it is assumed to be after the sign bit.
• Positive two's complement exponents still need the correct number of bits, so 6 must be 0110, not just 110.
• Add trailing zeros to fill the mantissa if the binary fraction ends early; do not change the value by shifting again.
• Check normalisation visually: for a positive value, the stored mantissa bits should begin 01.

Background Concept

A protocol is an agreed set of rules used when computers communicate. These rules cover things such as how data is formatted, when it is sent, how errors are handled and how the receiver knows what the data means.

Protocols are essential because two devices cannot communicate reliably if each one uses different rules. In the same way that human conversation depends on a shared language, computer communication depends on shared protocols.

At a higher level, different protocols may handle different jobs, but the basic reason they are needed is always the same: they make communication predictable and understandable.

Understanding the Question

This question asks why protocols are essential, not for examples of protocols. So the answer should focus on the reason protocols are needed.

For 2 marks, the safest approach is to give two clear points:

• protocols are rules or standards for communication
• they make sure both computers can exchange and understand data correctly

Approach

Start with the definition of a protocol, then connect that definition to successful communication. That gives the full idea:

1. a protocol provides agreed rules
2. those rules allow sender and receiver to work in the same way

That is enough for a concise full-mark answer.

Step-by-Step Reasoning

The first key idea is that a protocol is not a physical device and not the data itself. It is the rule set followed during communication.

The second key idea is why that matters. If one computer sends data in one format or sequence and the other expects something different, the message may be corrupted, rejected or misunderstood.

So a good answer states:

• protocols define the rules for communication
• these rules let both computers send, receive and interpret data consistently

That directly addresses both the meaning and the purpose.

Key Takeaways

• A protocol is a set of communication rules.
• Protocols are needed so that different devices use the same standards.
• Without protocols, data exchange would not be reliable or understandable.

Common Mistakes

• Naming examples only, such as HTTP or SMTP, without explaining why protocols are needed.
• Saying protocols "connect computers" without mentioning rules or standards.
• Giving very vague statements like "they help communication" with no explanation of how.

Things to Be Careful About

• The question says "why protocols are essential", so explain purpose, not just give names.
• Include the idea of both ends of the communication following the same rules.
• Keep the answer general; it is not asking about one specific protocol.

Background Concept

Different Internet services use different application-layer protocols. Email uses specific protocols depending on whether the message is being sent or retrieved.

SMTP stands for Simple Mail Transfer Protocol. It is used to send email.

POP3 stands for Post Office Protocol version 3. It is used to receive email, usually by downloading messages from the mail server.

IMAP is another valid receiving protocol. It allows email to be accessed and managed while it remains stored on the server.

Understanding the Question

The question gives one line for sending and one line for receiving. So you must supply:

• one protocol for sending email
• one protocol for receiving email

The standard answer for sending is SMTP. For receiving, POP3 is acceptable, and IMAP is also commonly accepted.

Approach

Match each task to its protocol:

1. sending email -> SMTP
2. receiving email -> POP3 or IMAP

Then write just the names, because the question says "State the names".

Step-by-Step Reasoning

To send an email from a client to a mail server, or between mail servers, the protocol used is SMTP.

To receive email from a mail server to a client, one common protocol is POP3.

So the completed response is:

• Sending: SMTP
• Receiving: POP3

If a candidate wrote IMAP instead of POP3 for receiving, that would also usually be correct because IMAP is also a receiving protocol.

Key Takeaways

• SMTP is for sending email.
• POP3 and IMAP are for receiving email.
• Application-layer protocols are associated with specific tasks.

Common Mistakes

• Writing POP3 or IMAP for sending.
• Writing SMTP for receiving.
• Giving a non-email protocol such as HTTP or FTP.

Things to Be Careful About

• The question asks for protocol names, so abbreviations like SMTP and POP3 are fine.
• Make sure the sending and receiving protocols are not swapped.
• If only one receiving protocol is asked for, give just one, not a list.

Background Concept

BitTorrent is an application-layer protocol used for file distribution. A protocol is a rule set, so BitTorrent defines how devices request, send and receive file data.

The phrase peer-to-peer means that the computers involved are treated as equals, called peers. Instead of one central server doing all the sending, many computers in the network can share data directly with each other.

In peer-to-peer file sharing, a file is often divided into smaller pieces. A computer can download different pieces from different peers and can also upload pieces it already has to others.

Understanding the Question

The question is asking you to explain the meaning of the whole phrase, not just define BitTorrent alone.

So you should break the phrase into its important parts:

• BitTorrent protocol
• peer-to-peer
• file sharing

A full answer should explain all three ideas clearly.

Approach

Take the phrase section by section:

1. explain that BitTorrent is a protocol, meaning a set of communication rules
2. explain that peer-to-peer means direct sharing between computers rather than one central server
3. explain that file sharing means the file data is uploaded and downloaded between those peers

This produces three distinct marking points.

Step-by-Step Reasoning

First, BitTorrent protocol means there is an agreed method for communication. Computers using BitTorrent follow the same rules so they can exchange file data properly.

Second, peer-to-peer tells you about the structure of the communication. The computers are peers, so they connect to one another directly. There is not just one machine acting as the only source of the file.

Third, file sharing explains what is being done. The peers exchange file data. In practice, this often means each peer downloads parts of the file from others and uploads parts it already has.

That is why a strong answer says:

• BitTorrent is a set of rules for file transfer
• computers share directly with other computers
• each computer can both send and receive parts of the file

Key Takeaways

• BitTorrent is a protocol, not just a program name.
• Peer-to-peer means direct communication between equal devices.
• In peer-to-peer file sharing, each peer may act as both downloader and uploader.

Common Mistakes

• Saying only that BitTorrent is "used to download files" without explaining protocol or peer-to-peer.
• Describing peer-to-peer as communication through a central server.
• Forgetting that peers can both send and receive data.

Things to Be Careful About

• Do not confuse peer-to-peer with client-server. They are different models.
• Mention the idea of rules or standards when explaining protocol.
• For full marks, explain the meaning of the full phrase, not just one word from it.

Background Concept

A data type defines what kind of value can be stored and what operations are valid on it. In this topic, data types are often grouped into two broad categories:

• Non-composite data types: hold one single value.
• Composite data types: are built from multiple components, fields, or elements.

A non-composite type is sometimes called a simple type. It is treated as one whole item, not as a structure made from smaller named parts. Examples include INTEGER, REAL, CHAR, and BOOLEAN.

By contrast, a composite type such as an array, record, or class contains multiple pieces of data inside it.

Understanding the Question

This question asks for two things:

1. an explanation of what the term non-composite data type means
2. one example of such a type

So the answer needs both a definition and an example. A definition on its own would not be enough, and just naming a type would also not be enough.

Approach

The quickest way to answer is to focus on the key distinction:

• non-composite = one value only
• composite = made from several parts

Then give a standard example that examiners will accept, such as INTEGER or BOOLEAN.

Step-by-Step Reasoning

To explain the term clearly, you should say that the type:

• stores a single item of data
• is not built from smaller component parts

That directly addresses the word non-composite. "Composite" means formed from parts, so "non-composite" means not formed from parts.

A good example is INTEGER because:

• it stores one whole number value at a time
• it is not split into fields or elements

So INTEGER is a clear example of a non-composite type.

Other examples that are commonly acceptable are REAL, BOOLEAN, or CHAR, provided they are written as data types rather than as values.

Key Takeaways

• A non-composite data type stores just one value.
• It is not made from smaller component items.
• Typical examples are INTEGER, REAL, BOOLEAN, and CHAR.
• Composite types are things like arrays and records, which contain multiple parts.

Common Mistakes

• Giving a value instead of a type: writing 7 or TRUE instead of INTEGER or BOOLEAN is not as strong, because the question asks for a data type.
• Describing storage size instead of structure: non-composite is about whether the type has components, not about how many bits it uses.
• Using a composite example: an array or record would be wrong because those are made from multiple elements or fields.
• Only saying "simple" without explaining why: the mark comes from explaining that it is a single value and not made of parts.

Things to Be Careful About

• Make sure your example is a type name, not just an example value.
• Include the idea of single value or not split into components in the definition.
• Do not confuse non-composite with primitive if your course materials use different terminology; in this syllabus, the important distinction is simple versus made of components.

Background Concept

A set data type stores a collection of values where:

• each item is unique
• the order of items is not important

This makes a set different from a list or array, where position matters. In a set, {2, 4, 6} and {6, 4, 2} represent the same group of values.

When declaring a set in pseudocode, you normally need to show:

• the identifier name
• that the structure is a SET
• the type of values stored in it, such as INTEGER

If the question also gives the values to be stored, then you initialise the set with those members.

Understanding the Question

The question asks for pseudocode statements to declare EvenNumbers so that it can hold this exact set:

• 2, 4, 6, 8, 10, 12

So there are really two tasks:

1. declare EvenNumbers as a set
2. assign the required even integer values to it

Because all the values are whole numbers, the element type should be INTEGER.

Approach

Use normal pseudocode style:

• first declare the identifier and its type
• then initialise it using set notation

The natural declaration is SET OF INTEGER because each member of the set is an integer.

Then use braces to list the members of the set exactly as given.

Step-by-Step Reasoning

First, decide what kind of structure is needed.

The question explicitly says it is a set, so the declaration must show that. The items are 2, 4, 6, 8, 10, and 12, all of which are integers, so the declaration should use INTEGER as the element type.

That gives:

DECLARE EvenNumbers : SET OF INTEGER

Next, place the required members into the set. Since the question gives the full set, initialise it directly:

EvenNumbers ← {2, 4, 6, 8, 10, 12}

This is suitable because:

• every member is listed
• all members are integers
• there are no duplicates
• the structure is clearly shown as a set

Putting both statements together gives the complete answer.

Key Takeaways

• A set stores unique values with no meaningful order.
• In pseudocode, you should declare both the structure and the element type.
• For numeric members like these, SET OF INTEGER is appropriate.
• If the members are already given, initialise the set directly.

Common Mistakes

• Using an array instead of a set: the question specifically asks for a set, so ARRAY would be wrong.
• Forgetting the element type: DECLARE EvenNumbers : SET is incomplete because it does not say what kind of values the set stores.
• Using duplicate values: sets should not contain repeated members.
• Treating order as important: the order shown is fine to copy, but a set is not about position.
• Writing real program code instead of pseudocode: this is a pseudocode task, so the style should stay language-neutral.

Things to Be Careful About

• Keep the identifier exactly as given: EvenNumbers.
• Use INTEGER, not REAL, because all given values are whole numbers.
• Use the assignment arrow ←, not =.
• Make sure all six values are included: 2, 4, 6, 8, 10, 12.
• Do not add extra values such as 0 or omit 12.

Background Concept

Reverse Polish Notation (RPN), also called postfix notation, writes each operator after its operands. In ordinary infix notation, we write something like 7 - 2; in RPN, that becomes 7 2 -.

The benefit of RPN is that brackets are usually not needed, because the order of evaluation is built into the position of the operators. When converting from infix to RPN, the main things to preserve are:

• the grouping caused by brackets
• operator precedence
• left-to-right order when operators have the same precedence

For example, A + B * C becomes A B C * + because multiplication must happen before addition.

Understanding the Question

You are given the infix expression:

(7 - 2 + 8) / (9 - 5)

and asked to rewrite it in RPN.

The brackets are important here. They show that the numerator and denominator must each be evaluated first, and only then is the division carried out. So the task is really:

1. convert the left bracketed part into RPN
2. convert the right bracketed part into RPN
3. place the / at the end, because division happens after both sides are ready

Approach

Treat each bracketed part as its own small infix expression.

• For (7 - 2 + 8), subtraction and addition have equal precedence, so we follow the left-to-right order shown by the infix expression.
• For (9 - 5), it is just a single subtraction.
• Once both subexpressions are in postfix form, append the division operator to the end.

That gives the full RPN expression.

Step-by-Step Reasoning

Start with the numerator:

(7 - 2 + 8)

Because - and + have the same precedence, evaluate from left to right:

1. 7 - 2 becomes 7 2 -
2. Then add 8, so append 8 +

So the numerator becomes:

7 2 - 8 +

Now the denominator:

(9 - 5)

This becomes simply:

9 5 -

Now combine the two parts. In RPN, an operator comes after its two operands. The two operands for division are:

• 7 2 - 8 +
• 9 5 -

So place / after them:

7 2 - 8 + 9 5 - /

That is the complete postfix form.

Key Takeaways

• In RPN, operators come after operands.
• Convert each bracketed subexpression separately if that makes the structure clearer.
• When two operators have equal precedence, keep the original left-to-right order.
• The final outer operator is written after the RPN for both of its operands.

Common Mistakes

• Writing the division too early, for example 7 2 - / 8 + ..., which breaks the original structure.
• Ignoring the left-to-right order in (7 - 2 + 8) and treating it as if the + 8 came first.
• Forgetting that the whole numerator must be completed before the denominator and / are added.
• Mixing infix and RPN, such as writing 7 2 - + 8.

Things to Be Careful About

• Keep the operands in the same order as the original expression.
• Do not add unnecessary brackets in RPN; postfix notation does not use them here.
• Make sure the final operator / comes last, because it acts on the complete numerator and denominator, not on just the nearest numbers.

Background Concept

RPN expressions are evaluated using a stack. A stack is a Last In, First Out (LIFO) structure:

• when you read an operand, you push it onto the top of the stack
• when you read an operator, you pop the top two items, apply the operator, then push the result back

This works because, in postfix notation, each operator appears only after its required operands are already available.

The order of popping matters for subtraction and division:

• if the stack top is 7 and below it is 9, then - means 9 - 7, not 7 - 9
• similarly, / would mean the lower value divided by the top value

So the first popped item is the right-hand operand, and the second popped item is the left-hand operand.

Understanding the Question

You are asked to evaluate the RPN expression:

a d + a b + c - *

using the values:

a = 6, b = 3, c = 7, d = 9

The question also asks you to show the changing contents of the stack as the expression is evaluated. That means you should not only give the final answer, but also show what is in the stack after each token is processed.

The blank stack diagram in the question is there for exactly that purpose: one stack snapshot per step.

Approach

First replace the variables with their values:

6 9 + 6 3 + 7 - *

Then scan from left to right.

• Numbers are pushed.
• Operators combine the top two stack items.
• After each token, record the new stack contents.

This is the standard stack algorithm for evaluating RPN.

Step-by-Step Reasoning

Substitute first:

a d + a b + c - *

becomes:

6 9 + 6 3 + 7 - *

Now process one token at a time.

1. Read 6

   • push 6
   • stack: [6]

2. Read 9

   • push 9
   • stack: [6, 9]

3. Read +

   • pop 9, then pop 6
   • calculate 6 + 9 = 15
   • push 15
   • stack: [15]

4. Read 6

   • push 6
   • stack: [15, 6]

5. Read 3

   • push 3
   • stack: [15, 6, 3]

6. Read +

   • pop 3, then pop 6
   • calculate 6 + 3 = 9
   • push 9
   • stack: [15, 9]

7. Read 7

   • push 7
   • stack: [15, 9, 7]

8. Read -

   • pop 7, then pop 9
   • calculate 9 - 7 = 2
   • push 2
   • stack: [15, 2]

9. Read *

   • pop 2, then pop 15
   • calculate 15 * 2 = 30
   • push 30
   • stack: [30]

So the final value is 30.

The finished stack snapshots are shown here:

Key Takeaways

• RPN is evaluated from left to right using a stack.
• Operands are pushed; operators pop two values, combine them, and push the result.
• For - and /, operand order matters: second pop is the left operand, first pop is the right operand.
• If one value remains at the end, that value is the result of the whole expression.

Common Mistakes

• Doing subtraction in the wrong order, for example 7 - 9 instead of 9 - 7.
• Forgetting to substitute the variable values before evaluating.
• Removing only one value for an operator instead of two.
• Recording the stack in the wrong order, with the top and bottom reversed.
• Skipping intermediate stack states and giving only the final value.

Things to Be Careful About

• Read the RPN tokens strictly left to right.
• For each operator, pop exactly two items.
• Keep the stack order clear: bottom at the bottom, most recently pushed item at the top.
• In a drawn stack, leave unused cells blank rather than inventing extra values.
• The final answer here is not just the number 30; the changing stack contents must also be shown to gain all the marks.

Background Concept

Converting RPN back into infix is the reverse idea of evaluating it. Instead of pushing numbers and calculating immediately, you push symbols or partial expressions.

The rule is:

• when you read an operand, push it
• when you read an operator, pop the top two expressions, combine them as (left operator right), then push the new expression back

Again, order matters:

• first pop gives the right-hand side
• second pop gives the left-hand side

Parentheses are often added to make the grouping explicit and to avoid ambiguity.

Understanding the Question

You are given the RPN expression:

b a c - + d b + * c /

and asked to write it in infix form.

So the task is not to evaluate any values. Instead, you must rebuild the ordinary algebraic expression that would produce this postfix form. Because there are several operators, it is safest to reconstruct it step by step using a stack of partial expressions.

Approach

Process the RPN expression from left to right.

• Push operands such as b, a, c, d.
• When an operator appears, pop the top two expressions and combine them.
• Put brackets around the new combined expression before pushing it back.

By the time you reach the final token, the stack will contain one complete infix expression.

Step-by-Step Reasoning

Start with an empty stack of expressions.

1. Read b

   • push b

2. Read a

   • push a

3. Read c

   • push c

4. Read -

   • pop c and a
   • combine as (a - c)
   • push (a - c)

   Stack now contains b, (a - c)

5. Read +

   • pop (a - c) and b
   • combine as b + (a - c)
   • push (b + (a - c))

6. Read d

   • push d

7. Read b

   • push b

8. Read +

   • pop b and d
   • combine as (d + b)
   • push (d + b)

9. Read *

   • pop (d + b) and (b + (a - c))
   • combine as ((b + (a - c)) * (d + b))
   • push that result

10. Read c

• push c

1. Read /

• pop c and ((b + (a - c)) * (d + b))
• combine as ((b + (a - c)) * (d + b)) / c

So the infix form is:

((b + (a - c)) * (d + b)) / c

You could omit some outer brackets in some contexts, but keeping them makes the evaluation order completely clear and matches the RPN structure safely.

Key Takeaways

• To convert RPN to infix, use a stack of partial expressions.
• Each operator combines the two most recent expressions.
• The first item popped becomes the right operand; the second becomes the left operand.
• Brackets help preserve the exact structure of the original postfix expression.

Common Mistakes

• Reversing operand order, for example turning a c - into c - a.
• Forgetting to bracket a combined expression, which can change the meaning when it is used in a larger expression.
• Treating the expression as if operators act on the nearest visible letters only, rather than the top two stack expressions.
• Stopping too early and not combining the final / c.

Things to Be Careful About

• Keep the pop order correct for - and /.
• Do not lose earlier combined expressions when a new operator appears.
• Parentheses are especially useful when +, -, *, and / are mixed.
• The final answer must be a single complete infix expression, not a list of intermediate fragments.

Background Concept

A truth table shows the output of a logic circuit for every possible combination of its inputs. With three inputs, $A$, $B$ and $C$, there are $2^3 = 8$ possible rows.

To complete a truth table for a circuit like this, work from left to right through the circuit:

• a NOT gate inverts its input
• an OR gate outputs 1 if at least one input is 1
• an AND gate outputs 1 only if all inputs are 1
• an XOR gate outputs 1 only when its two inputs are different

Using intermediate columns such as $P$, $Q$, $R$, $S$ and $T$ is good practice because it mirrors the structure of the circuit and reduces mistakes.

Understanding the Question

You are given a logic circuit with three original inputs and several internal points labelled $P$, $Q$, $R$, $S$ and $T$. The question asks you to complete the whole truth table, not just the final output $Z$.

From the diagram:

• $P$ is the output of NOT on $A$, so $P = \overline{A}$
• $Q$ is the output of NOT on $B$, so $Q = \overline{B}$
• $R$ is the output of NOT on $C$, so $R = \overline{C}$
• the gate labelled $S$ is an OR gate in the diagram, taking inputs $P$, $B$ and $C$
• the gate labelled $T$ is an AND gate taking inputs $Q$ and $R$
• $Z$ is the XOR of $S$ and $T$

A key point here is to trust the gate symbols shown in the circuit when deciding the logic.

Approach

The safest method is:

1. write the eight combinations of $A$, $B$, $C$
2. calculate $P$, $Q$, $R$ using the NOT gates
3. calculate $S$ from its three inputs
4. calculate $T$ from its two inputs
5. compare $S$ and $T$ to get $Z$ using XOR

This avoids trying to jump straight to $Z$, which often causes errors.

Step-by-Step Reasoning

First write the inverted inputs:

• if $A = 0$, then $P = 1$; if $A = 1$, then $P = 0$
• if $B = 0$, then $Q = 1$; if $B = 1$, then $Q = 0$
• if $C = 0$, then $R = 1$; if $C = 1$, then $R = 0$

Now evaluate each row.

For $A=0$, $B=0$, $C=0$:

• $P=1$, $Q=1$, $R=1$
• $S = P + B + C = 1 + 0 + 0 = 1$
• $T = Q \cdot R = 1 \cdot 1 = 1$
• $Z = S \oplus T = 1 \oplus 1 = 0$

For $A=0$, $B=0$, $C=1$:

• $P=1$, $Q=1$, $R=0$
• $S = 1 + 0 + 1 = 1$
• $T = 1 \cdot 0 = 0$
• $Z = 1 \oplus 0 = 1$

For $A=0$, $B=1$, $C=0$:

• $P=1$, $Q=0$, $R=1$
• $S = 1 + 1 + 0 = 1$
• $T = 0 \cdot 1 = 0$
• $Z = 1 \oplus 0 = 1$

For $A=0$, $B=1$, $C=1$:

• $P=1$, $Q=0$, $R=0$
• $S = 1 + 1 + 1 = 1$
• $T = 0 \cdot 0 = 0$
• $Z = 1 \oplus 0 = 1$

For $A=1$, $B=0$, $C=0$:

• $P=0$, $Q=1$, $R=1$
• $S = 0 + 0 + 0 = 0$
• $T = 1 \cdot 1 = 1$
• $Z = 0 \oplus 1 = 1$

For $A=1$, $B=0$, $C=1$:

• $P=0$, $Q=1$, $R=0$
• $S = 0 + 0 + 1 = 1$
• $T = 1 \cdot 0 = 0$
• $Z = 1 \oplus 0 = 1$

For $A=1$, $B=1$, $C=0$:

• $P=0$, $Q=0$, $R=1$
• $S = 0 + 1 + 0 = 1$
• $T = 0 \cdot 1 = 0$
• $Z = 1 \oplus 0 = 1$

For $A=1$, $B=1$, $C=1$:

• $P=0$, $Q=0$, $R=0$
• $S = 0 + 1 + 1 = 1$
• $T = 0 \cdot 0 = 0$
• $Z = 1 \oplus 0 = 1$

So only the first row gives $Z=0$.

Key Takeaways

• Complete logic-circuit truth tables in stages using the internal labels.
• Work gate by gate rather than trying to guess the final output.
• XOR gives 1 when its two inputs are different, not simply when at least one is 1.

Common Mistakes

• Treating XOR as OR. OR would make the final column wrong when both inputs are 1.
• Forgetting to invert $A$, $B$ or $C$ before using $P$, $Q$ or $R$.
• Misreading the gate at $S$. The symbol shown is OR, so $S$ is not an AND expression.
• Copying one wrong intermediate value into several later columns.

Things to Be Careful About

• Use the rows in the order given and do not miss any combination.
• Keep the internal columns linked to the diagram: $P$, $Q$, $R$ first, then $S$ and $T$, then $Z$.
• For XOR, remember $0 \oplus 0 = 0$, $1 \oplus 1 = 0$, but $0 \oplus 1 = 1$ and $1 \oplus 0 = 1$.
• Check whether a 3-input gate needs all inputs examined; for $S$, one 1 is enough because it is OR.

Background Concept

A sum-of-products expression is a Boolean expression made from:

• product terms: ANDed literals such as $A \cdot \overline{B} \cdot C$
• sums: ORing those product terms together

A standard way to form a sum-of-products expression is from a truth table:

• for every row where the output is 1, write one product term
• if an input is 1 in that row, use the plain variable
• if an input is 0 in that row, use the complemented variable
• OR all those terms together

After that, if possible, simplify the expression.

Understanding the Question

This part asks for the Boolean expression corresponding to the circuit, specifically as a sum-of-products. The most direct route is to use the truth table from part (a).

From part (a), the final output $Z$ is 1 for every input combination except $A=0$, $B=0$, $C=0$.

That means you can either:

• write the canonical sum-of-products from the seven rows where $Z=1$, then simplify it, or
• recognise directly that the output is 1 whenever at least one of $A$, $B$ or $C$ is 1.

Approach

Start from the rows where $Z=1$. Each such row gives one minterm. Then simplify.

Because only 000 gives 0, the function behaves exactly like a 3-input OR. So the simplified sum-of-products is just $A + B + C$.

Step-by-Step Reasoning

Using the truth table, $Z=1$ for:

• 001
• 010
• 011
• 100
• 101
• 110
• 111

Now turn each row into a product term.

• 001 gives $\overline{A} \cdot \overline{B} \cdot C$
• 010 gives $\overline{A} \cdot B \cdot \overline{C}$
• 011 gives $\overline{A} \cdot B \cdot C$
• 100 gives $A \cdot \overline{B} \cdot \overline{C}$
• 101 gives $A \cdot \overline{B} \cdot C$
• 110 gives $A \cdot B \cdot \overline{C}$
• 111 gives $A \cdot B \cdot C$

OR them together:

Now observe the pattern: the only missing row is 000. So the function is 0 only when all three inputs are 0, and 1 otherwise. That is exactly the behaviour of:

This is still a valid sum-of-products expression, because each single variable is a product term of one literal.

Key Takeaways

• A truth table can be converted directly into a canonical sum-of-products expression.
• If the output pattern is obvious, you can often simplify quickly.
• $A + B + C$ means the output is 1 whenever at least one input is 1.

Common Mistakes

• Writing only the unsimplified minterms and stopping, when the pattern clearly simplifies.
• Missing one of the seven rows where $Z=1$.
• Using the wrong complemented form for a 0 input in a minterm.
• Confusing sum-of-products with product-of-sums.

Things to Be Careful About

• In sum-of-products, each product term must match one 1-row exactly.
• Use OR between the terms, not XOR.
• A simplified expression must still produce the same truth table as the original circuit.
• Do not forget that a single variable, such as $A$, is allowed as a product term in a simplified SOP expression.

Background Concept

A file access method is the way records are located and retrieved from a file. The main idea in this question is the difference between sequential access and direct access.

With sequential access, records are read one after another in order, so if the required record is near the end, many earlier records may need to be read first.

With direct access, the system can go straight to the required record's position. This is possible when the storage location is known, or can be calculated from the key field, or when the record number/address can be used directly.

So the essential feature of direct access is jumping straight to a location rather than stepping through every earlier record.

Understanding the Question

This part asks for the meaning of direct access as a method of file access. It is not asking for examples of particular file organisations yet, and it is not asking for the detailed process for sequential or random files. That happens in part (b).

For full marks, the answer needs two ideas:

• the record can be reached directly using an address or key-derived value
• previous records do not need to be read first

Approach

For a 2-mark “outline” question, the safest approach is to give two short, precise points:

1. say how the record is located
2. contrast it with reading through the file from the start

That covers both the definition and the important distinguishing feature.

Step-by-Step Reasoning

The phrase direct access means the access method does not depend on reading all earlier records.

A good answer therefore mentions that:

• each record can be found from a known position, address, or calculated location
• the computer can move straight to that record

The second marking point usually comes from making the contrast explicit:

• no need to process the file sequentially from the beginning

That is why the solution states both the direct jump and the absence of step-by-step reading.

Key Takeaways

• Direct access means going straight to a required record.
• It relies on an address, record number, or value derived from the key.
• It avoids reading every preceding record in turn.

Common Mistakes

• Saying only “records are stored in order.” That describes file organisation, not direct access itself.
• Saying “direct access is faster” without explaining why. Speed alone is not the definition.
• Confusing direct access with random files only. Direct access is an access method; it can be used in more than one context.

Things to Be Careful About

• Use the word access correctly: this question is about how a record is reached, not how records are arranged physically.
• Include both points for full marks: immediate access and no need to read previous records.
• Avoid vague phrases like “the computer just finds it”; say it uses an address or key-derived location.

Background Concept

A linear search looks through a list one item at a time, starting at the beginning and moving forward until either:

• the target item is found, or
• the search reaches the end of the list.

This is the simplest searching method. It works whether the array is sorted or not, because it does not rely on any ordering.

In pseudocode, a linear search often uses:

• a counter, to track the current array position
• a Boolean flag such as Found, to record whether the item has been found
• sometimes another Boolean flag such as NotInList, to record that the end has been reached without success

The loop condition usually continues while the item has not been found and the end has not been reached.

Understanding the Question

You are given most of a linear-search algorithm and must fill in the missing lines.

The array is Widgets, indexed from 1 to 50000. The user enters a string in ToFind. The code already sets:

• TopOfList ← 1
• EndOfList ← 50000

The missing parts must make the search work correctly.

So the blanks need to do four jobs:

1. initialise Found
2. give the WHILE loop condition
3. compare the current array element with ToFind
4. detect when the counter has moved beyond the last valid position

Approach

Because this is a standard linear search, the structure is:

1. set Found to FALSE before searching starts
2. start Count at the first valid index
3. repeat while the item has not been found and we are still within the list
4. compare Widgets[Count] with ToFind
5. if equal, set Found to TRUE
6. otherwise move to the next item
7. if the counter goes past EndOfList, set NotInList to TRUE

The given output line uses Count - 1, so the program is designed so that Count is increased after each check. That means the end-of-list test must happen after incrementing Count.

Step-by-Step Reasoning

The first missing line is:

Found ← FALSE

This is needed because before the search begins, we must assume the item has not yet been found.

The next relevant lines already given are:

NotInList ← FALSE
Count ← TopOfList

So the search starts at the first position in the array.

The WHILE condition must allow the search to continue only while both of these are true:

• the item has not been found
• the search has not reached beyond the array

So the loop condition is:

WHILE Found = FALSE AND NotInList = FALSE

Inside the loop, the program must check whether the current array element matches the user's input. The current element is Widgets[Count], so the comparison is:

IF Widgets[Count] = ToFind THEN

If this is true, then:

Found ← TRUE

After that, the code increments:

Count ← Count + 1

Then it must decide whether the search has gone past the last valid index. Since valid positions are 1 to 50000, once Count becomes greater than EndOfList, there are no more elements left to test. So the final blank is:

IF Count > EndOfList THEN

and then:

NotInList ← TRUE

That matches the given program structure exactly.

A useful detail here is why the final output says Count - 1. If the item is found at position 200, the program sets Found ← TRUE, then still executes Count ← Count + 1, so Count becomes 201. Therefore the correct position to output is Count - 1.

Key Takeaways

• A linear search checks items one by one from the start of the array.
• It needs a current position variable, usually a counter.
• A flag such as Found is often used to stop the search once the item is located.
• End-of-list checking is essential to avoid moving beyond valid array bounds.
• You must match your stopping condition to the exact order of statements in the algorithm.

Common Mistakes

• Setting Found ← TRUE at the start. That would stop the loop immediately.
• Using IF Widgets[TopOfList] = ToFind instead of Widgets[Count]. The search must check the current position, not always the first element.
• Writing IF Widgets[Count] <> ToFind THEN NotInList ← TRUE. One mismatch does not mean the item is absent; it only means the current element is not the one wanted.
• Using IF Count = EndOfList THEN NotInList ← TRUE after incrementing. This would stop too early and may miss checking the last item properly.
• Forgetting that the output uses Count - 1, which depends on the counter being incremented before the loop ends.

Things to Be Careful About

• The array is indexed from 1, not 0.
• The loop condition must use both flags with AND, not OR.
• Found must be initialised before the loop starts.
• The comparison must be against Widgets[Count], because Count changes each iteration.
• The boundary test is Count > EndOfList because Count is increased before checking whether the end has been passed.

Background Concept

Searching algorithms are used to find whether a target item exists in a collection and, if so, where it is.

Two important search methods are:

• Linear search: examine items one after another
• Binary search: repeatedly split the search area in half

Linear search works by starting at the first element and comparing each value with the target. If the current value is not the target, the algorithm moves to the next element.

Binary search works only when the data is already sorted. It compares the target with the middle element:

• if they are equal, the search is complete
• if the target is smaller, search the lower half
• if the target is larger, search the upper half

This halving continues until the item is found or no items remain.

Big O notation describes how the running time grows as the number of items, $n$, increases.

• $O(n)$ means the time grows roughly in direct proportion to the number of items.
• $O(\log n)$ means the time grows much more slowly, because the problem size is repeatedly reduced by a factor of 2.

Understanding the Question

The question asks you to compare the methods used by linear and binary search, not just define them. It also specifically says to refer to Big O notation, so you must include their efficiencies.

That means a full answer needs both:

• how each algorithm works
• the complexity of each one

A strong comparison should also mention the key condition for binary search: the array must be sorted.

Approach

A clear way to answer is:

1. explain the method used by linear search
2. state its Big O
3. explain the method used by binary search
4. state its Big O and the need for sorted data

This covers both the practical difference in how they search and the theoretical difference in efficiency.

Step-by-Step Reasoning

Start with linear search.

It begins at the first element of the array and compares that element with the target.

• If the item matches, the search stops.
• If it does not match, the algorithm checks the next item.
• This continues until the item is found or the end of the array is reached.

Because the search may need to inspect every element, the worst-case number of comparisons is proportional to $n$.

So linear search is:

Now compare that with binary search.

Binary search does not look at every item one by one. Instead, it uses the fact that the array is sorted.

• First, it checks the middle item.
• If the target is smaller than the middle item, the entire top half can be ignored.
• If the target is larger, the entire bottom half can be ignored.
• The same process is repeated on the remaining half.

So each comparison cuts the search space roughly in half.

For example, if there are 64 items:

• after 1 comparison, at most 32 remain
• after 2 comparisons, at most 16 remain
• after 3 comparisons, at most 8 remain

This is why the growth is logarithmic rather than linear.

So binary search is:

This makes binary search much faster than linear search for large arrays, but only if the array is sorted first. If the array is unsorted, binary search cannot correctly discard half the items.

Therefore the comparison is:

• linear search: sequential checking, works on unsorted data, $O(n)$
• binary search: repeated halving, needs sorted data, $O(\log n)$

Key Takeaways

• Linear search checks items one at a time from the start.
• Binary search repeatedly checks the middle and halves the remaining search area.
• Binary search requires the data to be sorted.
• In Big O terms, linear search is $O(n)$ and binary search is $O(\log n)$.
• For large sorted arrays, binary search is usually far more efficient.

Common Mistakes

• Saying binary search is always better without mentioning that the array must be sorted.
• Giving only the Big O values without explaining how the algorithms work.
• Saying linear search is $O(1)$. It is only constant time in a lucky best-case situation, not in general or worst-case comparison.
• Writing that binary search removes one item at a time. It removes half of the remaining items each step.
• Confusing $O(\log n)$ with $O(n \log n)`, which is a different complexity used for some sorting algorithms.

Things to Be Careful About

• In this syllabus, when comparing search efficiency, the expected Big O is normally the general or worst-case performance.
• Do not forget the word sorted when describing binary search.
• Since the question says "compare", make sure both algorithms are discussed, not just one.
• Keep the method descriptions accurate: linear is sequential, binary is divide-and-conquer by halving.
• Use correct Big O notation: $O(n)$ for linear search and $O(\log n)$ for binary search.

Background Concept

A virtual machine is a software-based imitation of a computer system. It allows one physical computer to behave like several separate computers. Each virtual machine is given virtual hardware such as virtual memory, a virtual disk and virtual network hardware, and it can run its own operating system.

Virtualisation is useful because it separates software environments from the physical machine. This makes it possible to run different operating systems, keep environments isolated, and make better use of hardware. However, this extra layer also introduces overhead because the real hardware is being shared and managed through software.

Understanding the Question

This part asks for exactly four points: two benefits and two limitations of using a virtual machine. The wording says "outline", so each point should be short but clear. The marks are usually awarded for distinct valid points, so repeating the same idea in different words would not gain extra credit.

You need to think about what virtual machines are good for in practice, and what disadvantages come from not running directly on the physical hardware.

Approach

A good way to answer is to split your thinking into two sides:

1. What advantages does virtualisation give?

   • flexibility
   • isolation
   • testing
   • running multiple systems on one machine

2. What problems does it cause?

   • slower execution
   • more memory/storage/CPU needed
   • limited direct hardware access
   • dependence on the host machine

Then choose two strong benefits and two strong limitations that are clearly different from each other.

Step-by-Step Reasoning

The first benefit chosen is that multiple operating systems can run on one physical computer. This is a standard benefit because each VM behaves like a separate machine, so one device can host different environments.

The second benefit is safe isolation for testing. If a new operating system, patch or program is tested inside a VM and fails, the host system is not directly affected. This is why VMs are widely used for development, training and cybersecurity testing.

The first limitation is reduced performance. A VM does not usually have direct, unrestricted use of the real hardware. The host system has to manage resources, and the virtualisation layer adds overhead, so execution is typically slower than on a physical machine.

The second limitation is high resource usage. If several VMs are running, each one needs memory, storage and processor time. A machine with limited RAM or CPU power may struggle.

These four points are distinct and match the question requirement exactly.

Key Takeaways

• A virtual machine is a software-based computer running on real hardware.
• Key benefits include flexibility and isolation.
• Key limitations include performance overhead and resource demands.
• For short theory questions, give separate points rather than repeating one idea.

Common Mistakes

• Giving two benefits that are really the same point, such as "can test safely" and "mistakes do not affect the real system" without adding a different idea.
• Writing vague statements like "it is good" or "it is bad" with no explanation of why.
• Confusing a virtual machine with a simulator or emulator.
• Giving features of an operating system in general rather than benefits or limitations of virtualisation.

Things to Be Careful About

• The question asks for two benefits and two limitations, so make sure all four are present.
• Each point should be distinct.
• Keep the focus on virtual machines, not just on computers in general.
• If you mention testing or isolation, make it clear that the VM is separated from the host system.

Background Concept

In a virtualised system there are two operating-system levels to think about.

The host operating system is the operating system installed directly on the physical computer. It has access to the real CPU, RAM, storage and peripherals. It is responsible for controlling these hardware resources.

The guest operating system is an operating system installed inside a virtual machine. To the guest, the VM appears to be a normal computer, but the hardware it sees is virtual rather than physical.

This separation is fundamental to virtualisation: the host manages the actual machine, while the guest manages the virtual environment presented to it.

Understanding the Question

This question asks you to explain the roles of both the host OS and the guest OS. So you must not just define them; you must say what each one does.

The key distinction is:

• host OS = responsible for the real machine
• guest OS = responsible for the virtual machine environment

Because the question says "as used in a computer system running a virtual machine", the answer should stay in the context of virtualisation rather than giving general operating-system functions only.

Approach

A simple approach is to answer in three linked points:

1. State where the host OS runs and what it controls.
2. State that the host OS supports or runs the VM software and shares out resources.
3. State where the guest OS runs and what it controls inside the VM.

That gives a complete comparison while staying concise enough for a 3-mark answer.

Step-by-Step Reasoning

First, identify the host OS. This is the operating system on the actual physical computer. Since it is installed directly on the machine, it is the layer that deals with the real processor, main memory, disk drives and external devices.

Next, explain its virtualisation role. The host OS runs the virtual machine software, or supports the hypervisor layer, and allocates hardware resources to the VMs. For example, it decides how much RAM a VM can use, gives it processor time, and allows access to storage or network devices.

Then identify the guest OS. This is the operating system installed inside one of those virtual machines. It does not control the real hardware directly. Instead, it controls the virtual hardware presented to it by the VM.

Finally, explain its job. The guest OS runs user applications inside that VM and manages files, memory and processes within the virtual environment, just as if it were running on a separate physical computer.

So the host OS is concerned with the real machine and resource sharing, while the guest OS is concerned with the operation of the virtual machine itself.

Key Takeaways

• The host OS is the operating system on the real hardware.
• The guest OS is the operating system inside the virtual machine.
• The host manages physical resources and provides the VM environment.
• The guest manages the virtual environment and runs its own applications.

Common Mistakes

• Saying the guest OS controls the physical hardware directly. It normally does not; it sees virtual hardware.
• Describing only the host OS and forgetting the guest OS, or vice versa.
• Confusing the host OS with the hypervisor. In exam answers, it is usually enough to say the host runs or supports the virtual machine software.
• Giving a general definition of an operating system without linking it to virtual machines.

Things to Be Careful About

• Use the words physical or real hardware for the host OS and virtual hardware for the guest OS.
• Make the contrast clear; examiners are looking for different roles, not two similar descriptions.
• Do not overcomplicate the answer with unnecessary detail about hardware drivers or boot loaders unless it directly supports the role explanation.
• Keep the focus on what each operating system is responsible for in a VM setup.

Background Concept

In declarative programming, knowledge is stored as facts and rules.

• A fact states something that is true, for example client(stevie).
• A rule states that something is true if certain conditions are true.
• A goal is a query used to ask the system to find values that satisfy facts and rules.

This part only needs facts. Each clause represents one true statement about the world:

• activity(...) says something is an activity.
• client(...) says someone is a client.
• choice(person, activity) says that person has chosen that activity.
• done(person, activity) says that person has already done that activity.

Understanding the Question

The question gives a short English description about Jane and asks you to add clauses to represent it.

The description contains four separate pieces of information:

1. Jane is a client.
2. Surfing is an activity.
3. Jane would like to choose surfing.
4. Jane has already done sailing.

Since the program stores information as facts, each of these must become one clause.

Approach

The best approach is to break the sentence into separate facts, then match each fact to the predicate already used in the program.

• "Jane is a client" matches client(...)
• "surfing is an activity" matches activity(...)
• "would like to choose surfing" matches choice(...)
• "has already done sailing" matches done(...)

Then write each one using the same style as the existing clauses: lowercase atoms inside brackets, ending with a full stop.

Step-by-Step Reasoning

Look at the existing examples:

• activity(paddleboarding). shows how an activity is stored.
• client(stevie). shows how a client is stored.
• choice(petra, rowing). shows how a chosen activity is stored.
• done(henry, jetskiing). shows how a completed activity is stored.

Now convert Jane's information.

1. Jane is a client:

   • predicate needed: client
   • clause: client(jane).

2. Surfing is an activity:

   • predicate needed: activity
   • clause: activity(surfing).

3. Jane would like to choose surfing:

   • predicate needed: choice
   • first item is the client, second is the activity
   • clause: choice(jane, surfing).

4. Jane has already done sailing:

   • predicate needed: done
   • first item is the client, second is the activity
   • clause: done(jane, sailing).

The order of these clauses is usually not important for the meaning here, as long as all four correct facts are present.

Key Takeaways

• Translate each separate English statement into one declarative fact.
• Reuse the same predicate names and argument order already established in the knowledge base.
• Facts in this style are written with lowercase names and a full stop at the end.

Common Mistakes

• Writing jane or surfing with capitals. In declarative languages, capitalised words are often treated as variables, not fixed values.
• Using the wrong predicate, such as done(jane, surfing) instead of choice(jane, surfing).
• Reversing the argument order, for example choice(surfing, jane).
• Forgetting one of the four facts, especially the new activity surfing.

Things to Be Careful About

• Keep the same style as the given clauses.
• Use choice(jane, surfing) because she wants to choose it now.
• Use done(jane, sailing) because sailing is the activity she has already done.
• End each clause with a full stop.

Background Concept

A goal in declarative programming asks the system to find values that make a statement true.

For example, the goal choice(List, rowing) means:

• find every value of List such that a fact choice(List, rowing) exists.

The variable gets substituted with each matching value. If several facts match, all corresponding values are returned.

Understanding the Question

You are given one example:

• choice(List, rowing) returns petra, eliza

That example shows the method. You must now do the same for:

• choice(List, sailing)

So you need to scan the facts and find every choice fact where the second item is sailing.

Approach

Search only the choice(...) clauses, because the goal uses the predicate choice.

Then keep the ones with activity sailing and take the first item from each matching fact as the value of List.

Step-by-Step Reasoning

Relevant choice facts are:

• choice(petra, rowing).
• choice(frankie, sailing).
• choice(erik, sailing).
• choice(eliza, rowing).
• choice(stevie, jetskiing).
• choice(henry, sailing).

Now compare each one with choice(List, sailing):

• choice(petra, rowing) does not match because the activity is rowing.
• choice(frankie, sailing) matches, so List = frankie.
• choice(erik, sailing) matches, so List = erik.
• choice(eliza, rowing) does not match.
• choice(stevie, jetskiing) does not match.
• choice(henry, sailing) matches, so List = henry.

Therefore the returned values are:

• frankie
• erik
• henry

These are usually written in the order the matching facts appear.

Key Takeaways

• A goal matches only facts with the same predicate name.
• Variables are filled with values from matching facts.
• If several facts match, the result contains all successful substitutions.

Common Mistakes

• Including clients from done(...) facts instead of only choice(...) facts.
• Missing one of the sailing choices.
• Changing the order of names when the normal return order follows the fact order.

Things to Be Careful About

• Only choice facts matter here.
• The second argument must be exactly sailing.
• List is a variable, so you return the first argument from each matching fact.

Background Concept

A rule in declarative programming defines when a statement is true.

A rule has:

• a head: the statement being defined
• a body: the conditions that must be true

So a rule means:

• the head is true if all the body conditions are true.

This question also uses negation. Negation means a condition is true only when a matching fact cannot be found. Here, a client may choose an activity only if there is no fact showing that the client has already done it.

Understanding the Question

You are asked to define the rule may_choose_activity(C, A).

The question already tells you the exact meaning:

• C is a client
• A is an activity
• C has not already done A

So the body of the rule must contain those three conditions.

Approach

Take the English conditions one by one and convert each into a predicate:

• "C is a client" becomes client(C)
• "A is an activity" becomes activity(A)
• "C has not already done A" becomes NOT(done(C, A))

Then join them with AND because all of them must be true at the same time.

Step-by-Step Reasoning

Start with the rule head:

• may_choose_activity(C, A)

Now add the conditions.

1. C must be a client:

   • client(C)

2. A must be an activity:

   • activity(A)

3. C must not already have done A:

   • NOT(done(C, A))

Because the wording says "if A is an activity and C has not already done A" and the first sentence says "C is a client", all conditions are required together.

So the complete rule is:

may_choose_activity(C, A) IF client(C) AND activity(A) AND NOT(done(C, A))

This means the system can prove may_choose_activity(C, A) only when:

• C is known as a client,
• A is known as an activity,
• and there is no matching done(C, A) fact.

For example:

• may_choose_activity(henry, sailing) would fail because there is no done(henry, sailing) issue? Actually Henry has done jetskiing, not sailing, so this rule would allow sailing as long as sailing is an activity and Henry is a client.
• may_choose_activity(henry, jetskiing) would fail because done(henry, jetskiing) exists.

Key Takeaways

• A declarative rule is built from a head and a set of conditions.
• Each English condition should map directly to an existing predicate.
• Negation is used to block results when an unwanted fact exists.

Common Mistakes

• Omitting client(C), even though the question says C is a client.
• Writing done(C, A) instead of NOT(done(C, A)), which reverses the meaning.
• Using OR instead of AND, which would make the rule far too permissive.
• Swapping the arguments and writing done(A, C).

Things to Be Careful About

• Keep the variables consistent: use C for the client and A for the activity throughout.
• The condition is about activities already done, not activities already chosen.
• Use negation on done(C, A), not on activity(A) or client(C).
• Follow the style given in the question, which uses IF to introduce the rule body.