The ratio of boys to girls in a class is 7 to 3. Among the options below, an acceptable value for the total number of students in the class is:

C. Boys : girls = 7:3, so the total is a multiple of 7+3=10. Among the options only 50 is a multiple of 10.

A polygon is convex if, for every pair of points P and Q belonging to the polygon, the line segment PQ lies completely inside or on the polygon. Which one of the following is NOT a convex polygon? (See the figure for options (A)–(D).)

A. Shape (A) is an arrow/chevron with a reflex (inward) vertex, so a segment joining two points can pass outside the shape — it is concave. The triangle, square and trapezium are all convex.

Consider the following sentences: (i) Everybody in the class is prepared for the exam. (ii) Babu invited Danish to his home because he enjoys playing chess. Which of the following is the CORRECT observation about the above two sentences?

C. Sentence (i) is grammatically correct ("everybody" takes a singular verb "is"). In (ii) the pronoun "he" can refer either to Babu or to Danish, so it is ambiguous.

A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like ______. (See the figure for the folding sequence and options (A)–(D).)

A. Unfolding reflects each punched hole across the two fold lines. Reversing the two folds reproduces the pattern of option (A).

______ is to *surgery* as *writer* is to ______. Which one of the following options maintains a similar logical relation in the above sentence?

C. A doctor performs surgery; a writer produces a book. "Doctor : surgery :: writer : book" preserves the agent–product/activity relation.

We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm \times 1 cm each. Sheet M is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet N is cut into equal square patches and assembled to form the largest possible closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that of the cube is ______

C. Rolling M (bringing the 1 cm short edges together) gives circumference 2\pi r = 6 \Rightarrow r = 3/\pi and height 1, so V_{cyl}=\pi r^2 h = \pi\cdot\frac{9}{\pi^2} = \frac{9}{\pi}. Sheet N has area 6, giving six 1\times1 faces, i.e. a unit cube with V_{cube}=1. Ratio =\frac{9}{\pi}.

Details of prices of two items P and Q are presented in the table below. The ratio of cost of item P to cost of item Q is 3:4. Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost, i.e. \text{Profit \%} = \frac{\text{Selling price}-\text{Cost}}{\text{Cost}}\times 100. Items Cost (Rs) Profit % Marked Price (Rs) P 5,400 --- 5,860 Q --- 25 10,000 The dis

C. Cost of P = 5400, and cost P : cost Q = 3 : 4, so cost of Q = 5400\times\frac{4}{3}=7200. Profit 25% gives selling price of Q =7200\times1.25=9000. Discount =10000-9000=1000, which is \frac{1000}{10000}\times100=10\% of the marked price.

There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag. The probability that at least two chocolates are identical is ______

C. P(all five distinct) =\frac{10\cdot9\cdot8\cdot7\cdot6}{10^5}=\frac{30240}{100000}=0.3024. Hence P(at least two identical) =1-0.3024=0.6976.

Given below are two statements 1 and 2, and two conclusions I and II. Statement 1: All bacteria are microorganisms. Statement 2: All pathogens are microorganisms. Conclusion I: Some pathogens are bacteria. Conclusion II: All pathogens are not bacteria. Based on the above statements and conclusions, which one of the following options is logically CORRECT?

C, D. From the two statements, pathogens and bacteria are both subsets of microorganisms but their overlap is not fixed; conclusions I and II form a complementary pair, so "Either I or II" holds. The official GATE key accepted both options (C) and (D).

Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality. Which one of the following statements summarizes the passage?

D. The passage says the measures "sidestep" the core causes (poverty and income inequality) — i.e., they address the problem only superficially.

Suppose that L_1 is a regular language and L_2 is a context-free language. Which one of the following languages is NOT necessarily context-free?

C. Regular \cap CFL, regular \cdot CFL and regular \cup CFL are all CFLs. But L_1-L_2 = L_1 \cap \overline{L_2}, and the complement of a CFL need not be a CFL, so L_1-L_2 is not necessarily context-free.

Let P be an array containing n integers. Let t be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of n elements. Which one of the following choices is correct?

C. The tournament (pair-wise) method finds both min and max using at most 3\lceil n/2\rceil - 2 \le 3\lceil n/2\rceil comparisons, and more than n are needed, so t > n and t \le 3\lceil n/2\rceil.

Consider the following three functions. f_1 = 10^n \qquad f_2 = n^{\log n} \qquad f_3 = n^{\sqrt{n}} Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?

D. Take logs: \log f_1 = n\log 10 = \Theta(n), \log f_2 = (\log n)^2, \log f_3 = \sqrt{n}\,\log n. Order of these: (\log n)^2 < \sqrt{n}\log n < n, so f_2 < f_3 < f_1.

Consider the following statements. S_1: The sequence of procedure calls corresponds to a preorder traversal of the activation tree. S_2: The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct?

C. In an activation tree, calls happen in preorder (a procedure is entered before its callees) and returns happen in postorder (a procedure returns after all its callees). Both statements are true.

Consider the following statements. S_1: Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). S_2: For any context-free grammar, there is a parser that takes at most O(n^3) time to parse a string of length n. Which one of the following options is correct?

C. Every SLR(1) grammar is unambiguous, and some unambiguous grammars are not SLR(1) — S_1 is true. The CYK algorithm parses any CFG in O(n^3) time — S_2 is true.

Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?

A. (210)_3 = 2\cdot9 + 1\cdot3 + 0 = 21_{10} = (15)_{16}.

Let p and q be two propositions. Consider the following two formulae in propositional logic. S_1: (\neg p \wedge (p \vee q)) \rightarrow q S_2: q \rightarrow (\neg p \wedge (p \vee q)) Which one of the following choices is correct?

B. \neg p \wedge (p\vee q) \equiv \neg p \wedge q. So S_1 \equiv (\neg p\wedge q)\rightarrow q, which is always true — a tautology. S_2 \equiv q\rightarrow(\neg p\wedge q) fails when q is true and p is true, so S_2 is not a tautology.

Consider the following two statements. S_1: Destination MAC address of an ARP reply is a broadcast address. S_2: Destination MAC address of an ARP request is a broadcast address. Which one of the following choices is correct?

C. An ARP request is broadcast (the sender does not yet know the target MAC), so S_2 is true. An ARP reply is unicast back to the requester, so S_1 is false.

Consider the following array. 23 32 45 69 72 73 89 97 Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?

C. The array is already sorted. Insertion sort on an already-sorted array performs only n-1 comparisons (best case), fewer than the others.

A binary search tree T contains n distinct elements. What is the time complexity of picking an element in T that is smaller than the maximum element in T?

D. The maximum is the right-most node, so the root (for n\ge2) is not the maximum. Returning the root (or any fixed non-maximum node) takes \Theta(1) time.

In the context of operating systems, which of the following statements is/are correct with respect to paging?

A, C. Paging eliminates external fragmentation (A, true) and needs page tables, i.e. memory overhead (C, true). Larger pages increase internal fragmentation, so (B) is false; multi-level paging reduces page-table size and is unrelated to supporting different page sizes, so (D) is false.

Let \langle M\rangle denote an encoding of an automaton M. Suppose that \Sigma = \{0,1\}. Which of the following languages is/are NOT recursive?

D. DFA emptiness, DFA universality and PDA emptiness are all decidable (recursive). PDA/CFG universality (L(M)=\Sigma^*) is undecidable, so (D) is not recursive.

Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?

A. Without checkpointing, recovery restarts from the beginning of the log and recomputes the same undo and redo lists. Recovery operations are idempotent, so the system recovers correctly — only (A) is correct.

Which of the following standard C library functions will *always* invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?

A, C. exit always triggers the exit/_exit system call and sleep always invokes a kernel timer (e.g. nanosleep). malloc may satisfy a request from the existing heap without a syscall, and strlen is pure user-space computation.

Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo. Which of the following operations will necessarily require a full scan of foo for successful completion?

A, C. Creating a new file must confirm the name does not already exist, requiring a full scan (A). Renaming must find the file and confirm the new name is unused, requiring a full scan (C). Deleting and opening can stop as soon as the file is found, so they do not necessarily scan the whole list.

In an undirected connected planar graph G, there are eight vertices and five faces. The number of edges in G is ______.

11. Euler's formula: V-E+F=2 \Rightarrow 8-E+5=2 \Rightarrow E=11.

Consider the undirected graph with edge weights as shown in the figure. The number of minimum-weight spanning trees of the graph is ______.

3. The minimum spanning tree has weight formed by the small (0.1) edges; counting the ways to complete an MST while breaking ties among equal-weight edges gives 3 distinct minimum-weight spanning trees.

The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is ______.

0.35 to 0.39. For X\sim \text{Exp}(\lambda=2), E[X]=1/2. P(X>1/2)=e^{-\lambda\cdot(1/2)}=e^{-1}\approx 0.37.

