GATE CS 2024 Set 1 — Question 40

Let the statements be:
T1:
$S_1: a = a + 1$
$S_2: b = b + 1$
Constraint: $S_1$ must execute before $S_2$.T2:
$S_3: b = 2 * b$
$S_4: a = 2 * a$
Constraint: $S_3$ must execute before $S_4$.Initially $a=1, b=1$.Analysis of variable $a$:
Operations on $a$ are $S_1 (+1)$ and $S_4 (*2)$.

• If order is $S_1, S_4$: $1 \xrightarrow{+1} 2 \xrightarrow{*2} 4$. ($a=4$)
• If order is $S_4, S_1$: $1 \xrightarrow{*2} 2 \xrightarrow{+1} 3$. ($a=3$)

So $a \in \{3, 4\}$.Analysis of variable $b$:
Operations on $b$ are $S_2 (+1)$ and $S_3 (*2)$.

• If order is $S_2, S_3$: $1 \xrightarrow{+1} 2 \xrightarrow{*2} 4$. ($b=4$)
• If order is $S_3, S_2$: $1 \xrightarrow{*2} 2 \xrightarrow{+1} 3$. ($b=3$)

So $b \in \{3, 4\}$.Valid Interleavings:
We must respect thread order ($S_1 < S_2$ and $S_3 < S_4$).
Total permutations of 4 instructions is $\frac{4!}{2!2!} = 6$.Possible outcomes: $\{(4, 4), (4, 3), (3, 3)\}$.Note: The outcome $(3, 4)$ requires $S_4 < S_1$ (for $a=3$) and $S_2 < S_3$ (for $b=4$).
Combined with thread constraints $S_1 < S_2$ and $S_3 < S_4$, we get cycle: $S_4 < S_1 < S_2 < S_3 < S_4$. Impossible.Thus, the set of possible values is $\{(a=4, b=4), (a=3, b=3), (a=4, b=3)\}$.