GATE CS 2025 Set 2 - W3Colleges

Question 51

MSQ · 2 marks

Consider two grammars \(G_1\) and \(G_2\) with the production rules given below:

\(G_1\colon S \rightarrow \mathit{if}\ E\ \mathit{then}\ S \mid \mathit{if}\ E\ \mathit{then}\ S\ \mathit{else}\ S \mid a\)
\(\phantom{G_1\colon} E \rightarrow b\)

\(G_2\colon S \rightarrow \mathit{if}\ E\ \mathit{then}\ S \mid M\)
\(\phantom{G_2\colon} M \rightarrow \mathit{if}\ E\ \mathit{then}\ M\ \mathit{else}\ S \mid c\)
\(\phantom{G_2\colon} E \rightarrow b\)

where \(\mathit{if}, \mathit{then}, \mathit{else}, a, b, c\) are the terminals.

Which of the following option(s) is/are CORRECT?

\(G_1\) is not \(LL(1)\) and \(G_2\) is \(LL(1)\). \(G_1\) is \(LL(1)\) and \(G_2\) is not \(LL(1)\). \(G_1\) and \(G_2\) are not \(LL(1)\). \(G_1\) and \(G_2\) are ambiguous.

Explanation

Answer: (C), (D)

LL(1): in \(G_1\) two \(S\)-productions begin with \(\mathit{if}\). In \(G_2\), \(\mathrm{FIRST}(M) = \{\mathit{if}, c\}\) also contains \(\mathit{if}\), so on seeing \(\mathit{if}\) the parser cannot choose between \(S \rightarrow \mathit{if}\ E\ \mathit{then}\ S\) and \(S \rightarrow M\). Neither grammar is LL(1), so (C) holds and (A), (B) fail.

Ambiguity: \(G_1\) is the dangling-else grammar; \(\mathit{if}\ b\ \mathit{then}\ \mathit{if}\ b\ \mathit{then}\ a\ \mathit{else}\ a\) has two parse trees. \(G_2\) tries to force each \(\mathit{else}\) onto the nearest \(\mathit{if}\), but the \(\mathit{else}\) part of \(M\) is an \(S\), which may end in an unmatched \(\mathit{if}\). In \(\mathit{if}\ b\ \mathit{then}\ \mathit{if}\ b\ \mathit{then}\ c\ \mathit{else}\ \mathit{if}\ b\ \mathit{then}\ c\ \mathit{else}\ c\), the last \(\mathit{else}\) can pair with the first or the third \(\mathit{if}\), giving two parse trees. So (D) holds.

Answer: C, D

Question 52

MSQ · 2 marks