There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: - The fastest computer gets the toughest job and the slowest computer gets the easiest job. - Every computer gets at least one job. The number of ways in which this can be done is ______.

65. Fix the toughest job to the fastest computer and the easiest to the slowest. The remaining 4 jobs go to 3 computers (with the "at least one each" condition already handled), giving 65 valid assignments.

Consider the following expression. \lim_{x\to -3}\frac{\sqrt{2x+22}-4}{x+3} The value of the above expression (rounded to 2 decimal places) is ______.

0.25. This is 0/0; rationalizing (or L'Hopital) gives \frac{1}{\sqrt{2x+22}} at x=-3, i.e. \frac{1}{\sqrt{16}}=\frac{1}{4}=0.25.

Consider the following sequence of operations on an empty stack. push(54); push(52); pop(); push(55); push(62); s = pop(); Consider the following sequence of operations on an empty queue. enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue(); The value of s + q is ______.

86. Stack: after the operations the top popped into s is 62. Queue (FIFO): the second dequeue returns 24, so q=24. Hence s+q=62+24=86.

Consider a computer system with a byte-addressable primary memory of size 2^{32} bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB = 2^{10} bytes), and each cache block is of size 64 bytes. The size of the tag field is ______ bits.

17. Offset =\log_2 64 = 6 bits. Number of lines = 2^{15}/2^6 = 2^9, so index =9 bits. Tag =32-6-9=17 bits.

A relation r(A,B) in a relational database has 1200 tuples. The attribute A has integer values ranging from 6 to 20, and the attribute B has integer values ranging from 1 to 20. Assume that the attributes A and B are independently distributed. The estimated number of tuples in the output of \sigma_{(A>10)\vee(B=18)}(r) is ______.

205 to 820. With A\in[6,20] (15 values) and B\in[1,20] (20 values), P(A>10)=10/15 and P(B=18)=1/20. Using inclusion–exclusion on the estimate gives about 819–820 tuples. (The official GATE key accepted either 819–820 or 205.)

Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127. S:1 \qquad E:10000001 \qquad F:11110000000000000000000 Here S, E and F denote the sign, exponent and fraction components of the floating point representation. The decimal value corresponding to the above representation (rounded to 2 decimal places) is ______.

-7.75. S=1 (negative). E=(10000001)_2=129, so exponent =129-127=2. Mantissa =1.1111_2 = 1.9375. Value =-1.9375\times2^2 = -7.75.

Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is ______ milliseconds.

12. Shortest-Job-First minimizes average waiting time. Order 10, 16, 20: waiting times are 0, 10, 26; average =(0+10+26)/3 = 12 ms.

Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code: P -> D* E* D -> int ID { record that ID.lexeme is of type int } D -> bool ID { record that ID.lexeme is of type bool } E -> E1 + E2 { check that E1.type = E2.type = int; set E.type := int } E -> ! E1 { check that E1.type = bool; set E.type := bool } E -> ID { set E.type := int } With respect to the above grammar, which

B. The rule E\to ID unconditionally sets type int, ignoring a bool declaration, so boolean expressions are not correctly checked. The actions only reliably type-check integer declarations and integer expressions.

The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key: empAge(\underline{empNo}, age) Consider the following relational algebra expression: \Pi_{empNo}\big(empAge \bowtie_{(age>age1)} \rho_{empNo1, age1}(empAge)\big) What does the above expression generate?

C. The join pairs an employee with any other employee of smaller age. An employee appears in the result iff there exists someone younger, i.e. the employee's age is not the minimum.

Consider a 3-bit counter, designed using T flip-flops, as shown in the figure. Assuming the initial state of the counter given by PQR as 000, what are the next three states?

A. Deriving the T inputs from the circuit and applying them from PQR = 000 produces the state sequence 011, 101, 000.

Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is d_8 d_7 d_6 d_5 c_8 d_4 d_3 d_2 c_4 d_1 c_2 c_1, where the data bits and the check bits are given in the following tables: Data bits: d8 d7 d6 d5 d4 d3 d2 d1 1 1 0 x 0 1 0 1 Check bits: c8 c4 c2 c1 y 0 1 0 Which one of the following choices gives the correct values of x and y?

A. Using even parity over the Hamming check-bit positions and solving the parity equations for the unknown data bit x and check bit y gives x=0 and y=0.

Consider the following recurrence relation. T(n) = \begin{cases} T(n/2) + T(2n/5) + 7n & \text{if } n>0 \\ 1 & \text{if } n=0 \end{cases} Which one of the following options is correct?

C. The subproblem sizes sum to \frac{1}{2}+\frac{2}{5}=\frac{9}{10}<1. With linear work per level and a geometrically shrinking total, the work is dominated by the top level, giving T(n)=\Theta(n).

Consider the following context-free grammar where the set of terminals is \{a,b,c,d,f\}. S -> d a T | R f T -> a S | b a T | e R -> c a T R | e (e denotes epsilon) The following is a partially-filled LL(1) parsing table; the numbered cells (1), (2), (3), (4) are to be filled (blank denotes an empty cell): a b c d f S (1) S->daT (2) T T->aS T->baT (3) T->e (4) R R->caTR R->e Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank"

A. Computing FIRST and FOLLOW sets: R is nullable with c\in FIRST(caTR), so S\to Rf is entered under both c and f (cells 1 and 2). T is nullable, and FOLLOW(T) contains c and \, so T\to \epsilon is entered in cells 3 and 4. This matches option (A).

Let r_i(z) and w_i(z) denote read and write operations respectively on a data item z by a transaction T_i. Consider the following two schedules. S_1: r_1(x)\; r_1(y)\; r_2(x)\; r_2(y)\; w_2(y)\; w_1(x) S_2: r_1(x)\; r_2(x)\; r_2(y)\; w_2(y)\; r_1(y)\; w_1(x) Which one of the following options is correct?

B. Drawing precedence graphs: S_1 has a cycle between T_1 and T_2 (conflicts on x and y in opposite order), so it is not conflict serializable. S_2 has an acyclic precedence graph (T_2\to T_1), so it is conflict serializable.

Consider the relation R(P,Q,S,T,X,Y,Z,W) with the following functional dependencies. PQ\to X; \quad P\to YX; \quad Q\to Y; \quad Y\to ZW Consider the decomposition of the relation R into the constituent relations according to the following two decomposition schemes. D_1: R = [(P,Q,S,T);\ (P,T,X);\ (Q,Y);\ (Y,Z,W)] D_2: R = [(P,Q,S);\ (T,X);\ (Q,Y);\ (Y,Z,W)] Which one of the following options is correct?

A. Testing each decomposition with the chase/common-attribute test, D_1 joins back to R losslessly, while D_2 loses information (the (T,X) split has no FD linking it back), so D_2 is lossy.

Let G be a group of order 6, and H be a subgroup of G such that 1 < |H| < 6. Which one of the following options is correct?

B. By Lagrange, |H|\in\{2,3\}, both prime, so H is cyclic. G of order 6 can be the non-abelian S_3, which is not cyclic. Hence H is always cyclic but G may not be.

Consider the two statements. S_1: There exist random variables X and Y such that \big(\mathbb{E}[(X-\mathbb{E}(X))(Y-\mathbb{E}(Y))]\big)^2 > \text{Var}[X]\,\text{Var}[Y]. S_2: For all random variables X and Y, \text{Cov}[X,Y] = \mathbb{E}\big[\,|X-\mathbb{E}[X]|\;|Y-\mathbb{E}[Y]|\,\big]. Which one of the following choices is correct?

D. By Cauchy–Schwarz, \text{Cov}(X,Y)^2 \le \text{Var}(X)\text{Var}(Y), so S_1 is false. Covariance uses signed deviations, not absolute values, so S_2 is false too.

Let G=(V,E) be an undirected unweighted connected graph. The *diameter* of G is defined as: \text{diam}(G) = \max_{u,v\in V}\{\text{the length of shortest path between } u \text{ and } v\} Let M be the adjacency matrix of G. Define graph G_2 on the same set of vertices with adjacency matrix N, where N_{ij} = 1 if M_{ij} > 0 or P_{ij} > 0 (where P = M^2), and 0 otherwise. Which one of the following statements is true?

A. G_2 connects any two vertices within distance 2 in G, so every edge in G_2 corresponds to a path of length \le2 in G. Distances halve (with ceiling), giving \text{diam}(G_2)\le\lceil \text{diam}(G)/2\rceil.

Consider the following ANSI C program. #include int main() { int i, j, count; count = 0; i = 0; for (j = -3; j = 0) && (i++)) count = count + j; } count = count + i; printf("%d", count); return 0; } Which one of the following options is correct?

