GATE CS 2024 Set 1 - W3Colleges

Question 31

MSQ · 1 mark

Which of the following fields is/are modified in the IP header of a packet going out of a network address translation (NAT) device from an internal network to an external network?

Source IP Destination IP Header Checksum Total Length

Explanation

Answer: (A), (C)

A NAT device lets hosts with private addresses share a public address. For a packet leaving the internal network it replaces the private source address with its own public address (with port translation it also changes the source port, but that is in the TCP or UDP header) and records the mapping so that replies can be sent back.

Source IP: modified, as described.
Destination IP: unchanged, because the packet still goes to the same external host.
Header Checksum: modified. It covers the whole IP header, so it must be recomputed once the source address changes.
Total Length: unchanged, because the sizes of the header and the data stay the same.

Answer: A, C

Question 32

NAT · 1 mark

Let $A$ and $B$ be non-empty finite sets such that there exist one-to-one and onto functions (i) from $A$ to $B$ and (ii) from $A \times A$ to $A \cup B$. The number of possible values of $|A|$ is __________

Your answer

Explanation

Answer: 2

A one-to-one and onto function (a bijection) exists between two finite sets exactly when they have the same number of elements. Let $|A| = n \ge 1$.

Condition (i) gives $|B| = n$.
Condition (ii) gives $|A \cup B| = |A \times A| = n^{2}$.

The union of two $n$-element sets has between $n$ elements (when $A = B$) and $2n$ elements (when they are disjoint), so $n \le n^{2} \le 2n$, which forces $n \le 2$.

$n = 1$: take $A = B = \{a\}$; then $|A \cup B| = 1 = 1^{2}$.
$n = 2$: take disjoint $A = \{a, b\}$ and $B = \{c, d\}$; then $|A \cup B| = 4 = 2^{2}$.

Both values occur, so $|A|$ has 2 possible values.

Answer: 2

Question 33

NAT · 1 mark

Consider the operator precedence and associativity rules for the integer arithmetic operators given in the table below.

Operator	Precedence	Associativity
$+$	Highest	Left
$-$	High	Right
$*$	Medium	Right
$/$	Low	Right

The value of the expression $3 + 1 + 5 * 2 \mathbin{/} 7 + 2 - 4 - 7 - 6 \mathbin{/} 2$ as per the above rules is __________

Your answer

Explanation

Answer: 6

The operator with the lowest precedence is applied last, so the expression splits first at $/$. As $/$ is right-associative, it reads $A \mathbin{/} (B \mathbin{/} C)$ with $A = 3 + 1 + 5 * 2$, $B = 7 + 2 - 4 - 7 - 6$ and $C = 2$.

In $A$, $+$ binds tighter than $*$: $A = (3 + 1 + 5) * 2 = 18$.
In $B$, $+$ binds first, giving $9 - 4 - 7 - 6$; right-associative $-$ groups this as $9 - (4 - (7 - 6)) = 9 - 3 = 6$.
The value is $18 \mathbin{/} (6 \mathbin{/} 2) = 18 \mathbin{/} 3 = 6$, and every division is exact.

The usual C rules would give $-7$ instead.

Answer: 6

Question 34

NAT · 1 mark

The number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is _________

Your answer

Explanation

Answer: 16

By Cayley’s formula, the complete graph on $n$ labelled vertices has $n^{n-2}$ spanning trees, so $K_{4}$ has $4^{4-2} = 16$.

A direct count agrees. A spanning tree on 4 vertices has 3 edges, and $K_{4}$ has 6 edges, so there are $\binom{6}{3} = 20$ sets of 3 edges. Three edges on four vertices fail to form a tree only when they make a triangle (leaving the fourth vertex isolated), and $K_{4}$ has 4 triangles: $20 - 4 = 16$. They are the 12 paths and the 4 stars on A, B, C, D.

Answer: 16

Question 35

NAT · 1 mark

Consider the following two relations, $\boldsymbol{R(A,B)}$ and $\boldsymbol{S(A,C)}$:

$\boldsymbol{R}$
$\boldsymbol{A}$	$\boldsymbol{B}$
10	20
20	30
30	40
30	50
50	95

$\boldsymbol{S}$
$\boldsymbol{A}$	$\boldsymbol{C}$
10	90
30	45
40	80

The total number of tuples obtained by evaluating the following expression

\[\boldsymbol{\sigma_{B \lt C}(R \bowtie_{R.A=S.A} S)}\]

is _________

Your answer

Explanation

Answer: 2

The join pairs each tuple of $R$ with the tuples of $S$ that have the same $A$ value:

$A = 10$: $(10, 20)$ pairs with $(10, 90)$.
$A = 30$: $(30, 40)$ and $(30, 50)$ both pair with $(30, 45)$.
$A = 20$ and $A = 50$ have no match in $S$, and the $S$ tuple with $A = 40$ has no match in $R$.

