A set X can be represented by an array x[n] as follows: Consider the following…
2006
A set X can be represented by an array x[n] as follows:
Consider the following algorithm in which x,y and z are Boolean arrays of size n:
C
algorithm zzz(x[] , y[], z [])
{
int i;
for (i=O; i<n; ++i)
z[i] = (x[i] ^ ~y[i]) V (~x[i] ^ y[i])
}
The set Z computed by the algorithm is:
- A.
(X ∩ Y)
- B.
(X ∪ Y)
- C.
(X-Y) ∩ (Y-X)
- D.
(X-Y) ∪ (Y-X)
Attempted by 149 students.
Show answer & explanation
Correct answer: D
Interpretation: x[i] and y[i] are Boolean indicators for membership in X and Y respectively. The expression in the code is (x[i] AND NOT y[i]) OR (NOT x[i] AND y[i]).
Case analysis (for each index i):
If x[i] = 1 and y[i] = 0, then (x[i] AND NOT y[i]) is true, so z[i] = 1 (element is in X − Y).
If x[i] = 0 and y[i] = 1, then (NOT x[i] AND y[i]) is true, so z[i] = 1 (element is in Y − X).
If x[i] = 1 and y[i] = 1, both terms are false, so z[i] = 0.
If x[i] = 0 and y[i] = 0, both terms are false, so z[i] = 0.
Conclusion: z[i] = 1 exactly when the element belongs to exactly one of X or Y. Therefore the set computed is (X − Y) ∪ (Y − X), the symmetric difference of X and Y.