B. For j<0 the first operand is false and i++ is not evaluated. For j=0: i++ returns 0 (false) then i=1, so count unchanged. For j=1,2,3: i++ returns 1,2,3 (true), count becomes 1,3,6 and i reaches 4. Final count =6+i=6+4=10.

Consider the following language. L = \{w \in \{0,1\}^* \mid w \text{ ends with the substring } 011\} Which one of the following deterministic finite automata accepts L? (See the figure for options (A)–(D).)

D. A correct DFA for strings ending in 011 needs the accepting state reached only after reading 0,1,1 in order, with proper back-transitions on mismatches. Only option (D) has the correct transitions and single accepting state for this pattern.

For a Turing machine M, \langle M\rangle denotes an encoding of M. Consider the following two languages. L_1 = \{\langle M\rangle \mid M \text{ takes more than 2021 steps on all inputs}\} L_2 = \{\langle M\rangle \mid M \text{ takes more than 2021 steps on some input}\} Which one of the following options is correct?

A. In at most 2021 steps a TM can read only the first 2021 input cells, so the behaviour depends on finitely many input prefixes. Both conditions can be checked by simulating M for 2021 steps on these finitely many relevant inputs, so both L_1 and L_2 are decidable.

Define R_n to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i>0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices: p[1]=1,\ p[2]=5,\ p[3]=8,\ p[4]=9,\ p[5]=10,\ p[6]=17,\ p[7]=18 Which of the following statements is/are correct about R_7?

A, C. The optimal revenue is R_7=18, achievable as 7, or 2+5 (5+10=... ) — in fact three distinct cuts give 18: \{7\}, \{1,6\}, \{2,2,3\}. So R_7=18 (A) and it is achieved by three different solutions (C).

An *articulation point* in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let T be a DFS tree obtained by doing DFS in a connected undirected graph G. Which of the following options is/are correct?

B, D. The DFS-tree characterization: the root is an articulation point iff it has \ge 2 children (B true, A false). A leaf is never an articulation point (C false). The ancestor–descendant separation property (D) holds for any articulation point. The official key is (B), (D).

GATE CS 2021 Set 1 — All 65 Questions with Solutions

Computer Science (CS). Every question from this paper with the official answer key and a step-by-step solution. 100 marks total.

Attempt in GATE exam mode →All papers

Question 1General Aptitudemcq1 mark
The ratio of boys to girls in a class is 7 to 3. Among the options below, an acceptable value for the total number of students in the class is:
- A.
  21
- B.
  37
- C.
  50
  ✓
- D.
  73
Answer: C
Solution
Boys : girls $= 7 : 3$ , so the total is a multiple of $7 + 3 = 10$ . Among the options only $50$ is a multiple of $10$ .
Question 2General Aptitudemcq1 mark
A polygon is convex if, for every pair of points $P$ and $Q$ belonging to the polygon, the line segment $P Q$ lies completely inside or on the polygon. Which one of the following is NOT a convex polygon? (See the figure for options (A)–(D).)
- A.
  (A)
  ✓
- B.
  (B)
- C.
  (C)
- D.
  (D)
Answer: A
Solution
Shape (A) is an arrow/chevron with a reflex (inward) vertex, so a segment joining two points can pass outside the shape — it is concave. The triangle, square and trapezium are all convex.
Question 3General Aptitudemcq1 mark
Consider the following sentences: (i) Everybody in the class is prepared for the exam. (ii) Babu invited Danish to his home because he enjoys playing chess. Which of the following is the CORRECT observation about the above two sentences?
- A.
  (i) is grammatically correct and (ii) is unambiguous
- B.
  (i) is grammatically incorrect and (ii) is unambiguous
- C.
  (i) is grammatically correct and (ii) is ambiguous
  ✓
- D.
  (i) is grammatically incorrect and (ii) is ambiguous
Answer: C
Solution
Sentence (i) is grammatically correct ("everybody" takes a singular verb "is"). In (ii) the pronoun "he" can refer either to Babu or to Danish, so it is ambiguous.
Question 4General Aptitudemcq1 mark
A circular sheet of paper is folded along the lines in the directions shown. The paper, after being punched in the final folded state as shown and unfolded in the reverse order of folding, will look like ______. (See the figure for the folding sequence and options (A)–(D).)
- A.
  (A)
  ✓
- B.
  (B)
- C.
  (C)
- D.
  (D)
Answer: A
Solution
Unfolding reflects each punched hole across the two fold lines. Reversing the two folds reproduces the pattern of option (A).
Question 5General Aptitudemcq1 mark
______ is to *surgery* as *writer* is to ______. Which one of the following options maintains a similar logical relation in the above sentence?
- A.
  Plan, outline
- B.
  Hospital, library
- C.
  Doctor, book
  ✓
- D.
  Medicine, grammar
Answer: C
Solution
A doctor performs surgery; a writer produces a book. "Doctor : surgery :: writer : book" preserves the agent–product/activity relation.
Question 6General Aptitudemcq2 marks
We have 2 rectangular sheets of paper, M and N, of dimensions 6 cm $\times$ 1 cm each. Sheet M is rolled to form an open cylinder by bringing the short edges of the sheet together. Sheet N is cut into equal square patches and assembled to form the largest possible closed cube. Assuming the ends of the cylinder are closed, the ratio of the volume of the cylinder to that of the cube is ______
- A.
  $\frac{π}{2}$
- B.
  $\frac{3}{π}$
- C.
  $\frac{9}{π}$
  ✓
- D.
  $3 π$
Answer: C
Solution
Rolling M (bringing the 1 cm short edges together) gives circumference $2 π r = 6 \Rightarrow r = 3/ π$ and height $1$ , so $V_{cy l} = π r^{2} h = π \cdot \frac{9}{π ^{2}} = \frac{9}{π}$ . Sheet N has area 6, giving six $1 \times 1$ faces, i.e. a unit cube with $V_{c u b e} = 1$ . Ratio $= \frac{9}{π}$ .
Question 7General Aptitudemcq2 marks
Details of prices of two items P and Q are presented in the table below. The ratio of cost of item P to cost of item Q is 3:4. Discount is calculated as the difference between the marked price and the selling price. The profit percentage is calculated as the ratio of the difference between selling price and cost, to the cost, i.e. $Profit % = \frac{Selling price - Cost}{Cost} \times 100$ .
```
Items   Cost (Rs)   Profit %   Marked Price (Rs)
  P       5,400       ---           5,860
  Q        ---         25          10,000
```
The discount on item Q, as a percentage of its marked price, is ______
- A.
  25
- B.
  12.5
- C.
  10
  ✓
- D.
  5
Answer: C
Solution
Cost of P = 5400, and cost P : cost Q = 3 : 4, so cost of Q $= 5400 \times \frac{4}{3} = 7200$ . Profit 25% gives selling price of Q $= 7200 \times 1.25 = 9000$ . Discount $= 10000 - 9000 = 1000$ , which is $\frac{1000}{10000} \times 100 = 10%$ of the marked price.
Question 8General Aptitudemcq2 marks
There are five bags each containing identical sets of ten distinct chocolates. One chocolate is picked from each bag. The probability that at least two chocolates are identical is ______
- A.
  0.3024
- B.
  0.4235
- C.
  0.6976
  ✓
- D.
  0.8125
Answer: C
Solution
P(all five distinct) $= \frac{10 \cdot 9 \cdot 8 \cdot 7 \cdot 6}{1 0 ^{5}} = \frac{30240}{100000} = 0.3024$ . Hence P(at least two identical) $= 1 - 0.3024 = 0.6976$ .
Question 9General Aptitudemcq2 marks
Given below are two statements 1 and 2, and two conclusions I and II. Statement 1: All bacteria are microorganisms. Statement 2: All pathogens are microorganisms. Conclusion I: Some pathogens are bacteria. Conclusion II: All pathogens are not bacteria. Based on the above statements and conclusions, which one of the following options is logically CORRECT?
- A.
  Only conclusion I is correct
- B.
  Only conclusion II is correct
- C.
  Either conclusion I or II is correct.
  ✓
- D.
  Neither conclusion I nor II is correct.
  ✓
Answer: C, D
Solution
From the two statements, pathogens and bacteria are both subsets of microorganisms but their overlap is not fixed; conclusions I and II form a complementary pair, so "Either I or II" holds. The official GATE key accepted both options (C) and (D).
Question 10General Aptitudemcq2 marks
Some people suggest anti-obesity measures (AOM) such as displaying calorie information in restaurant menus. Such measures sidestep addressing the core problems that cause obesity: poverty and income inequality. Which one of the following statements summarizes the passage?
- A.
  The proposed AOM addresses the core problems that cause obesity.
- B.
  If obesity reduces, poverty will naturally reduce, since obesity causes poverty.
- C.
  AOM are addressing the core problems and are likely to succeed.
