GATE CSE 2006 | Question: 50

Question

A set $X$ can be represented by an array $x[n]$ as follows: 

 $x\left [ i \right ]=\begin {cases} 1 & \text{if } i \in X \\ 0 & \text{otherwise}  \end{cases}$

Consider the following algorithm in which $x$, $y$, and $z$ are Boolean arrays of size $n$: 

algorithm zzz(x[], y[], z[]) {
    int i;
    
    for(i=0; i<n; ++i)
        z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);
}

The set $Z$ computed by the algorithm is: 

• A. $(X\cup Y)$
• B. $(X\cap Y)$
• C. $(X-Y)\cap (Y-X)$
• D. $(X-Y)\cup (Y-X)$

Comments

Apply simple set theory to it.
(X ∧ ~Y) ∨ (~X ∧ Y)

Draw venn diagram. Answer is D.

---

Hi Guys,

I think quickly answer could be obtained by 'Venn Diagram'.

---

algorithm zzz(x[], y[], z[]) {
    int i;
    
    for(i=0; i<n; ++i)
        z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);
}

Focus highlighted line you can write as-

z = (x ^ y’ ) v ( x’ ^ y)

or….z = x.y’ + x’y

now match with options which one is matching only D will match.

from option D :

(x-y) union ( y -x)

or

xy’ + yx’

So D is correct.

 

Answer 1

Correct Option: D

In the given algorithm the for loop contains a logical expression

 z[i] = (x[i] ∧ ~y[i]) ∨ (~x[i] ∧ y[i]);

The equivalent set representation of a given logical expression if we assume $z[i] = Z, x[i] = X, y[i] = Y$ then 

$Z = ( X \wedge \neg Y ) \vee ( \neg X \wedge  Y)$

$\implies Z = ( X - Y ) \cup ( Y - X )  [\because A \wedge \neg B = A - B]$

Comments

This can also be solve using some example and even by using ven  diagram which resuts in exor operation at end hence d)

---

This is the symettric difference operation.

Answer 2

experesion AB' + A'B is XOR.. XOR has property that either of A or B is 1 then output is 1 but not both...

this can be achieved by option (D)..

Answer 3

Here, I illustrated a bit more with an example taking set X, Y with corresponding array x and array y.

 

 

Answer : D

Comments

great explanation bro….

---

how did you presumed which elements to take in the set

Answer 4

D

This is called the symettric difference of two sets

Source: https://en.wikipedia.org/wiki/Symmetric_difference