Let \(\Sigma = \{a, b, c\}\). For \(x \in \Sigma^{*}\), and \(\alpha \in \Sigma\), let \(\#_{\alpha}(x)\) denote the number of occurrences of \(\alpha\) in \(x\).

Which one or more of the following option(s) define(s) regular language(s)?

\(\{a^{m}b^{n} \mid m, n \ge 0\}\) \(\{a, b\}^{*} \cap \{a^{m}b^{n}c^{m-n} \mid m \ge n \ge 0\}\) \(\{w \mid w \in \{a, b\}^{*}, \#_{a}(w) \equiv 2 \pmod{7}, \text{ and } \#_{b}(w) \equiv 3 \pmod{9}\}\) \(\{w \mid w \in \{a, b\}^{*}, \#_{a}(w) \equiv 2 \pmod{7}, \text{ and } \#_{a}(w) = \#_{b}(w)\}\)

Explanation

Answer: (A), (C)

(A) is the language of \(a^{*}b^{*}\), so it is regular.
(B) Intersecting with \(\{a, b\}^{*}\) keeps only strings without \(c\), which forces \(m - n = 0\). What remains is \(\{a^{n}b^{n} \mid n \ge 0\}\), which is not regular.
(C) A DFA only has to track \(\#_{a}(w) \bmod 7\) and \(\#_{b}(w) \bmod 9\): a product of two cyclic counters with \(7 \times 9 = 63\) states. Regular.
(D) Requiring \(\#_{a}(w) = \#_{b}(w)\) needs an unbounded counter. If the language were regular, its intersection with \(a^{*}b^{*}\), namely \(\{a^{n}b^{n} \mid n \equiv 2 \pmod{7}\}\), would be regular too; the pumping lemma rules this out, because pumping inside the leading block of \(a\)'s changes the number of \(a\)'s but not of \(b\)'s.

Answer: A, C

Question 53

MSQ · 2 marks

Consider the database transactions T1 and T2, and data items X and Y. Which of the schedule(s) is/are conflict serializable?

Transaction T1
R1(X)
W1(Y)
R1(X)
W1(X)
COMMIT(T1)

Transaction T2
W2(X)
W2(Y)
COMMIT(T2)

R1(X), W2(X), W1(Y), W2(Y), R1(X), W1(X), COMMIT(T2), COMMIT(T1) W2(X), R1(X), W2(Y), W1(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1) R1(X), W1(Y), W2(X), W2(Y), R1(X), W1(X), COMMIT(T1), COMMIT(T2) W2(X), R1(X), W1(Y), W2(Y), R1(X), COMMIT(T2), W1(X), COMMIT(T1)

Explanation

Answer: (B)

Build the precedence graph. Two operations conflict when they come from different transactions, touch the same item and at least one is a write; the earlier one's transaction gets an edge to the later one's. Commits add no edges.

(A) R1(X) before W2(X) gives T1 → T2, but W2(X) before the second R1(X) gives T2 → T1. Cycle.
(B) W2(X) comes before both R1(X) operations and W1(X), and W2(Y) comes before W1(Y). Every edge is T2 → T1, so the graph is acyclic and the schedule is equivalent to the serial order T2, T1.
(C) W1(Y) before W2(Y) gives T1 → T2, while W2(X) before the second R1(X) gives T2 → T1. Cycle.
(D) W2(X) before R1(X) gives T2 → T1, while W1(Y) before W2(Y) gives T1 → T2. Cycle.

Answer: B

Question 54

MSQ · 2 marks

Consider the following relational schema:

Students (rollno: integer, name: string, age: integer, cgpa: real)

Courses (courseno: integer, cname: string, credits: integer)

Enrolled (rollno: integer, courseno: integer, grade: string)

Which of the following options is/are correct SQL query/queries to retrieve the names of the students enrolled in course number (i.e., courseno) 1470?

SELECT S.name
FROM Students S
WHERE EXISTS (SELECT * FROM Enrolled E
              WHERE E.courseno = 1470
                      AND E.rollno = S.rollno);

SELECT S.name
FROM Students S
WHERE SIZEOF (SELECT * FROM Enrolled E
              WHERE E.courseno = 1470
                      AND E.rollno = S.rollno) > 0;

SELECT S.name
FROM Students S
WHERE  0 < (SELECT COUNT(*)
            FROM Enrolled E
            WHERE E.courseno = 1470
                      AND E.rollno = S.rollno);

SELECT S.name
FROM Students S NATURAL JOIN Enrolled E
WHERE E.courseno = 1470;

Explanation

Answer: (A), (C), (D)

(A) For each student, the correlated EXISTS subquery is true exactly when an Enrolled row has that student's roll number and course 1470. Correct.
(B) SIZEOF is not an SQL operator or aggregate function, so this is not a valid query.
(C) The correlated COUNT(*) counts the student's enrolments in course 1470, and requiring it to be greater than 0 is the same test as (A). Correct.
(D) rollno is the only attribute common to Students and Enrolled, so the natural join pairs each student with their enrolments and the filter keeps course 1470. Because (rollno, courseno) is the key of Enrolled, each such student appears once. Correct.

Answer: A, C, D

Question 55

NAT · 2 marks

Given a computing system with two levels of cache (L1 and L2) and a main memory. The first level (L1) cache access time is 1 nanosecond (ns) and the “hit rate” for L1 cache is 90% while the processor is accessing the data from L1 cache. Whereas, for the second level (L2) cache, the “hit rate” is 80% and the “miss penalty” for transferring data from L2 cache to L1 cache is 10 ns. The “miss penalty” for the data to be transferred from main memory to L2 cache is 100 ns.

Then the average memory access time in this system in nanoseconds is ___________ . (rounded off to one decimal place)

Your answer

Explanation

Answer: 4

Every access pays the L1 time of 1 ns. The 10% of accesses that miss in L1 pay 10 ns to fetch from L2, and the 20% of those that also miss in L2 pay a further 100 ns to bring the data from main memory:

\[\text{AMAT} = 1 + 0.1 \times (10 + 0.2 \times 100) = 1 + 0.1 \times 30 = 4.0\ \text{ns}\]

A common slip is to charge the 100 ns to 20% of all accesses (giving 22 ns). It applies only to the \(0.1 \times 0.2 = 2\%\) of accesses that miss in both caches.

Answer: 4.0

Question 56

NAT · 2 marks

A 5-stage instruction pipeline has stage delays of 180, 250, 150, 170, and 250, respectively, in nanoseconds. The delay of an inter-stage latch is 10 nanoseconds. Assume that there are no pipeline stalls due to branches and other hazards. The time taken to process 1000 instructions in microseconds is __________ . (rounded off to two decimal places)

Your answer

Explanation

Answer: 260.2 to 261.2

The clock must fit the slowest stage plus a latch: \(T = 250 + 10 = 260\) ns.

With no stalls, the first instruction takes 5 cycles to pass through the pipeline and each of the other 999 instructions finishes one cycle after the previous one:

\[(5 + 1000 - 1) \times 260 = 1004 \times 260 = 261040\ \text{ns} = 261.04\ \mu\text{s}\]

Using the average stage delay, or leaving out the latch delay, gives a clock that is too short: every stage advances in lockstep, so the slowest stage sets the pace.

Answer: 261.04

Question 57

NAT · 2 marks

In a B⁺- tree where each node can hold at most four key values, a root to leaf path consists of the following nodes:

A = (49, 77, 83, -), B = (7, 19, 33, 44), C = (20*, 22*, 25*, 26*)

The *-marked keys signify that these are data entries in a leaf.

Assume that a pointer between keys \(k_1\) and \(k_2\) points to a subtree containing keys in \([k_1, k_2)\), and that when a leaf is created, the smallest key in it is copied up into its parent.

A record with key value 23 is inserted into the B⁺- tree.

The smallest key value in the parent of the leaf that contains 25* is __________. (Answer in integer)

Your answer

Explanation

Answer: 33

Key 23 goes to leaf C: B is the child of A for keys below 49, and C is B's child for \([19, 33)\). C is full, so the five keys 20, 22, 23, 25, 26 split into two leaves, and the smallest key of the new right leaf (23 for a 2 + 3 split, 25 for a 3 + 2 split) is copied into B.

B now has five keys, one too many, so it splits as well: its middle key (the one just copied up) moves to A, which has room, leaving (7, 19) on the left and (33, 44) on the right. The leaf holding 25* lies to the right of the promoted key, so its parent is (33, 44).

Both ways of splitting the leaf give the same parent, whose smallest key is 33.

Answer: 33

Question 58

NAT · 2 marks

A computer system supports a logical address space of \(2^{32}\) bytes. It uses two-level hierarchical paging with a page size of 4096 bytes. A logical address is divided into a \(b\)-bit index to the outer page table, an offset within the page of the inner page table, and an offset within the desired page. Each entry of the inner page table uses eight bytes. All the pages in the system have the same size.

The value of \(b\) is ___________ . (Answer in integer)

Your answer

Explanation

Answer: 11

Split the 32-bit logical address from the right:

Offset within the desired page: \(4096 = 2^{12}\) bytes, so 12 bits.
Offset within a page of the inner page table: one page holds \(4096 / 8 = 512 = 2^{9}\) eight-byte entries, so 9 bits.
Outer page table index: whatever is left, \(b = 32 - 12 - 9 = 11\).

So the outer page table has \(2^{11} = 2048\) entries, each pointing to one page of the inner page table.

Answer: 11

Question 59

NAT · 2 marks

Consider the following algorithm someAlgo that takes an undirected graph \(G\) as input.

someAlgo(\(G\))

Let \(v\) be any vertex in \(G\). Run BFS on \(G\) starting at \(v\). Let \(u\) be a vertex in \(G\) at maximum distance from \(v\) as given by the BFS.
Run BFS on \(G\) again with \(u\) as the starting vertex. Let \(z\) be the vertex at maximum distance from \(u\) as given by the BFS.
Output the distance between \(u\) and \(z\) in \(G\).

The output of someAlgo(\(T\)) for the tree shown in the given figure is ___________. (Answer in integer)

A tree with 14 vertices drawn as dots joined by edges. One vertex is joined to a leaf, to a vertex with two further leaves, to a vertex with one further leaf, and to a second branching vertex; that second vertex has two leaves and one more neighbour, which has a leaf and a two-edge path hanging from it.

Your answer

Explanation

Answer: 6

On a tree, a vertex farthest from any start vertex is always an end of a longest path, so the second BFS measures the tree's diameter: the largest distance, in edges, between two vertices.

In the figure, a longest path starts at the lowest leaf on the far left, goes up to its neighbour and the left branching vertex, crosses to the central branching vertex, and follows the right branch through two more vertices to the rightmost leaf: 6 edges. The topmost leaf also reaches the rightmost leaf in 6 edges, and no two vertices are farther apart.

So the output is 6 whichever start vertex \(v\) is chosen.

Answer: 6

Question 60

NAT · 2 marks

Let \(\Sigma = \{1,2,3,4\}\). For \(x \in \Sigma^{*}\), let \(\mathit{prod}(x)\) be the product of symbols in \(x\) modulo 7. We take \(\mathit{prod}(\epsilon) = 1\), where \(\epsilon\) is the null string.

For example, \(\mathit{prod}(124) = (1 \times 2 \times 4) \bmod 7 = 1\).

Define \(L = \{x \in \Sigma^{*} \mid \mathit{prod}(x) = 2\}\).

The number of states in a minimum state DFA for \(L\) is ___________. (Answer in integer)

Your answer

Explanation

Answer: 6

A DFA only needs the product read so far as a residue mod 7, with residue 2 accepting. No symbol is a multiple of 7 and 7 is prime, so the product never becomes 0 and no dead state is needed. All six non-zero residues are reachable from the start state 1: 1, 2, 3, 4 directly, \(3 \times 4 \equiv 5\) and \(2 \times 3 = 6\).

The six states are pairwise distinguishable. For residues \(r \ne s\), take a string \(y\) with \(\mathit{prod}(y) \equiv 2r^{-1} \pmod{7}\) (one exists, since every non-zero residue is reachable). It takes \(r\) to 2 and accepts, but takes \(s\) to \(2sr^{-1} \not\equiv 2\) and rejects.

So the minimum DFA has 6 states.

Answer: 6

Computer Science and Information Technology