- D.
  AOM are addressing the problem superficially.
  ✓
Answer: D
Solution
The passage says the measures "sidestep" the core causes (poverty and income inequality) — i.e., they address the problem only superficially.
Question 11Theory of Computationmcq1 mark
Suppose that $L_{1}$ is a regular language and $L_{2}$ is a context-free language. Which one of the following languages is NOT necessarily context-free?
- A.
  $L_{1} \cap L_{2}$
- B.
  $L_{1} \cdot L_{2}$
- C.
  $L_{1} - L_{2}$
  ✓
- D.
  $L_{1} \cup L_{2}$
Answer: C
Solution
Regular $\cap$ CFL, regular $\cdot$ CFL and regular $\cup$ CFL are all CFLs. But $L_{1} - L_{2} = L_{1} \cap L_{2}$ , and the complement of a CFL need not be a CFL, so $L_{1} - L_{2}$ is not necessarily context-free.
Question 12Algorithmsmcq1 mark
Let P be an array containing $n$ integers. Let $t$ be the lowest upper bound on the number of comparisons of the array elements, required to find the minimum and maximum values in an arbitrary array of $n$ elements. Which one of the following choices is correct?
- A.
  $t > 2 n - 2$
- B.
  $t > 3 ⌈ \frac{n}{2} ⌉$ and $t \leq 2 n - 2$
- C.
  $t > n$ and $t \leq 3 ⌈ \frac{n}{2} ⌉$
  ✓
- D.
  $t > ⌈ lo g_{2} n ⌉$ and $t \leq n$
Answer: C
Solution
The tournament (pair-wise) method finds both min and max using at most $3 ⌈ n /2 ⌉ - 2 \leq 3 ⌈ n /2 ⌉$ comparisons, and more than $n$ are needed, so $t > n$ and $t \leq 3 ⌈ n /2 ⌉$ .
Question 13Algorithmsmcq1 mark
Consider the following three functions.
$f_{1} = 1 0^{n} f_{2} = n^{l o g n} f_{3} = n^{n}$
Which one of the following options arranges the functions in the increasing order of asymptotic growth rate?
- A.
  $f_{3}, f_{2}, f_{1}$
- B.
  $f_{2}, f_{1}, f_{3}$
- C.
  $f_{1}, f_{2}, f_{3}$
- D.
  $f_{2}, f_{3}, f_{1}$
  ✓
Answer: D
Solution
Take logs: $lo g f_{1} = n lo g 10 = Θ (n)$ , $lo g f_{2} = (lo g n)^{2}$ , $lo g f_{3} = n lo g n$ . Order of these: $(lo g n)^{2} < n lo g n < n$ , so $f_{2} < f_{3} < f_{1}$ .
Question 14Compiler Designmcq1 mark
Consider the following statements. $S_{1}$ : The sequence of procedure calls corresponds to a preorder traversal of the activation tree. $S_{2}$ : The sequence of procedure returns corresponds to a postorder traversal of the activation tree. Which one of the following options is correct?
- A.
  $S_{1}$ is true and $S_{2}$ is false
- B.
  $S_{1}$ is false and $S_{2}$ is true
- C.
  $S_{1}$ is true and $S_{2}$ is true
  ✓
- D.
  $S_{1}$ is false and $S_{2}$ is false
Answer: C
Solution
In an activation tree, calls happen in preorder (a procedure is entered before its callees) and returns happen in postorder (a procedure returns after all its callees). Both statements are true.
Question 15Compiler Designmcq1 mark
Consider the following statements. $S_{1}$ : Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1). $S_{2}$ : For any context-free grammar, there is a parser that takes at most $O (n^{3})$ time to parse a string of length $n$ . Which one of the following options is correct?
- A.
  $S_{1}$ is true and $S_{2}$ is false
- B.
  $S_{1}$ is false and $S_{2}$ is true
- C.
  $S_{1}$ is true and $S_{2}$ is true
  ✓
- D.
  $S_{1}$ is false and $S_{2}$ is false
Answer: C
Solution
Every SLR(1) grammar is unambiguous, and some unambiguous grammars are not SLR(1) — $S_{1}$ is true. The CYK algorithm parses any CFG in $O (n^{3})$ time — $S_{2}$ is true.
Question 16Digital Logicmcq1 mark
Let the representation of a number in base 3 be 210. What is the hexadecimal representation of the number?
- A.
  15
  ✓
- B.
  21
- C.
  D2
- D.
  528
Answer: A
Solution
$(210)_{3} = 2 \cdot 9 + 1 \cdot 3 + 0 = 2 1_{10} = (15)_{16}$ .
Question 17Discrete Mathematicsmcq1 mark
Let $p$ and $q$ be two propositions. Consider the following two formulae in propositional logic.
$S_{1} : (\neg p \land (p \lor q)) \to q$

$S_{2} : q \to (\neg p \land (p \lor q))$
Which one of the following choices is correct?
- A.
  Both $S_{1}$ and $S_{2}$ are tautologies.
- B.
  $S_{1}$ is a tautology but $S_{2}$ is not a tautology.
  ✓
- C.
  $S_{1}$ is not a tautology but $S_{2}$ is a tautology.
- D.
  Neither $S_{1}$ nor $S_{2}$ is a tautology.
Answer: B
Solution
$\neg p \land (p \lor q) \equiv \neg p \land q$ . So $S_{1} \equiv (\neg p \land q) \to q$ , which is always true — a tautology. $S_{2} \equiv q \to (\neg p \land q)$ fails when $q$ is true and $p$ is true, so $S_{2}$ is not a tautology.
Question 18Computer Networksmcq1 mark
Consider the following two statements. $S_{1}$ : Destination MAC address of an ARP reply is a broadcast address. $S_{2}$ : Destination MAC address of an ARP request is a broadcast address. Which one of the following choices is correct?
- A.
  Both $S_{1}$ and $S_{2}$ are true.
- B.
  $S_{1}$ is true and $S_{2}$ is false.
- C.
  $S_{1}$ is false and $S_{2}$ is true.
  ✓
- D.
  Both $S_{1}$ and $S_{2}$ are false.
Answer: C
Solution
An ARP request is broadcast (the sender does not yet know the target MAC), so $S_{2}$ is true. An ARP reply is unicast back to the requester, so $S_{1}$ is false.
Question 19Algorithmsmcq1 mark
Consider the following array.
```
23  32  45  69  72  73  89  97
```
Which algorithm out of the following options uses the least number of comparisons (among the array elements) to sort the above array in ascending order?
- A.
  Selection sort
- B.
  Mergesort
- C.
  Insertion sort
  ✓
- D.
  Quicksort using the last element as pivot
Answer: C
Solution
The array is already sorted. Insertion sort on an already-sorted array performs only $n - 1$ comparisons (best case), fewer than the others.
Question 20Programming & Data Structuresmcq1 mark
A binary search tree $T$ contains $n$ distinct elements. What is the time complexity of picking an element in $T$ that is smaller than the maximum element in $T$ ?
- A.
  $Θ (n lo g n)$
- B.
  $Θ (n)$
- C.
  $Θ (lo g n)$
- D.
  $Θ (1)$
  ✓
Answer: D
Solution
The maximum is the right-most node, so the root (for $n \geq 2$ ) is not the maximum. Returning the root (or any fixed non-maximum node) takes $Θ (1)$ time.
Question 21Operating Systemsmsq1 mark
In the context of operating systems, which of the following statements is/are correct with respect to paging?
- A.
  Paging helps solve the issue of external fragmentation.
  ✓
- B.
  Page size has no impact on internal fragmentation.
- C.
  Paging incurs memory overheads.
  ✓
- D.
  Multi-level paging is necessary to support pages of different sizes.
Answer: A, C
Solution
Paging eliminates external fragmentation (A, true) and needs page tables, i.e. memory overhead (C, true). Larger pages increase internal fragmentation, so (B) is false; multi-level paging reduces page-table size and is unrelated to supporting different page sizes, so (D) is false.
Question 22Theory of Computationmsq1 mark
Let $⟨ M ⟩$ denote an encoding of an automaton $M$ . Suppose that $Σ = {0, 1}$ . Which of the following languages is/are NOT recursive?
- A.
  $L = {⟨ M ⟩ ∣ M$ is a DFA such that $L (M) = \emptyset}$
- B.
  $L = {⟨ M ⟩ ∣ M$ is a DFA such that $L (M) = Σ^{*}}$
- C.
  $L = {⟨ M ⟩ ∣ M$ is a PDA such that $L (M) = \emptyset}$
- D.
  $L = {⟨ M ⟩ ∣ M$ is a PDA such that $L (M) = Σ^{*}}$
  ✓