So the join has 3 tuples, whose $(B, C)$ values are $(20, 90)$, $(40, 45)$ and $(50, 45)$. The selection $B \lt C$ keeps the first two and removes $(50, 45)$, leaving 2 tuples.

Answer: 2

Question 36

MCQ · 2 marks · −0.66

Consider a network path P—Q—R between nodes P and R via router Q. Node P sends a file of size $10^{6}$ bytes to R via this path by splitting the file into chunks of $10^{3}$ bytes each. Node P sends these chunks one after the other without any wait time between the successive chunk transmissions. Assume that the size of extra headers added to these chunks is negligible, and that the chunk size is less than the MTU.

Each of the links P—Q and Q—R has a bandwidth of $10^{6}$ bits/sec, and negligible propagation latency. Router Q immediately transmits every packet it receives from P to R, with negligible processing and queueing delays. Router Q can simultaneously receive on link P—Q and transmit on link Q—R.

Assume P starts transmitting the chunks at time $t = 0$.
Which one of the following options gives the time (in seconds, rounded off to 3 decimal places) at which R receives all the chunks of the file?

8.000 8.008 15.992 16.000

Explanation

Answer: (B)

The file is split into $10^{6} / 10^{3} = 1000$ chunks of 8000 bits each. Sending one chunk on a $10^{6}$ bits/sec link takes $8000 / 10^{6}$ s, that is 8 ms.

P sends the chunks back to back, so Q has received the last chunk at $1000 \times 8$ ms $= 8$ s. Q forwards each chunk as soon as it has fully arrived, and because it can send while it receives, it finishes forwarding one chunk just as the next one has arrived: no queue builds up. The last chunk then needs one more transmission time on Q—R, so R has everything at $8 + 0.008 = 8.008$ s.

Holding the whole file at Q before forwarding would give 16.000 s, and 8.000 s leaves out the second hop of the last chunk.

Answer: B

Question 37

MCQ · 2 marks · −0.66

Consider the following syntax-directed definition (SDD).

${S \to DHTU}$	$\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}$
${D \to \text{``M''}D_{1}}$	$\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}$
${D \to \epsilon}$	$\{\ D.\mathit{val} = -5;\ \}$
${H \to \text{``L''}H_{1}}$	$\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}$
${H \to \epsilon}$	$\{\ H.\mathit{val} = -10;\ \}$
${T \to \text{``C''}T_{1}}$	$\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}$
${T \to \epsilon}$	$\{\ T.\mathit{val} = -5;\ \}$
${U \to \text{``K''}}$	$\{\ U.\mathit{val} = 5;\ \}$

Given "MMLK" as the input, which one of the following options is the CORRECT value computed by the SDD (in the attribute $S.\mathit{val}$)?

45 50 55 65

Explanation

Answer: (A)

For "MMLK", the rule $S \to DHTU$ uses $D$ for "MM", $H$ for "L", $T$ for the empty string and $U$ for "K". Evaluating the attributes bottom-up:

$D$: the innermost $D \to \epsilon$ gives $-5$, then $5 + (-5) = 0$, then $5 + 0 = 5$.
$H$: $H \to \epsilon$ gives $-10$, then $5 * 10 + (-10) = 40$.
$T \to \epsilon$ gives $-5$, and $U$ gives 5.

So $S.\mathit{val} = 5 + 40 + (-5) + 5 = 45$. Ignoring the negative values of some of the $\epsilon$-productions leads to the other options, 50, 55 or 65.

Answer: A

Question 38

MCQ · 2 marks · −0.66

Consider the following grammar $G$, with $S$ as the start symbol. The grammar $G$ has three incomplete productions denoted by (1), (2), and (3).

$S \to daT \mid \underline{\quad (1) \quad}$
$T \to aS \mid bT \mid \underline{\quad (2) \quad}$
$R \to \underline{\quad (3) \quad} \mid \epsilon$

The set of terminals is $\{a, b, c, d, f\}$. The FIRST and FOLLOW sets of the different non-terminals are as follows.

FIRST($S$) = $\{c, d, f\}$, FIRST($T$) = $\{a, b, \epsilon\}$, FIRST($R$) = $\{c, \epsilon\}$

FOLLOW($S$) = FOLLOW($T$) = $\{c, f, \$\}$, FOLLOW($R$) = $\{f\}$

Which one of the following options CORRECTLY fills in the incomplete productions?

(1) $S \to Rf$ (2) $T \to \epsilon$ (3) $R \to cTR$ (1) $S \to fR$ (2) $T \to \epsilon$ (3) $R \to cTR$ (1) $S \to fR$ (2) $T \to cT$ (3) $R \to cR$ (1) $S \to Rf$ (2) $T \to cT$ (3) $R \to cR$

Explanation

Answer: (A)