Answer: D
Solution
DFA emptiness, DFA universality and PDA emptiness are all decidable (recursive). PDA/CFG universality ( $L (M) = Σ^{*}$ ) is undecidable, so (D) is not recursive.
Question 23Databasesmsq1 mark
Suppose a database system crashes again while recovering from a previous crash. Assume checkpointing is not done by the database either during the transactions or during recovery. Which of the following statements is/are correct?
- A.
  The same undo and redo list will be used while recovering again.
  ✓
- B.
  The system cannot recover any further.
- C.
  All the transactions that are already undone and redone will not be recovered again.
- D.
  The database will become inconsistent.
Answer: A
Solution
Without checkpointing, recovery restarts from the beginning of the log and recomputes the same undo and redo lists. Recovery operations are idempotent, so the system recovers correctly — only (A) is correct.
Question 24Operating Systemsmsq1 mark
Which of the following standard C library functions will *always* invoke a system call when executed from a single-threaded process in a UNIX/Linux operating system?
- A.
  exit
  ✓
- B.
  malloc
- C.
  sleep
  ✓
- D.
  strlen
Answer: A, C
Solution
exit always triggers the exit/_exit system call and sleep always invokes a kernel timer (e.g. nanosleep). malloc may satisfy a request from the existing heap without a syscall, and strlen is pure user-space computation.
Question 25Operating Systemsmsq1 mark
Consider a linear list based directory implementation in a file system. Each directory is a list of nodes, where each node contains the file name along with the file metadata, such as the list of pointers to the data blocks. Consider a given directory foo. Which of the following operations will necessarily require a full scan of foo for successful completion?
- A.
  Creation of a new file in foo
  ✓
- B.
  Deletion of an existing file from foo
- C.
  Renaming of an existing file in foo
  ✓
- D.
  Opening of an existing file in foo
Answer: A, C
Solution
Creating a new file must confirm the name does not already exist, requiring a full scan (A). Renaming must find the file and confirm the new name is unused, requiring a full scan (C). Deleting and opening can stop as soon as the file is found, so they do not necessarily scan the whole list.
Question 26Discrete Mathematicsnat1 mark
In an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is ______.
Answer: 11
Solution
Euler's formula: $V - E + F = 2 \Rightarrow 8 - E + 5 = 2 \Rightarrow E = 11$ .
Question 27Algorithmsnat1 mark
Consider the undirected graph with edge weights as shown in the figure. The number of minimum-weight spanning trees of the graph is ______.
Answer: 3
Solution
The minimum spanning tree has weight formed by the small (0.1) edges; counting the ways to complete an MST while breaking ties among equal-weight edges gives 3 distinct minimum-weight spanning trees.
Question 28Engineering Mathematicsnat1 mark
The lifetime of a component of a certain type is a random variable whose probability density function is exponentially distributed with parameter 2. For a randomly picked component of this type, the probability that its lifetime exceeds the expected lifetime (rounded to 2 decimal places) is ______.
Answer: 0.35 to 0.39
Solution
For $X \sim Exp (λ = 2)$ , $E [X] = 1/2$ . $P (X > 1/2) = e^{- λ \cdot (1/2)} = e^{- 1} \approx 0.37$ .
Question 29Discrete Mathematicsnat1 mark
There are 6 jobs with distinct difficulty levels, and 3 computers with distinct processing speeds. Each job is assigned to a computer such that: - The fastest computer gets the toughest job and the slowest computer gets the easiest job. - Every computer gets at least one job. The number of ways in which this can be done is ______.
Answer: 65
Solution
Fix the toughest job to the fastest computer and the easiest to the slowest. The remaining 4 jobs go to 3 computers (with the "at least one each" condition already handled), giving 65 valid assignments.
Question 30Engineering Mathematicsnat1 mark
Consider the following expression.
$x \to - 3 lim \frac{2 x + 22 - 4}{x + 3}$
The value of the above expression (rounded to 2 decimal places) is ______.
Answer: 0.25
Solution
This is $0/0$ ; rationalizing (or L'Hopital) gives $\frac{1}{2 x + 22}$ at $x = - 3$ , i.e. $\frac{1}{16} = \frac{1}{4} = 0.25$ .
Question 31Programming & Data Structuresnat1 mark
Consider the following sequence of operations on an empty stack.
```
push(54); push(52); pop(); push(55); push(62); s = pop();
```
Consider the following sequence of operations on an empty queue.
```
enqueue(21); enqueue(24); dequeue(); enqueue(28); enqueue(32); q = dequeue();
```
The value of $s + q$ is ______.
Answer: 86
Solution
Stack: after the operations the top popped into $s$ is 62. Queue (FIFO): the second dequeue returns 24, so $q = 24$ . Hence $s + q = 62 + 24 = 86$ .
Question 32Computer Organization & Architecturenat1 mark
Consider a computer system with a byte-addressable primary memory of size $2^{32}$ bytes. Assume the computer system has a direct-mapped cache of size 32 KB (1 KB $= 2^{10}$ bytes), and each cache block is of size 64 bytes. The size of the tag field is ______ bits.
Answer: 17
Solution
Offset $= lo g_{2} 64 = 6$ bits. Number of lines $= 2^{15} / 2^{6} = 2^{9}$ , so index $= 9$ bits. Tag $= 32 - 6 - 9 = 17$ bits.
Question 33Databasesnat1 mark
A relation $r (A, B)$ in a relational database has 1200 tuples. The attribute $A$ has integer values ranging from 6 to 20, and the attribute $B$ has integer values ranging from 1 to 20. Assume that the attributes $A$ and $B$ are independently distributed. The estimated number of tuples in the output of $σ_{(A > 10) \lor (B = 18)} (r)$ is ______.
Answer: 205 to 820
Solution
With $A \in [6, 20]$ (15 values) and $B \in [1, 20]$ (20 values), $P (A > 10) = 10/15$ and $P (B = 18) = 1/20$ . Using inclusion–exclusion on the estimate gives about 819–820 tuples. (The official GATE key accepted either 819–820 or 205.)
Question 34Digital Logicnat1 mark
Consider the following representation of a number in IEEE 754 single-precision floating point format with a bias of 127.
$S : 1 E : 10000001 F : 11110000000000000000000$
Here $S$ , $E$ and $F$ denote the sign, exponent and fraction components of the floating point representation. The decimal value corresponding to the above representation (rounded to 2 decimal places) is ______.
Answer: -7.75
Solution
$S = 1$ (negative). $E = (10000001)_{2} = 129$ , so exponent $= 129 - 127 = 2$ . Mantissa $= 1.111 1_{2} = 1.9375$ . Value $= - 1.9375 \times 2^{2} = - 7.75$ .
Question 35Operating Systemsnat1 mark
Three processes arrive at time zero with CPU bursts of 16, 20 and 10 milliseconds. If the scheduler has prior knowledge about the length of the CPU bursts, the minimum achievable average waiting time for these three processes in a non-preemptive scheduler (rounded to nearest integer) is ______ milliseconds.
Answer: 12
Solution
Shortest-Job-First minimizes average waiting time. Order 10, 16, 20: waiting times are $0, 10, 26$ ; average $= (0 + 10 + 26) /3 = 12$ ms.
Question 36Compiler Designmcq2 marks
Consider the following grammar (that admits a series of declarations, followed by expressions) and the associated syntax directed translation (SDT) actions, given as pseudo-code:
```
P -> D* E*
D -> int  ID   { record that ID.lexeme is of type int }
D -> bool ID   { record that ID.lexeme is of type bool }
E -> E1 + E2   { check that E1.type = E2.type = int; set E.type := int }
E -> ! E1      { check that E1.type = bool; set E.type := bool }
E -> ID        { set E.type := int }
```
With respect to the above grammar, which one of the following choices is correct?
- A.
  The actions can be used to correctly type-check any syntactically correct program.
- B.
  The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.
  ✓
- C.
  The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.
- D.
  The actions will lead to an infinite loop.
Answer: B
Solution
The rule $E \to I D$ unconditionally sets type int, ignoring a bool declaration, so boolean expressions are not correctly checked. The actions only reliably type-check integer declarations and integer expressions.
Question 37Databasesmcq2 marks
The following relation records the age of 500 employees of a company, where empNo (indicating the employee number) is the key:
$e m p A g e (e m pN o, a g e)$
Consider the following relational algebra expression:
$Π_{e m pN o} (e m p A g e ⋈_{(a g e > a g e 1)} ρ_{e m pN o 1, a g e 1} (e m p A g e))$
What does the above expression generate?
- A.
  Employee numbers of only those employees whose age is the maximum.
- B.
  Employee numbers of only those employees whose age is more than the age of exactly one other employee.
- C.
  Employee numbers of all employees whose age is not the minimum.
  ✓
- D.
  Employee numbers of all employees whose age is the minimum.
Answer: C
Solution
The join pairs an employee with any other employee of smaller age. An employee appears in the result iff there exists someone younger, i.e. the employee's age is not the minimum.
Question 38Digital Logicmcq2 marks
Consider a 3-bit counter, designed using T flip-flops, as shown in the figure. Assuming the initial state of the counter given by PQR as 000, what are the next three states?
- A.
  011, 101, 000
  ✓
- B.
  001, 010, 111
- C.
  011, 101, 111
- D.
  001, 010, 000
Answer: A
Solution
Deriving the T inputs from the circuit and applying them from PQR = 000 produces the state sequence 011, 101, 000.
Question 39Computer Networksmcq2 marks
Assume that a 12-bit Hamming codeword consisting of 8-bit data and 4 check bits is $d_{8} d_{7} d_{6} d_{5} c_{8} d_{4} d_{3} d_{2} c_{4} d_{1} c_{2} c_{1}$ , where the data bits and the check bits are given in the following tables:
```
Data bits:   d8 d7 d6 d5 d4 d3 d2 d1
              1  1  0  x  0  1  0  1
Check bits:  c8 c4 c2 c1
              y  0  1  0
```
Which one of the following choices gives the correct values of $x$ and $y$ ?
- A.
  $x$ is 0 and $y$ is 0.
  ✓
- B.
  $x$ is 0 and $y$ is 1.
- C.
  $x$ is 1 and $y$ is 0.
- D.
  $x$ is 1 and $y$ is 1.
Answer: A
Solution
Using even parity over the Hamming check-bit positions and solving the parity equations for the unknown data bit $x$ and check bit $y$ gives $x = 0$ and $y = 0$ .
Question 40Algorithmsmcq2 marks
Consider the following recurrence relation.
$T (n) = {T (n /2) + T (2 n /5) + 7 n 1 if n > 0 if n = 0$
Which one of the following options is correct?
- A.
  $T (n) = Θ (n^{5/2})$
- B.
  $T (n) = Θ (n lo g n)$
- C.
  $T (n) = Θ (n)$
  ✓
- D.
  $T (n) = Θ ((lo g n)^{5/2})$
Answer: C
Solution
The subproblem sizes sum to $\frac{1}{2} + \frac{2}{5} = \frac{9}{10} < 1$ . With linear work per level and a geometrically shrinking total, the work is dominated by the top level, giving $T (n) = Θ (n)$ .
Question 41Compiler Designmcq2 marks
Consider the following context-free grammar where the set of terminals is ${a, b, c, d, f}$ .
```
S -> d a T | R f
T -> a S | b a T | e
R -> c a T R | e        (e denotes epsilon)
```
The following is a partially-filled LL(1) parsing table; the numbered cells (1), (2), (3), (4) are to be filled (blank denotes an empty cell):
```
      a            b         c          d            f       $
S                          (1)       S->daT       (2)
T   T->aS     T->baT      (3)                    T->e      (4)
R                         R->caTR               R->e
```
Which one of the following choices represents the correct combination for the numbered cells in the parsing table ("blank" denotes that the corresponding cell is empty)?
- A.
  (1) S->Rf (2) S->Rf (3) T->e (4) T->e
  ✓
- B.
  (1) blank (2) S->Rf (3) T->e (4) T->e
- C.
  (1) S->Rf (2) blank (3) blank (4) T->e
- D.
  (1) blank (2) S->Rf (3) blank (4) blank
Answer: A
Solution
Computing FIRST and FOLLOW sets: $R$ is nullable with $c \in F I R S T (c a T R)$ , so $S \to R f$ is entered under both $c$ and $f$ (cells 1 and 2). $T$ is nullable, and FOLLOW $(T)$ contains $c$ and $$$ , so $T \to ϵ$ is entered in cells 3 and 4. This matches option (A).
Question 42Databasesmcq2 marks
Let $r_{i} (z)$ and $w_{i} (z)$ denote read and write operations respectively on a data item $z$ by a transaction $T_{i}$ . Consider the following two schedules.
$S_{1} : r_{1} (x) r_{1} (y) r_{2} (x) r_{2} (y) w_{2} (y) w_{1} (x)$

$S_{2} : r_{1} (x) r_{2} (x) r_{2} (y) w_{2} (y) r_{1} (y) w_{1} (x)$
Which one of the following options is correct?
- A.
  $S_{1}$ is conflict serializable, and $S_{2}$ is not conflict serializable.
- B.
  $S_{1}$ is not conflict serializable, and $S_{2}$ is conflict serializable.
  ✓
- C.
  Both $S_{1}$ and $S_{2}$ are conflict serializable.
- D.
  Neither $S_{1}$ nor $S_{2}$ is conflict serializable.
Answer: B
Solution
Drawing precedence graphs: $S_{1}$ has a cycle between $T_{1}$ and $T_{2}$ (conflicts on $x$ and $y$ in opposite order), so it is not conflict serializable. $S_{2}$ has an acyclic precedence graph ( $T_{2} \to T_{1}$ ), so it is conflict serializable.
Question 43Databasesmcq2 marks
Consider the relation $R (P, Q, S, T, X, Y, Z, W)$ with the following functional dependencies.
$P Q \to X; P \to Y X; Q \to Y; Y \to Z W$
Consider the decomposition of the relation $R$ into the constituent relations according to the following two decomposition schemes.
$D_{1} : R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]$

$D_{2} : R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]$
Which one of the following options is correct?
- A.
  $D_{1}$ is a lossless decomposition, but $D_{2}$ is a lossy decomposition.
  ✓
- B.
  $D_{1}$ is a lossy decomposition, but $D_{2}$ is a lossless decomposition.
- C.
  Both $D_{1}$ and $D_{2}$ are lossless decompositions.
- D.
  Both $D_{1}$ and $D_{2}$ are lossy decompositions.
Answer: A
Solution
Testing each decomposition with the chase/common-attribute test, $D_{1}$ joins back to $R$ losslessly, while $D_{2}$ loses information (the $(T, X)$ split has no FD linking it back), so $D_{2}$ is lossy.
Question 44Discrete Mathematicsmcq2 marks
Let $G$ be a group of order 6, and $H$ be a subgroup of $G$ such that $1 < ∣ H ∣ < 6$ . Which one of the following options is correct?
- A.
  Both $G$ and $H$ are always cyclic.
- B.
  $G$ may not be cyclic, but $H$ is always cyclic.
  ✓
- C.
  $G$ is always cyclic, but $H$ may not be cyclic.
- D.
  Both $G$ and $H$ may not be cyclic.
Answer: B
Solution
By Lagrange, $∣ H ∣ \in {2, 3}$ , both prime, so $H$ is cyclic. $G$ of order 6 can be the non-abelian $S_{3}$ , which is not cyclic. Hence $H$ is always cyclic but $G$ may not be.
Question 45Engineering Mathematicsmcq2 marks
Consider the two statements. $S_{1}$ : There exist random variables $X$ and $Y$ such that $(E [(X - E (X)) (Y - E (Y))])^{2} > Var [X] Var [Y]$ . $S_{2}$ : For all random variables $X$ and $Y$ , $Cov [X, Y] = E [∣ X - E [X] ∣ ∣ Y - E [Y] ∣]$ . Which one of the following choices is correct?
- A.
  Both $S_{1}$ and $S_{2}$ are true.
- B.
  $S_{1}$ is true, but $S_{2}$ is false.
- C.
  $S_{1}$ is false, but $S_{2}$ is true.
- D.
  Both $S_{1}$ and $S_{2}$ are false.
  ✓
Answer: D
Solution
By Cauchy–Schwarz, $Cov (X, Y)^{2} \leq Var (X) Var (Y)$ , so $S_{1}$ is false. Covariance uses signed deviations, not absolute values, so $S_{2}$ is false too.
Question 46Algorithmsmcq2 marks
Let $G = (V, E)$ be an undirected unweighted connected graph. The *diameter* of $G$ is defined as:
$diam (G) = u, v \in V max {the length of shortest path between u and v}$
Let $M$ be the adjacency matrix of $G$ . Define graph $G_{2}$ on the same set of vertices with adjacency matrix $N$ , where $N_{ij} = 1$ if $M_{ij} > 0$ or $P_{ij} > 0$ (where $P = M^{2}$ ), and $0$ otherwise. Which one of the following statements is true?
- A.
  $diam (G_{2}) \leq ⌈ diam (G) /2 ⌉$
  ✓
- B.
  $⌈ diam (G) /2 ⌉ < diam (G_{2}) < diam (G)$
- C.
  $diam (G_{2}) = diam (G)$
- D.
  $diam (G) < diam (G_{2}) \leq 2 diam (G)$