(2): FIRST($T$) contains $\epsilon$ but not $c$, so the missing rule is $T \to \epsilon$. $T \to cT$ (options C, D) would put $c$ into FIRST($T$) and leave $\epsilon$ out.
(1): $c \in$ FIRST($S$) can only come through $R$. With $S \to Rf$ and $R$ nullable, FIRST($Rf$) = $\{c, f\}$, so FIRST($S$) = $\{c, d, f\}$. $S \to fR$ would miss $c$ and would also put $\$$ into FOLLOW($R$).
(3): $R \to cTR$ gives FIRST($R$) = $\{c, \epsilon\}$. In it $T$ is followed by $R$, so FOLLOW($T$) gets $c$ and, because $R$ can vanish, also FOLLOW($R$) = $\{f\}$, which comes from $S \to Rf$. With $S \to daT$ and $T \to aS$, FOLLOW($S$) = FOLLOW($T$) = $\{c, f, \$\}$, exactly the given sets.

Answer: A

Question 39

MCQ · 2 marks · −0.66

Consider the following pseudo-code.

L1:    t1 = -1
L2:    t2 = 0
L3:    t3 = 0
L4:    t4 = 4 * t3
L5:    t5 = 4 * t2
L6:    t6 = t5 * M
L7:    t7 = t4 + t6
L8:    t8 = a[t7]
L9:    if t8 <= max goto L11
L10:   t1 = t8
L11:   t3 = t3 + 1
L12:   if t3 < M goto L4
L13:   t2 = t2 + 1
L14:   if t2 < N goto L3
L15:   max = t1

Which one of the following options CORRECTLY specifies the number of basic blocks and the number of instructions in the largest basic block, respectively ?

6 and 6 6 and 7 7 and 7 7 and 6

Explanation

Answer: (D)

A leader starts each basic block: the first instruction, every jump target, and every instruction right after a jump.

L1 is the first instruction.
L11, L4 and L3 are the targets of the jumps in L9, L12 and L14.
L10, L13 and L15 each follow a conditional jump.

These 7 leaders give 7 blocks: L1–L2, L3, L4–L9, L10, L11–L12, L13–L14 and L15. The largest is L4–L9, with 6 instructions; it ends at the jump in L9. Missing L3 or L4 as a leader merges two blocks, which leads to the 6-block options A and B.

Answer: D

Question 40

MCQ · 2 marks · −0.66

Consider the following two threads T1 and T2 that update two shared variables a and b. Assume that initially a = b = 1. Though context switching between threads can happen at any time, each statement of T1 or T2 is executed atomically without interruption.

    T1                T2

a = a + 1;        b = 2 * b;
b = b + 1;        a = 2 * a;

Which one of the following options lists all the possible combinations of values of a and b after both T1 and T2 finish execution?

(a = 4, b = 4); (a = 3, b = 3); (a = 4, b = 3) (a = 3, b = 4); (a = 4, b = 3); (a = 3, b = 3) (a = 4, b = 4); (a = 4, b = 3); (a = 3, b = 4) (a = 2, b = 2); (a = 2, b = 3); (a = 3, b = 4)

Explanation

Answer: (A)

Each thread runs its two statements in order, so the four atomic statements interleave in $\binom{4}{2} = 6$ ways. Writing the results as $(a, b)$:

T1 entirely first: $a = 2$, $b = 2$, then $b = 4$, $a = 4$: (4, 4).
T2 entirely first: $b = 2$, $a = 2$, then $a = 3$, $b = 3$: (3, 3).
Each of the other four orders runs a = a + 1 before a = 2 * a and b = 2 * b before b = b + 1, giving (4, 3).

(3, 4) is impossible: $a = 3$ needs T2 to finish before T1 starts, while $b = 4$ needs T1 to finish before T2 starts. Options B, C and D all contain it.

Answer: A

\({S \to DHTU}\)	\(\{\ S.\mathit{val} = D.\mathit{val} + H.\mathit{val} + T.\mathit{val} + U.\mathit{val};\ \}\)
\({D \to \text{``M''}D_{1}}\)	\(\{\ D.\mathit{val} = 5 + D_{1}.\mathit{val};\ \}\)
\({D \to \epsilon}\)	\(\{\ D.\mathit{val} = -5;\ \}\)
\({H \to \text{``L''}H_{1}}\)	\(\{\ H.\mathit{val} = 5 * 10 + H_{1}.\mathit{val};\ \}\)
\({H \to \epsilon}\)	\(\{\ H.\mathit{val} = -10;\ \}\)
\({T \to \text{``C''}T_{1}}\)	\(\{\ T.\mathit{val} = 5 * 100 + T_{1}.\mathit{val};\ \}\)
\({T \to \epsilon}\)	\(\{\ T.\mathit{val} = -5;\ \}\)
\({U \to \text{``K''}}\)	\(\{\ U.\mathit{val} = 5;\ \}\)

\(\boldsymbol{R}\)
\(\boldsymbol{A}\)	\(\boldsymbol{B}\)
10	20
20	30
30	40
30	50
50	95

\(\boldsymbol{S}\)
\(\boldsymbol{A}\)	\(\boldsymbol{C}\)
10	90
30	45
40	80

Computer Science and Information Technology