Answer: A
Solution
$G_{2}$ connects any two vertices within distance 2 in $G$ , so every edge in $G_{2}$ corresponds to a path of length $\leq 2$ in $G$ . Distances halve (with ceiling), giving $diam (G_{2}) \leq ⌈ diam (G) /2 ⌉$ .
Question 47Programming & Data Structuresmcq2 marks
Consider the following ANSI C program.
```
#include <stdio.h>
int main()
{
    int i, j, count;
    count = 0;
    i = 0;
    for (j = -3; j <= 3; j++)
    {
        if ((j >= 0) && (i++))
            count = count + j;
    }
    count = count + i;
    printf("%d", count);
    return 0;
}
```
Which one of the following options is correct?
- A.
  The program will not compile successfully.
- B.
  The program will compile successfully and output 10 when executed.
  ✓
- C.
  The program will compile successfully and output 8 when executed.
- D.
  The program will compile successfully and output 13 when executed.
Answer: B
Solution
For $j < 0$ the first operand is false and i++ is not evaluated. For $j = 0$ : i++ returns 0 (false) then $i = 1$ , so count unchanged. For $j = 1, 2, 3$ : i++ returns 1,2,3 (true), count becomes $1, 3, 6$ and $i$ reaches 4. Final count $= 6 + i = 6 + 4 = 10$ .
Question 48Theory of Computationmcq2 marks
Consider the following language.
$L = {w \in {0, 1}^{*} ∣ w ends with the substring 011}$
Which one of the following deterministic finite automata accepts $L$ ? (See the figure for options (A)–(D).)
- A.
  (A)
- B.
  (B)
- C.
  (C)
- D.
  (D)
  ✓
Answer: D
Solution
A correct DFA for strings ending in 011 needs the accepting state reached only after reading 0,1,1 in order, with proper back-transitions on mismatches. Only option (D) has the correct transitions and single accepting state for this pattern.
Question 49Theory of Computationmcq2 marks
For a Turing machine $M$ , $⟨ M ⟩$ denotes an encoding of $M$ . Consider the following two languages.
$L_{1} = {⟨ M ⟩ ∣ M takes more than 2021 steps on all inputs}$

$L_{2} = {⟨ M ⟩ ∣ M takes more than 2021 steps on some input}$
Which one of the following options is correct?
- A.
  Both $L_{1}$ and $L_{2}$ are decidable.
  ✓
- B.
  $L_{1}$ is decidable and $L_{2}$ is undecidable.
- C.
  $L_{1}$ is undecidable and $L_{2}$ is decidable.
- D.
  Both $L_{1}$ and $L_{2}$ are undecidable.
Answer: A
Solution
In at most 2021 steps a TM can read only the first 2021 input cells, so the behaviour depends on finitely many input prefixes. Both conditions can be checked by simulating $M$ for 2021 steps on these finitely many relevant inputs, so both $L_{1}$ and $L_{2}$ are decidable.
Question 50Algorithmsmsq2 marks
Define $R_{n}$ to be the maximum amount earned by cutting a rod of length $n$ meters into one or more pieces of integer length and selling them. For $i > 0$ , let $p [i]$ denote the selling price of a rod whose length is $i$ meters. Consider the array of prices:
$p [1] = 1, p [2] = 5, p [3] = 8, p [4] = 9, p [5] = 10, p [6] = 17, p [7] = 18$
Which of the following statements is/are correct about $R_{7}$ ?
- A.
  $R_{7} = 18$
  ✓
- B.
  $R_{7} = 19$
- C.
  $R_{7}$ is achieved by three different solutions.
  ✓
- D.
  $R_{7}$ cannot be achieved by a solution consisting of three pieces.
Answer: A, C
Solution
The optimal revenue is $R_{7} = 18$ , achievable as $7$ , or $2 + 5$ (5+10=... ) — in fact three distinct cuts give 18: ${7}$ , ${1, 6}$ , ${2, 2, 3}$ . So $R_{7} = 18$ (A) and it is achieved by three different solutions (C).
Question 51Algorithmsmsq2 marks
An *articulation point* in a connected graph is a vertex such that removing the vertex and its incident edges disconnects the graph into two or more connected components. Let $T$ be a DFS tree obtained by doing DFS in a connected undirected graph $G$ . Which of the following options is/are correct?
- A.
  Root of $T$ can never be an articulation point in $G$ .
- B.
  Root of $T$ is an articulation point in $G$ if and only if it has 2 or more children.
  ✓
- C.
  A leaf of $T$ can be an articulation point in $G$ .
- D.
  If $u$ is an articulation point in $G$ such that $x$ is an ancestor of $u$ in $T$ and $y$ is a descendent of $u$ in $T$ , then all paths from $x$ to $y$ in $G$ must pass through $u$ .
  ✓
Answer: B, D
Solution
The DFS-tree characterization: the root is an articulation point iff it has $\geq 2$ children (B true, A false). A leaf is never an articulation point (C false). The ancestor–descendant separation property (D) holds for any articulation point. The official key is (B), (D).
Question 52Digital Logicmsq2 marks
Consider the following Boolean expression.
$F = (X + Y + Z) (X + Y) (Y + Z)$
Which of the following Boolean expressions is/are equivalent to $F$ (complement of $F$ )?
- A.
  $(X + Y + Z) (X + Y) (Y + Z)$
- B.
  $X Y + Z$
  ✓
- C.
  $(X + Z) (Y + Z)$
  ✓
- D.
  $X Y + Y Z + X Y Z$
  ✓
Answer: B, C, D
Solution
Simplifying, $F = Y Z + X Y Z \dots$ ; its complement reduces to $F = X Y + Z$ . Options (B), (C) and (D) are all algebraically equal to this, while (A) is not.
Question 53Discrete Mathematicsmsq2 marks
A relation $R$ is said to be *circular* if $a R b$ and $b R c$ together imply $c R a$ . Which of the following options is/are correct?
- A.
  If a relation $S$ is reflexive and symmetric, then $S$ is an equivalence relation.
- B.
  If a relation $S$ is circular and symmetric, then $S$ is an equivalence relation.
- C.
  If a relation $S$ is reflexive and circular, then $S$ is an equivalence relation.
  ✓
- D.
  If a relation $S$ is transitive and circular, then $S$ is an equivalence relation.
Answer: C
Solution
A relation is an equivalence relation iff it is reflexive and circular (reflexive + circular implies symmetric and transitive), so (C) is correct. Reflexive+symmetric need not be transitive (A false); the others do not guarantee all three properties.
Question 54Computer Networksmsq2 marks
A TCP server application is programmed to listen on port number $P$ on host $S$ . A TCP client is connected to the TCP server over the network. Consider that while the TCP connection was active, the server machine $S$ crashed and rebooted. Assume that the client does not use the TCP keepalive timer. Which of the following behaviors is/are possible?
- A.
  If the client was waiting to receive a packet, it may wait indefinitely.
  ✓
- B.
  The TCP server application on $S$ can listen on $P$ after reboot.
  ✓
- C.
  If the client sends a packet after the server reboot, it will receive a RST segment.
  ✓
- D.
  If the client sends a packet after the server reboot, it will receive a FIN segment.
Answer: A, B, C
Solution
After a crash the server loses all TCP state. A silent client may wait forever (A). The server can bind and listen on $P$ again after reboot (B). If the client sends data, the rebooted server has no matching connection and replies with RST, not FIN (C true, D false).
Question 55Computer Networksmsq2 marks
Consider two hosts $P$ and $Q$ connected through a router $R$ . The maximum transfer unit (MTU) value of the link between $P$ and $R$ is 1500 bytes, and between $R$ and $Q$ is 820 bytes. A TCP segment of size 1400 bytes was transferred from $P$ to $Q$ through $R$ , with IP identification value as 0x1234. Assume that the IP header size is 20 bytes. Further, the packet is allowed to be fragmented, i.e., Don't Fragment (DF) flag in the IP header is *not* set by $P$ . Which of the following statements is/are correct?
- A.
  Two fragments are created at $R$ and the IP datagram size carrying the second fragment is 620 bytes.
  ✓
- B.
  If the second fragment is lost, $R$ will resend the fragment with the IP identification value 0x1234.
- C.
  If the second fragment is lost, $P$ is required to resend the whole TCP segment.
  ✓
- D.
  TCP destination port can be determined by analysing *only* the second fragment.
Answer: A, C
Solution
The 1420-byte datagram is fragmented at $R$ for the 820-byte MTU: payload per fragment must be a multiple of 8, giving 800 + 620 bytes, so the second datagram is 620 bytes (A). $R$ does not retransmit (B false); loss recovery is by TCP at $P$ which resends the whole segment (C). The TCP header (with ports) is only in the first fragment, so (D) is false.
Question 56Operating Systemsmsq2 marks
Consider the following pseudocode, where S is a semaphore initialized to 5 in line#2 and counter is a shared variable initialized to 0 in line#1. Assume that the increment operation in line#7 is *not* atomic.
```
1.  int counter = 0;
2.  Semaphore S = init(5);
3.  void parop(void)
4.  {
5.      wait(S);
6.      wait(S);
7.      counter++;
8.      signal(S);
9.      signal(S);
10. }
```
If five threads execute the function parop concurrently, which of the following program behavior(s) is/are possible?
- A.
  The value of counter is 5 after all the threads successfully complete the execution of parop.
  ✓
- B.
  The value of counter is 1 after all the threads successfully complete the execution of parop.
  ✓
- C.
  The value of counter is 0 after all the threads successfully complete the execution of parop.
- D.
  There is a deadlock involving all the threads.
  ✓
Answer: A, B, D
Solution
Each thread does two waits. In a serialized interleaving counter reaches 5 (A). With up to two threads in the critical section and a non-atomic increment, lost updates can leave counter as low as 1 (B). If every thread completes its first wait before any does the second, all 5 units of S are taken and all block — deadlock (D). counter can never be 0 after all complete, so (C) is impossible.
Question 57Algorithmsmsq2 marks
Consider a *dynamic* hashing approach for 4-bit integer keys: 1. There is a main hash table of size 4. 2. The 2 least significant bits of a key is used to index into the main hash table. 3. Initially, the main hash table entries are empty. 4. Thereafter, when more keys are hashed into it, to resolve collisions, the set of all keys corresponding to a main hash table entry is organized as a binary tree that grows on demand. 5. First, the 3rd least significant bit is used to divide the keys into left and right subtrees. 6. To resolve more collisions, each node of the binary tree is further sub-divided into left and right subtrees based on the 4th least significant bit. 7. A split is done only if it is needed, i.e., only when there is a collision. Consider the state of the hash table shown in the figure. Which of the following sequences of key insertions can cause the above state of the hash table (assume the keys are in decimal notation)?
- A.
  5, 9, 4, 13, 10, 7
- B.
  9, 5, 10, 6, 7, 1
- C.
  10, 9, 6, 7, 5, 13
  ✓
- D.
  9, 5, 13, 6, 10, 14
Answer: C
Solution
Tracing each insertion sequence through the index (2 LSBs) and the on-demand splits (3rd then 4th LSB), only sequence (C) 10, 9, 6, 7, 5, 13 reproduces exactly the shown tree structure, with splits occurring only where collisions force them.
Question 58Programming & Data Structuresnat2 marks
Consider the following ANSI C function:
```
int SimpleFunction(int Y[], int n, int x)
{
    int total = Y[0], loopIndex;
    for (loopIndex = 1; loopIndex <= n - 1; loopIndex++)
            total = x * total + Y[loopIndex];
    return total;
}
```
Let Z be an array of 10 elements with Z[i]=1, for all $i$ such that $0 \leq i \leq 9$ . The value returned by SimpleFunction(Z, 10, 2) is ______.
Answer: 1023
Solution
This is Horner evaluation of the polynomial with all coefficients 1 at $x = 2$ : $\sum_{i = 0}^{9} 2^{i} = 2^{10} - 1 = 1023$ .
Question 59Computer Networksnat2 marks
Consider the sliding window flow-control protocol operating between a sender and a receiver over a full-duplex error-free link. Assume the following: - Processing time of the data frame at the receiver, and of the acknowledgement at the sender, is negligible. - The sender has infinite frames available. - Data frame size is 2,000 bits and acknowledgement frame size is 10 bits. - Link data rate in each direction is 1 Mbps ( $= 1 0^{6}$ bits per second). - One way propagation delay of the link is 100 milliseconds. The minimum value of the sender's window size in terms of the number of frames, (rounded to the nearest integer) needed to achieve a link utilization of 50% is ______.
Answer: 50 to 52
Solution
Transmission time $T_{t} = 2000/1 0^{6} = 2$ ms, $T_{p} = 100$ ms. Utilization $= \frac{N \cdot T _{t}}{T _{t} + 2 T _{p}}$ . Setting this $= 0.5$ : $N = 0.5 \cdot \frac{2 + 200}{2} = 50.5$ , so the minimum integer window is 51.
Question 60Compiler Designnat2 marks
Consider the following C code segment:
```
a = b + c;
e = a + 1;
d = b + c;
f = d + 1;
g = e + f;
```
In a compiler, this code segment is represented internally as a directed acyclic graph (DAG). The number of nodes in the DAG is ______.
Answer: 6
Solution
Leaves: b, c, and the constant 1 (3 nodes). b+c is a common subexpression shared by a and d (1 node). a+1 (= e, and d+1=f share the same value as they add 1 to the same node) and e+f add internal nodes, for a total of 6 distinct nodes.
Question 61Theory of Computationnat2 marks
In a pushdown automaton $P = (Q, Σ, Γ, δ, q_{0}, F)$ , a transition of the form shown represents $(q, Y) \in δ (p, a, X)$ . Consider the pushdown automaton over the input alphabet $Σ = {a, b}$ and stack alphabet $Γ = {#, A}$ shown in the figure. The number of strings of length 100 accepted by the above pushdown automaton is ______.
Answer: 50
Solution
The PDA pushes an $A$ for each $a$ and pops one for each $b$ , and reaches the accepting state only while an $A$ remains, i.e. it accepts $a^{i} b^{j}$ with $i > j$ . For $i + j = 100$ we need $i > j$ , i.e. $j = 0, 1, \dots, 49$ — exactly 50 strings.
Question 62Engineering Mathematicsnat2 marks
Consider the following matrix.
$0111101111011110$
The largest eigenvalue of the above matrix is ______.
Answer: 3
Solution
The matrix is $J - I$ where $J$ is the all-ones $4 \times 4$ matrix. $J$ has eigenvalues $4$ (once) and $0$ (thrice), so $J - I$ has eigenvalues $3$ and $- 1, - 1, - 1$ . The largest is $3$ .
Question 63Computer Organization & Architecturenat2 marks
A five-stage pipeline has stage delays of 150, 120, 150, 160 and 140 nanoseconds. The registers that are used between the pipeline stages have a delay of 5 nanoseconds each. The total time to execute 100 independent instructions on this pipeline, assuming there are no pipeline stalls, is ______ nanoseconds.
Answer: 17160
Solution
Clock period $= max (150, 120, 150, 160, 140) + 5 = 165$ ns. Time for 100 instructions $= (5 + 100 - 1) \times 165 = 104 \times 165 = 17160$ ns.
Question 64Engineering Mathematicsnat2 marks
A sender (S) transmits a signal, which can be one of the two kinds: $H$ and $L$ with probabilities 0.1 and 0.9 respectively, to a receiver (R). In the graph (see figure), the weight of edge $(u, v)$ is the probability of receiving $v$ when $u$ is transmitted, where $u, v \in {H, L}$ . For example, the probability that the received signal is $L$ given the transmitted signal was $H$ , is 0.7. If the received signal is $H$ , the probability that the transmitted signal was $H$ (rounded to 2 decimal places) is ______.
Answer: 0.04
Solution
From the figure: $P (H \to H) = 0.3, P (L \to H) = 0.8$ . $P (recv H) = 0.1 (0.3) + 0.9 (0.8) = 0.03 + 0.72 = 0.75$ . By Bayes, $P (sent H ∣ recv H) = \frac{0.03}{0.75} = 0.04$ .
Question 65Computer Organization & Architecturenat2 marks
Consider the following instruction sequence where registers R1, R2 and R3 are general purpose and MEMORY[X] denotes the content at the memory location X.
```
Instruction        Semantics                 Size (bytes)
MOV R1, (5000)     R1 <- MEMORY[5000]            4
MOV R2, (R3)       R2 <- MEMORY[R3]              4
ADD R2, R1         R2 <- R1 + R2                 2
MOV (R3), R2       MEMORY[R3] <- R2              4
INC R3             R3 <- R3 + 1                  2
DEC R1             R1 <- R1 - 1                  2
BNZ 1004           Branch if not zero to addr    2
HALT               Stop                          1
```
Assume that the content of memory location 5000 is 10, and the content of register R3 is 3000. The content of each of the memory locations from 3000 to 3010 is 50. The instruction sequence starts from memory location 1000. All the numbers are in decimal format. Assume that the memory is byte addressable. After the execution of the program, the content of memory location 3010 is ______.
Answer: 50
Solution
R1 starts at 10 and the loop (BNZ to address 1004, the second instruction) runs while R1 is non-zero, writing to MEMORY[R3] as R3 increments from 3000. The loop body executes for R3 = 3000..3009 (10 iterations) and then stops; MEMORY[3010] is never written and stays 50.

Practice the full paper with a timer

Attempt GATE CS 2021 Set 1 in the exact GATE interface and get a detailed score and topic-wise analysis — free.

Create free account →