GATE CS 2026_Set1 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

GATE CS 2026_Set1 previous year paper: 65 questions with answer key and detailed solutions, section-wise breakdown and free sample questions.

Paper breakdown

65 questions · 100 marks. Engineering Mathematics: 10 · Computer Organization and Architecture: 9 · Programming and Data Structures: 8 · Computer Networks: 5 · Theory of Computation: 4 · Operating System: 4 · Databases: 4 · Compiler Design: 4 · Algorithms: 4 · Quantitative Aptitude: 3 · Digital Logic: 3 · Analytical Aptitude: 3 · Verbal Aptitude: 2 · Spatial Aptitude: 2

Free sample questions from GATE CS 2026_Set1 Question Paper

Question 1 · Engineering Mathematics · 2026_Set1 MCQ

An urn contains one red ball and one blue ball. At each step, a ball is picked uniformly at random from the urn, and this ball together with another ball of the same color is put back in the urn. The probability that there are equal number of red and blue balls after two steps is

A.
$\frac{1}{4}$
B.
$\frac{1}{3}$
C.
$\frac{1}{2}$
D.
$\frac{2}{3}$

Correct Answer:

Step-by-Step Solution

Insight: Equal red and blue after 2 steps means exactly 1 red and 1 blue were drawn — use exchangeability or direct enumeration.

Exam route: Start: 1R, 1B. After 2 steps, total = 4. Equal counts need 2R and 2B, so exactly $k = 1$ red drawn. By exchangeability: $P = (1 2) \cdot 1^{(1)} \cdot 1^{(1)} / 2^{(2)} = 2 \cdot 1 \cdot 1/6 = 1/3$ . Select B.

Learning route:

This is a Polya Urn state question, identifiable by the reinforcement mechanism (draw, replace, add one of the same colour) and the question asking about the urn's composition after a fixed number of steps.

Setup: Initial state: 1 red, 1 blue, total 2. After 2 draws, total = $2 + 2 = 4$ balls. For equal red and blue counts, we need 2 red and 2 blue, which means exactly 1 red and 1 blue were drawn in the 2 draws.

Method 1 — Direct enumeration:

List all possible sequences of 2 draws:

RR: $P = \frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}$ → final: 3R, 1B (not equal)
RB: $P = \frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}$ → final: 2R, 2B (equal ✓)
BR: $P = \frac{1}{2} \cdot \frac{1}{3} = \frac{1}{6}$ → final: 2R, 2B (equal ✓)
BB: $P = \frac{1}{2} \cdot \frac{2}{3} = \frac{1}{3}$ → final: 1R, 3B (not equal)

$P (equal) = \frac{1}{6} + \frac{1}{6} = \frac{1}{3}$

Method 2 — Exchangeability formula:

$P (k reds in n draws) = \frac{( k n ) \cdot r ^{(k)} \cdot b ^{(n - k)}}{( r + b ) ^{(n)}}$

With $r = 1, b = 1, n = 2, k = 1$ :

$P = \frac{( 1 2 ) \cdot 1 ^{(1)} \cdot 1 ^{(1)}}{2 ^{(2)}} = \frac{2 \cdot 1 \cdot 1}{2 \cdot 3} = \frac{2}{6} = \frac{1}{3}$

Wrong path walkthrough: A student who treats draws as independent coin flips computes $P (exactly 1 head in 2 flips) = (1 2) (1/2)^{2} = 1/2$ , matching option C. The mistake is at the independence assumption: in a Polya Urn, the second draw's probability depends on the first draw's outcome. The reinforcement mechanism makes draws dependent, reducing the probability of mixed outcomes.

Generalisation: In a Polya Urn, reinforcement amplifies early outcomes, making "all same colour" more likely and "mixed" less likely compared to independent draws.

Verification: The four sequence probabilities sum to $\frac{1}{3} + \frac{1}{6} + \frac{1}{6} + \frac{1}{3} = 1$ . ✓

Answer: B) $\frac{1}{3}$

Question 2 · Engineering Mathematics · 2026_Set1 MCQ

Consider $4 \times 4$ matrices with their elements from ${0, 1}$ . The number of such matrices with even number of $1$ s in every row and every column is

A.
512
B.
1025
C.
1023
D.
255

Correct Answer:

Step-by-Step Solution

Key idea: This is a binary matrix counting problem with parity constraints, recognizable by the requirement of an "even number of 1s in every row and every column". We solve this by determining the degrees of freedom in the matrix.

Step 1: Consider the top-left $3 \times 3$ submatrix (rows 1-3, columns 1-3). The entries in this submatrix can be chosen completely freely.

Number of ways to fill this $3 \times 3$ block = $2^{3 \times 3} = 2^{9} = 512$ .

Step 2: Determine the remaining cells in the first 3 rows.

For each of the first 3 rows, the entry in the 4th column is uniquely forced to make the row sum even.

Step 3: Determine the remaining cells in the first 3 columns.

For each of the first 3 columns, the entry in the 4th row is uniquely forced to make the column sum even.

Step 4: Determine the bottom-right cell (row 4, column 4).

This cell must satisfy both the 4th row parity and the 4th column parity. In a binary matrix, the sum of all row parities equals the sum of all column parities (both equal the total sum of all elements mod 2). Thus, the two constraints on the bottom-right cell are perfectly consistent, and it is uniquely determined.

Step 5: Calculate the total.

Since all other cells are uniquely determined by the free choices in the $3 \times 3$ submatrix, the total number of valid matrices is exactly 512.

Answer: A

Question 3 · Engineering Mathematics · 2026_Set1 MCQ

For $n > 1$ , the maximum multiplicity of any eigenvalue of an $n \times n$ matrix with elements from $R$ is

A.
$n$
B.
$n - 1$
C.
1
D.
$n + 1$

Correct Answer:

Step-by-Step Solution

Insight: The characteristic polynomial of an $n \times n$ matrix has degree exactly $n$ , so no eigenvalue can repeat more than $n$ times — and the identity matrix achieves this bound.

Exam route: The characteristic equation $det (A - λ I) = 0$ is a polynomial of degree $n$ . The maximum multiplicity of any root of a degree- $n$ polynomial is $n$ . The identity matrix $I_{n}$ has characteristic polynomial $(1 - λ)^{n} = 0$ , so eigenvalue $1$ has multiplicity $n$ . Answer: $n$ .

Learning route: This is a theoretical maximum-multiplicity question, recognisable because no specific matrix is given and the answer is in terms of $n$ .

Step 1: For any $n \times n$ matrix $A$ , the characteristic equation $det (A - λ I) = 0$ expands to a polynomial in $λ$ of degree exactly $n$ .

Step 2: By the Fundamental Theorem of Algebra, this polynomial has exactly $n$ roots counting multiplicity. The algebraic multiplicity of a single eigenvalue is the number of times it appears as a root.

Step 3: Since the total count of all roots (with multiplicity) is $n$ , no single eigenvalue can have algebraic multiplicity exceeding $n$ .

Step 4: To confirm $n$ is achievable, consider $A = I_{n}$ . Its characteristic polynomial is $(1 - λ)^{n} = 0$ , giving $λ = 1$ with algebraic multiplicity exactly $n$ .

Wrong path — Option B ( $n - 1$ ): A student confuses this with the rank-nullity theorem or thinks "at least one eigenvalue must differ." This produces $n - 1$ . It breaks at Step 4: the identity matrix is a direct counterexample where all $n$ eigenvalues are identical.

Wrong path — Option C ( $1$ ): A student assumes all eigenvalues must be distinct, or confuses algebraic multiplicity with the minimum geometric multiplicity. This produces $1$ . It breaks at Step 3: nothing prevents all $n$ roots from coinciding.

Wrong path — Option D ( $n + 1$ ): A student does not realise the characteristic polynomial has degree exactly $n$ and thinks multiplicity can exceed the matrix size. This produces $n + 1$ . It breaks at Step 1: a degree- $n$ polynomial cannot have a root of multiplicity $n + 1$ .

Generalization: The sum of algebraic multiplicities of all eigenvalues of an $n \times n$ matrix always equals $n$ , so the maximum any single eigenvalue can claim is the entire sum.

Verification: For $n = 3$ , $I_{3}$ has characteristic polynomial $(1 - λ)^{3} = 0$ , giving eigenvalue $1$ with multiplicity $3 = n$ . Confirmed.

Question 4 · Computer Organization and Architecture · 2026_Set1 MCQ

Match each addressing mode in List I with a data element or an element of a data structure (in a high-level language) in List II:

List I	List II
P. Immediate	1. Element of an array
Q. Indirect	2. Pointer
R. Base with index	3. Element of a record
S. Base with offset/displacement	4. Constant

A.
P–4, Q–3, R–1, S–2
B.
P–4, Q–2, R–1, S–3
C.
P–1, Q–4, R–3, S–2
D.
P–2, Q–3, R–1, S–4

Correct Answer:

Step-by-Step Solution

Key idea: This is a concept mapping question, recognisable because it asks to link hardware-level addressing modes with software-level data structures. The method is to analyse the components of each addressing mode and match them to how high-level languages access data.

Step 1: Analyse Immediate addressing. The operand is directly given in the instruction itself. This corresponds to a literal constant in code. So, P matches 4.

Step 2: Analyse Indirect addressing. The instruction gives the address of the address (or a register contains the address of the operand). This is the exact definition of a pointer (a variable that stores the memory address of another variable). So, Q matches 2.

Step 3: Analyse Base with index addressing. The effective address is Base + Index. The base is the start of a collection, and the index is a variable offset (like a loop counter). This is used to access elements of an array. So, R matches 1.

Step 4: Analyse Base with offset/displacement addressing. The effective address is Base + fixed Offset. The base is the start of a data structure, and the offset is a fixed distance to a specific field. This is used to access elements of a record or struct. So, S matches 3.

Conclusion: P-4, Q-2, R-1, S-3. This matches option B.

Question 5 · Computer Organization and Architecture · 2026_Set1 MCQ

Consider a processor P whose instruction set architecture is the load-store architecture. The instruction format is such that the first operand of any instruction is the destination operand.

Which one of the following sequences of instructions corresponds to the high-level language statement

Z = X + Y

?

Note: X, Y, and Z are memory operands. R0, R1, and R2 are registers.

A.
ADD Z, X, Y
B. LOAD R0, X
ADD Z, R0, Y
C. ADD R0, X, Y
STORE Z, R0
D. LOAD R0, X
LOAD R1, Y
ADD R2, R0, R1
STORE Z, R2

Correct Answer:

Step-by-Step Solution

Key idea: This is a load-store architecture translation question, recognisable because it asks to map a high-level variable assignment to a sequence of assembly instructions under strict memory-access rules.

Why this method applies: In a load-store architecture, the ALU cannot operate directly on memory operands. Data must be explicitly moved into registers before computation, and the result must be stored back to memory.

Step 1: Identify the operands. X and Y are memory operands, and Z is the memory destination.

Step 2: Load the operands into registers. We need two LOAD instructions to bring X and Y into registers (e.g., R0 and R1).

Step 3: Perform the computation. Use an ADD instruction with register operands to compute X + Y, storing the result in a third register (e.g., R2).

Step 4: Store the result. Use a STORE instruction to write the value from R2 back to the memory location Z.

Matching this sequence to the options:

Option A attempts a memory-memory ADD, which is invalid in load-store architecture.

Option B loads X but tries to ADD with Y still in memory, which is invalid.

Option C attempts to ADD memory operands directly, which is invalid.

Option D correctly loads X into R0, loads Y into R1, adds them into R2, and stores R2 into Z.

Answer: Option D.

Question 6 · Computer Organization and Architecture · 2026_Set1 MCQ

Which one of the following dependencies among the register operands of different instructions can cause a data hazard in a pipelined processor?

A.
Read-after-read
B.
Read-after-write
C.
Write-after-read
D.
Write-after-write

Correct Answer:

Step-by-Step Solution

Key idea: This is a conceptual MCQ on data dependency types, recognisable because it asks which dependency among register operands causes a data hazard in a pipelined processor.

Step 1: Recall the three types of data dependencies between instructions I (earlier) and J (later):

RAW (Read After Write): J reads a register that I writes. This is a true data dependency because J genuinely needs the value I produces.
WAR (Write After Read): J writes a register that I reads. This is a name dependency (anti-dependency).
WAW (Write After Write): J writes a register that I also writes. This is a name dependency (output dependency).

Step 2: In a standard in-order 5-stage pipeline, instructions execute in program order. WAR and WAW hazards cannot occur because reads always happen before later writes in program order, and writes complete in order. Only RAW creates a genuine hazard where J might read a stale value before I has written the new one.

Step 3: Read-after-read (option A) is not even a recognized dependency type that causes any hazard, since both instructions only read and neither modifies the value.

Step 4: Therefore, only Read-after-write (RAW) causes a data hazard in a pipelined processor.

Answer: B

Question 7 · Programming and Data Structures · 2026_Set1 MSQ

Let

n

be an odd number greater than 100. Consider a binary minheap with

n

elements stored in an array

P

whose index starts from 1.

Which of the following indices of

P

do/does NOT correspond to any leaf node of the minheap?

A.
$\frac{n + 1}{2}$
B.
$\frac{n - 1}{2}$
C.
$\frac{n - 3}{2}$
D.
$n$

Question 8 · Programming and Data Structures · 2026_Set1 MSQ

Consider a hash table

P [0, 1, \dots, 10]

that is initially empty. The hash table is maintained using open addressing with linear probing. The hash function used is

h (x) = (x + 7) mod 11

.

Consider the following sequence of insertions performed on

P

1, 13, 22, 15, 11, 24

Which of the following positions in the hash table is/are empty after these insertions are performed?

A.
0
B.
10
C.
2
D.
1

Correct Answer:

["C"]

Step-by-Step Solution

Insight: Linear probing resolves collisions by sequentially checking the next available slot, wrapping around the table if necessary.

Exam route: Map each key to its initial hash, then shift right one slot at a time upon collision, keeping track of occupied indices to identify the empty ones.

Learning route:

Table size $m = 11$ , indices $0$ to $10$ .

$h (x) = (x + 7) mod 11$ .

Insertions:

1: $h (1) = 8$ . P[8] = 1.
13: $h (13) = 9$ . P[9] = 13.
22: $h (22) = 7$ . P[7] = 22.
15: $h (15) = 0$ . P[0] = 15.
11: $h (11) = 7$ . P[7] full. Probe 8 (full), 9 (full), 10 (empty). P[10] = 11.
24: $h (24) = 9$ . P[9] full. Probe 10 (full), 0 (full), 1 (empty). P[1] = 24.

Occupied slots: 0, 1, 7, 8, 9, 10.

Empty slots: 2, 3, 4, 5, 6.

Checking the options: 0 is occupied, 10 is occupied, 2 is empty, 1 is occupied. Only position 2 is empty.

Tempting wrong path: Assuming index 0 remains empty because no key naturally hashes to it without wrap-around, but 15 hashes to 0 directly. Or assuming index 10 is empty because it is at the end, forgetting that 11 wraps into it.

Generalization: Linear probing clusters can wrap around the end of the array; always apply the modulo operator when incrementing the probe index.

Verification: Count the keys. 6 keys inserted, so exactly 6 slots must be occupied and 5 empty. Our occupied list has 6 distinct slots.

Question 9 · Programming and Data Structures · 2026_Set1 NAT

The height of a binary tree is the number of edges in the longest path from the root to a leaf in the tree. The maximum possible height of a full binary tree with 23 nodes is _________. (answer in integer)

Correct Answer:

11.00

Step-by-Step Solution

Insight: This is a strict binary tree height question, recognizable because it asks for the "maximum possible height" of a "full" (strict) binary tree with a given node count.

Exam route: A full binary tree has nodes with 0 or 2 children. To maximize height, make the tree as unbalanced as possible: each internal node has one leaf child and one internal node child. The number of internal nodes is $(n - 1) /2$ . The max height equals the number of internal nodes. For $n = 23$ , height = $(23 - 1) /2 = 11$ .

Learning route:

Step 1: Understand the constraints. A "full" or "strict" binary tree requires every node to have either 0 or 2 children. No node can have exactly 1 child.

Step 2: Relate nodes to degrees. Let $N_{0}$ be leaves, $N_{2}$ be internal nodes (degree 2). We know $N_{0} = N_{2} + 1$ and Total $N = N_{0} + N_{2}$ .

Step 3: Calculate $N_{2}$ for $N = 23$ .

$23 = (N_{2} + 1) + N_{2} ⟹ 2 N_{2} = 22 ⟹ N_{2} = 11$ .

There are exactly 11 internal nodes.

Step 4: Maximize the height. Height is the number of edges on the longest root-to-leaf path. To make this path as long as possible, we must string the internal nodes together in a single "spine".

Step 5: Construct the spine. Each of the 11 internal nodes (except the last one) will have one child that is a leaf (which terminates that branch) and one child that is the next internal node in the spine. The 11th internal node will have two leaf children.

Step 6: Count the edges. The path from the root to the deepest leaf passes through all 11 internal nodes. The number of edges in this path is exactly 11.

Formula: $h_{ma x} = \frac{N - 1}{2} = \frac{23 - 1}{2} = 11$ .

Wrong path: Confusing "full" with "perfect". A perfect tree minimizes height ( $h = ⌊ lo g_{2} 23 ⌋ = 4$ ). The question asks for maximum height, which requires maximizing imbalance while respecting the strict degree constraint.

Question 10 · Computer Networks · 2026_Set1 MCQ

With respect to a TCP connection between a client and a server, which one of the following statements is true?

A.
The client and server use a two-way handshake mechanism before the start of data transmission
B.
The server cannot initiate closing of the connection before the client initiates closing of the connection
C.
The TCP connection is half-duplex
D.
The client and server can initiate closing of the connection at the same time

Question 11 · Computer Networks · 2026_Set1 MSQ

Which of the following statements is/are true with respect to the interaction of a web browser with a web server using HTTP 1.1?

A.
HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, if the objects are stored in the same server
B.
HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, even if they are stored in different servers
C.
HTTP 1.1 facilitates sending a request for downloading one object without waiting for a previously requested object to be downloaded completely
D.
HTTP 1.1 facilitates downloading multiple webpages on the same server to be downloaded over a single TCP connection

Question 12 · Computer Networks · 2026_Set1 MCQ

A TCP sender successfully establishes a connection with a TCP receiver and starts the transmission of segments. The TCP congestion control mechanism’s slow-start threshold is set to 10000 segments. Assume that the round-trip time is fixed at 1 millisecond. Assume that the sender always has data to send, the segments are numbered from 1, and no segment is lost. Let

t

denote the time (in milliseconds) at which the transmission of segment number 2000 starts.

Which one of the following options is correct?

A.
$9 \leq t < 10$
B.
$10 \leq t < 11$
C.
$11 \leq t < 12$
D.
$12 \leq t < 13$

Question 13 · Theory of Computation · 2026_Set1 MSQ

Consider the following grammar where

S

is the start symbol, and

a

and

b

are terminal symbols.

S \to a S b S ∣ b S ∣ ϵ

Which of the following statements is/are true?

A.
The grammar is ambiguous
B.
The string $abb$ has two distinct derivations in this grammar
C.
The string $abab$ has only one rightmost derivation
D.
The language generated by the grammar is undecidable

Correct Answer:

["A","B"]

Step-by-Step Solution

Key idea: This is a grammar ambiguity question. To prove a grammar is ambiguous, we must find at least one string with multiple distinct leftmost derivations.

Step 1: Check string "abb".

Derivation 1 (Leftmost):

S ⇒ aSbS

⇒ abSbS (using S → bS for the first S)

⇒ abbS (using S → ε for the second S)

⇒ abb (using S → ε for the third S)

Derivation 2 (Leftmost):

S ⇒ aSbS

⇒ abS (using S → ε for the first S)

⇒ abbS (using S → bS for the remaining S)

⇒ abb (using S → ε for the remaining S)

These are two distinct leftmost derivations for "abb", so the grammar is ambiguous.

Step 2: Evaluate options.

A: True (proven above).

B: True (proven above).

C: False. The string "abab" has multiple rightmost derivations. For example:

RMD 1: S ⇒ aSbS ⇒ aSbaSbS ⇒ aSbaSb ⇒ aSbab ⇒ abab

RMD 2: S ⇒ aSbS ⇒ aSb ⇒ a(aSbS)b ⇒ a(aSb)b ⇒ a(ab)b ⇒ abab

D: False. All context-free languages are decidable (e.g., via CYK algorithm).

Answer: Options A and B are true.

Question 14 · Theory of Computation · 2026_Set1 MSQ

Let M be a nondeterministic finite automaton (NFA) with 6 states over a finite alphabet.

Which of the following options CANNOT be the number of states in the minimal deterministic finite automaton (DFA) that is equivalent to

M

A.
32
B.
65
C.
1
D.
128

Question 15 · Theory of Computation · 2026_Set1 MSQ

Let

L_{1}

and

L_{2}

be two languages over a finite alphabet, such that

L_{1} \cap L_{2}

and

L_{2}

are regular languages.

Which of the following statements is/are always true?

A.
$L_{1}$ is regular
B.
$L_{1} \cup L_{2}$ is regular
C.
$L_{2}$ is context-free
D.
$L_{1}$ is context-free

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is a closure properties question involving the subset fallacy, recognizable because it gives a condition on an intersection and asks what must be true about the individual languages.

Step 1: We are given that $L_{1} \cap L_{2}$ is regular and $L_{2}$ is regular. We need to determine which statements are ALWAYS true.

Step 2: Evaluate Option A ( $L_{1}$ is regular) and Option B ( $L_{1} \cup L_{2}$ is regular). Consider the counterexample where $L_{2} = \emptyset$ . The empty set is regular. Then $L_{1} \cap L_{2} = L_{1} \cap \emptyset = \emptyset$ , which is regular. This satisfies the given conditions for ANY language $L_{1}$ . If we choose $L_{1}$ to be a non-regular language (e.g., ${a^{n} b^{n} ∣ n \geq 0}$ ), then $L_{1}$ is not regular, and $L_{1} \cup L_{2} = L_{1} \cup \emptyset = L_{1}$ is not regular. Thus, A and B are NOT always true.

Step 3: Evaluate Option D ( $L_{1}$ is context-free). Using the same counterexample where $L_{1} = {a^{n} b^{n} c^{n} ∣ n \geq 0}$ (which is not context-free) and $L_{2} = \emptyset$ , the conditions are met but $L_{1}$ is not CFL. Thus, D is NOT always true.

Step 4: Evaluate Option C ( $L_{2}$ is context-free). We are explicitly given that $L_{2}$ is regular. Since every regular language is also a context-free language (Regular $\subset$ CFL), $L_{2}$ MUST be context-free. This is ALWAYS true.

Answer: C

Question 16 · Operating System · 2026_Set1 MSQ

With respect to deadlocks in an operating system, which of the following statements is/are FALSE?

A.
Banker’s algorithm is used to prevent deadlocks
B.
Deadlock formation can be prevented by ensuring that the hold and wait condition is not allowed
C.
An assignment edge in a resource allocation graph is marked from a process to a resource
D.
A safe state guarantees that all processes can finish without formation of a deadlock

Question 17 · Operating System · 2026_Set1 NAT

Consider a system consisting of

k

instances of a resource

R

, being shared by 5 processes. Assume that each process requires a maximum of two instances of resource

R

and a process can request or release only one instance at a time. Further, a process can request the second instance of the resource only after acquiring the first instance.

The minimum value of

k

for the system to be deadlock-free is ________. (answer in integer)

Question 18 · Operating System · 2026_Set1 NAT

Consider the following program snippet. Assume that the program compiles and runs successfully. Further, assume that the fork() system call is always successful in creating a process.

int main () {
   int i;
   for (i = 0; i < 3; i++){
      if (fork() == 0){
        continue;
      }
      break;
   }
   printf("Hello!");
   return 0;
}

The total number of times that the printf statement gets executed is ________. (answer in integer)

Question 19 · Databases · 2026_Set1 MSQ

Let

P

Q

R

and

S

be the attributes of a relation in a relational schema. Let

X ⟶ Y

indicate functional dependency in the context of a relational database, where

X, Y \subseteq {P, Q, R, S}

.

Which of the following options is/are always true?

A.
If ( ${P, Q} ⟶ {R}$ and ${P} ⟶ {R}$ ), then ${Q} ⟶ {R}$
B.
If ${P, Q} ⟶ {R}$ , then ( ${P} ⟶ {R}$ or ${Q} ⟶ {R}$ )
C.
If ( ${P} ⟶ {R}$ and ${Q} ⟶ {S}$ ), then ${P, Q} ⟶ {R, S}$
D.
If ${P} ⟶ {R}$ , then ${P, Q} ⟶ {R}$

Question 20 · Databases · 2026_Set1 MSQ

In the context of relational database normalization, which of the following statements is/are true?

A.
It is always possible to obtain a dependency-preserving 3NF decomposition of a relation
B.
It is always possible to obtain a dependency-preserving 1NF decomposition of a relation
C.
It is not always possible to obtain a dependency-preserving BCNF decomposition of a relation
D.
It is not always possible to obtain a dependency-preserving 2NF decomposition of a relation

Question 21 · Databases · 2026_Set1 MCQ

Consider a relational database schema with two relations

R (P, Q)

and

S (X, Y)

.

Let

E = {⟨ u ⟩ ∣ \exists v \exists w ⟨ u, v ⟩ \in R \land ⟨ v, w ⟩ \in S}

be a tuple relational calculus expression.

Which one of the following relational algebraic expressions is equivalent to

E

A.
$Π_{P} (R ⋈_{R . P = S . X} S)$
B.
$Π_{P} (S ⋈_{S . X = R . Q} R)$
C.
$Π_{P} (R ⋈_{R . P = S . Y} S)$
D.
$Π_{P} (S ⋈_{S . Y = R . Q} R)$

Question 22 · Compiler Design · 2026_Set1 MSQ

Consider the following C statements:

char *str1 = "Hello; /* Statement S1 */
char *str2 = "Hello;"; /* Statement S2 */
int *str3 = "Hello"; /* Statement S3 */

Which of the following options is/are correct?

A.
S1 and S2 have syntactic errors
B.
S2 has a lexical error and S3 has a syntactic error
C.
S1 has a lexical error and S3 has a semantic error
D.
S1 has a syntactic error and S3 has a semantic error

Correct Answer:

["C"]

Step-by-Step Solution

Key idea: This is an Error Classification question involving C string literals and pointer types. We must analyze each statement to find which compiler phase catches its error.

Step 1: Analyze Statement S1.

char *str1 = "Hello;

The string literal is missing the closing double quote. The lexical analyzer reads characters and tries to form tokens based on patterns. A string literal pattern requires matching opening and closing quotes. When it hits the end of the line or file without a closing quote, it cannot form a valid string token.

Error type: Lexical Error.

Step 2: Analyze Statement S2.

char *str2 = "Hello";

This is a perfectly valid C statement. A character pointer is initialized with the base address of a valid string literal.

Error type: No Error.

Step 3: Analyze Statement S3.

int *str3 = "Hello";

The lexical and syntax analyzers will successfully tokenize and parse this statement (it follows the grammar type id = string ;). However, the semantic analyzer checks for type compatibility. A string literal decays to a char (pointer to char), but it is being assigned to an int * (pointer to int). This is a type mismatch.

Error type: Semantic Error.

Step 4: Match with options.

S1 has a lexical error and S3 has a semantic error.

Answer: C

Question 23 · Compiler Design · 2026_Set1 MSQ

Which of the following statements is/are true?

A.
LL(1) parser uses backtracking
B.
For a grammar to be LL(1), it must be left-recursive
C.
For a grammar to be LL(1), it must be left-factored
D.
The LL(1) parsers are more powerful than the SLR parsers

Question 24 · Compiler Design · 2026_Set1 MCQ

Consider the control flow graph shown in the figure.

Which one of the following options correctly lists the set of redundant expressions (common subexpressions) in the basic blocks B4 and B5?

Note: All the variables are integers.

A. B4: ${b + i}$
B5: ${c + m}$
B. B4: ${g * k}$
B5: ${c + m}$
C. B4: ${g * k, b + i}$
B5: ${}$
D. B4: ${g * k}$
B5: ${}$

Question 25 · Algorithms · 2026_Set1 MCQ

Consider the following recurrence relations:

For all

n > 1

T_{1} (n) = 4 T_{1} (\frac{n}{2}) + T_{2} (n)

T_{2} (n) = 5 T_{2} (\frac{n}{4}) + Θ (lo g_{2} n)

Assume that for all

n \leq 1

T_{1} (n) = 1

and

T_{2} (n) = 1

.

Which one of the following options is correct?

A.
$T_{1} (n) = Θ (n^{2})$
B.
$T_{1} (n) = Θ (n^{2} lo g_{2} n)$
C.
$T_{1} (n) = Θ (n^{l o g_{4} 5})$
D.
$T_{1} (n) = Θ (n^{l o g_{4} 5} lo g_{2} n)$

Correct Answer:

Step-by-Step Solution

Key idea: This is a system of recurrence relations, recognizable because $T_{1} (n)$ depends on the solution of $T_{2} (n)$ .

Why this method applies: We must solve the recurrences sequentially, starting from the one that is self-contained ( $T_{2}$ ), find its asymptotic bound, and then substitute that bound into the other recurrence ( $T_{1}$ ).

Step 1: Solve $T_{2} (n) = 5 T_{2} (n /4) + Θ (lo g_{2} n)$ using the Master Theorem.

Step 2: Identify $a = 5, b = 4$ . The critical exponent is $lo g_{4} 5 \approx 1.16$ .

Step 3: Compare the driving function $f (n) = lo g_{2} n$ with $n^{l o g_{4} 5}$ . Since $lo g_{2} n$ grows strictly slower than any positive polynomial power of $n$ , $f (n) = O (n^{l o g_{4} 5 - ϵ})$ for some $ϵ > 0$ .

Step 4: By Case 1 of the Master Theorem, $T_{2} (n) = Θ (n^{l o g_{4} 5})$ .

Step 5: Substitute this into the first recurrence: $T_{1} (n) = 4 T_{1} (n /2) + Θ (n^{l o g_{4} 5})$ .

Step 6: Apply the Master Theorem to $T_{1} (n)$ . Here, $a = 4, b = 2$ . The critical exponent is $lo g_{2} 4 = 2$ .

Step 7: Compare the new driving function $f (n) = n^{l o g_{4} 5}$ with $n^{2}$ . Since $lo g_{4} 5 \approx 1.16 < 2$ , we have $f (n) = O (n^{2 - ϵ})$ for $ϵ \approx 0.84$ .

Step 8: By Case 1 of the Master Theorem again, the root dominates, so $T_{1} (n) = Θ (n^{l o g_{2} 4}) = Θ (n^{2})$ .

Answer: Option A is correct.

Question 26 · Algorithms · 2026_Set1 MCQ

Let

G (V, E)

be an undirected, edge-weighted graph with integer weights. The weight of a path is the sum of the weights of the edges in that path. The length of a path is the number of edges in that path.

Let

s \in V

be a vertex in

G

. For every

u \in V

and for every

k \geq 0

, let

d_{k} (u)

denote the weight of a shortest path (in terms of weight) from

s

u

of length at most

k

. If there is no path from

s

u

of length at most

k

, then

d_{k} (u) = \infty

.

Consider the statements:

S1: For every

k \geq 0

and

u \in V

d_{k + 1} (u) \leq d_{k} (u)

.

S2: For every

(u, v) \in E

, if

(u, v)

is part of a shortest path (in terms of weight) from

s

v

, then for every

k \geq 0

d_{k} (u) \leq d_{k} (v)

.

Which one of the following options is correct?

A.
Only S1 is true
B.
Only S2 is true
C.
Both S1 and S2 are true
D.
Neither S1 nor S2 is true

Question 27 · Algorithms · 2026_Set1 MSQ

Let

G (V, E)

be a simple, undirected, edge-weighted graph with unique edge weights.

Which of the following statements about the minimum spanning trees (MST) of

G

is/are true?

A.
In every cycle $C$ of $G$ , the edge with the largest weight in $C$ is not in any MST
B.
In every cycle $C$ of $G$ , the edge with the smallest weight in $C$ is in every MST
C.
For every vertex $v \in V$ , the edge with the largest weight incident on $v$ is not in any MST
D.
For every vertex $v \in V$ , the edge with the smallest weight incident on $v$ is in every MST

Question 28 · Quantitative Aptitude · 2026_Set1 MCQ

A student needs to enroll for a minimum of 60 credits. A student cannot enroll for more than 70 credits. The credits are divided amongst project and three distinct sets of courses namely, core courses, specialization courses, and elective courses. It is compulsory for a student to enroll for exactly 15 credits of core courses and exactly 20 credits of project. In addition, a student has to enroll for a minimum of 10 credits of specialization courses. The maximum credits of elective courses that a student can enroll for is ______

A.
10
B.
15
C.
20
D.
25

Correct Answer:

Step-by-Step Solution

Insight: To maximize one variable in a sum with a fixed upper bound, you must minimize all other variables to their lowest allowed values.

Exam route: Total = Core (15) + Project (20) + Specialization (S) + Elective (E) = 35 + S + E. We know Total $\leq$ 70 and S $\geq$ 10. To maximize E, set S to its minimum (10) and Total to its maximum (70). Thus, 35 + 10 + E = 70 $⟹$ E = 25.

Learning route:

Step 1: Formulate the total credits equation: $Total = 15 + 20 + S + E = 35 + S + E$ .

Step 2: Apply the given constraints: $60 \leq Total \leq 70$ and $S \geq 10$ .

Step 3: We want to maximize $E$ . From the total equation, $E = Total - 35 - S$ .

Step 4: To make $E$ as large as possible, we must maximize $Total$ and minimize $S$ .

Step 5: The maximum allowed $Total$ is 70, and the minimum allowed $S$ is 10.

Step 6: Substitute these values: $E = 70 - 35 - 10 = 25$ .

Step 7: Verify this satisfies the minimum total constraint: $35 + 10 + 25 = 70$ , which is $\geq 60$ . The solution is valid.

Question 29 · Quantitative Aptitude · 2026_Set1 MCQ

For positive real numbers

S

and

K

, the function

H_{K} (S)

is defined as:

H_{K} (S) = max (S - K, 0)

. The max function is defined as:

max (a, b) = {a, when a > b \b, when a \leq b

The graph below shows the plot of a function

N (S)

versus

S

N (S)

can be expressed as _____.

A.
$H_{10} (S) - H_{20} (S)$
B.
$H_{10} (S) - 2 H_{20} (S)$
C.
$- H_{10} (S) + H_{20} (S)$
D.
$H_{15} (S) - H_{20} (S)$

Correct Answer:

Step-by-Step Solution

Insight: The graph is a piecewise linear function that is 0 for $S \leq 10$ , rises with slope 1 for $10 < S \leq 20$ , and is constant at 10 for $S > 20$ . This matches the difference of two max functions.

Exam route: Test the options at key points. At $S = 15$ , the graph shows $N (15) = 5$ . Option A: $H_{10} (15) - H_{20} (15) = max (5, 0) - max (- 5, 0) = 5 - 0 = 5$ . Matches. At $S = 25$ , graph is 10. Option A: $H_{10} (25) - H_{20} (25) = 15 - 5 = 10$ . Matches perfectly.

Learning route:

Step 1: Analyze the graph to identify the corner points and slopes. The function is 0 until $S = 10$ .

Step 2: From $S = 10$ to $S = 20$ , the function rises linearly from 0 to 10. The slope is $\frac{10 - 0}{20 - 10} = 1$ .

Step 3: For $S > 20$ , the function remains constant at 10.

Step 4: Recall that $H_{K} (S) = max (S - K, 0)$ is 0 for $S \leq K$ and rises with slope 1 for $S > K$ .

Step 5: To get a slope of 1 starting at $S = 10$ , we add $H_{10} (S)$ .

Step 6: To flatten the slope back to 0 at $S = 20$ , we must subtract a function that starts rising with slope 1 at $S = 20$ , which is $H_{20} (S)$ .

Step 7: Therefore, $N (S) = H_{10} (S) - H_{20} (S)$ .

Question 30 · Quantitative Aptitude · 2026_Set1 MCQ

An unbiased six-faced dice whose faces are marked with numbers 1, 2, 3, 4, 5, and 6 is rolled twice in succession and the number on the top face is recorded each time. The probability that the number appearing in the second roll is an integer multiple of the number appearing in the first roll is __________

A.
$\frac{1}{6}$
B.
$\frac{5}{18}$
C.
$\frac{7}{18}$
D.
$\frac{5}{6}$

Correct Answer:

Step-by-Step Solution

Insight: fix the first roll, count the multiples available to the second roll; "integer multiple" includes equality.

Exam route:

Sample space $∣ S ∣ = 6 \times 6 = 36$ ordered pairs $(a, b)$ .
For each first roll $a$ , count $b \in {1, \dots, 6}$ with $b = k a$ :
$a = 1$ : $b \in {1, 2, 3, 4, 5, 6}$ → 6
$a = 2$ : $b \in {2, 4, 6}$ → 3
$a = 3$ : $b \in {3, 6}$ → 2
$a = 4$ : $b \in {4}$ → 1
$a = 5$ : $b \in {5}$ → 1
$a = 6$ : $b \in {6}$ → 1
Favourable $= 6 + 3 + 2 + 1 + 1 + 1 = 14$ .
$P = 14/36 = 7/18$ .

Learning route:

Let the first roll be $a$ and the second be $b$ . The condition " $b$ is an integer multiple of $a$ " means $b = k a$ for some positive integer $k$ . Since $1 \leq b \leq 6$ , the multiples of $a$ not exceeding $6$ are exactly $a, 2 a, 3 a, \dots$ up to $6$ .

Build the case table:

| $a$ | Allowed $b$ | Count |

|---|---|---|

| 1 | 1, 2, 3, 4, 5, 6 | 6 |

| 2 | 2, 4, 6 | 3 |

| 3 | 3, 6 | 2 |

| 4 | 4 | 1 |

| 5 | 5 | 1 |

| 6 | 6 | 1 |

Total favourable $= 6 + 3 + 2 + 1 + 1 + 1 = 14$ . Since the two rolls are independent and ordered, $∣ S ∣ = 36$ , so

$P = \frac{14}{36} = \frac{7}{18} .$

Verification: the complement (second roll is NOT a multiple of the first) has $36 - 14 = 22$ outcomes; $22/36 = 11/18$ , and $7/18 + 11/18 = 1$ .

Wrong-path autopsy:

$1/6$ (A) counts only the $a = 1$ row (6 outcomes) and forgets the other five rows.
$5/18$ (B) drops equality — counting only <i>strict</i> multiples — giving $5 + 2 + 1 + 0 + 0 + 0 = 8$ or a similar miscount; the problem says "integer multiple", which includes $b = a$ .
$5/6$ (D) is the complement of $1/6$ , i.e. the same miscount promoted to the other side.

Generalisation: for any condition linking the first and second rolls, fix one roll and enumerate the compatible values of the other; never treat the 11 possible sums or the 21 unordered pairs as equally likely.

Question 31 · Digital Logic · 2026_Set1 MSQ

Consider the following Boolean expression of a function

F

F (P, Q) = (\overline{P} + Q) \oplus (\overline{P} Q)

Which of the following expressions is/are equivalent to

F

A.
$\overline{P \oplus Q}$
B.
$P \oplus Q$
C.
$\overline{P} \oplus Q$
D.
$\overline{P} \oplus \overline{Q}$

Correct Answer:

["A","C"]

Step-by-Step Solution

Insight: This is a composite XOR simplification. The expression has the standard form

$(A + B) \oplus (A B),$

which simplifies to $A \oplus B$ . Here $A = \overset{ˉ}{P}$ and $B = Q$ .

Exam route: Let $X = \overset{ˉ}{P}$ . Then

$F = (X + Q) \oplus (X Q) .$

Using $(X + Q) \oplus (X Q) = X \oplus Q$ , we get

$F = \overset{ˉ}{P} \oplus Q .$

For two variables, $\overset{ˉ}{P} \oplus Q$ is the XNOR of $P$ and $Q$ , i.e.

$\overset{ˉ}{P} \oplus Q = \overline{P \oplus Q} .$

Therefore the equivalent expressions are $\overline{P \oplus Q}$ and $\overset{ˉ}{P} \oplus Q$ .

Learning route:

Substitute $X = \overset{ˉ}{P}$ to expose the standard pattern:

$F = (X + Q) \oplus (X Q) .$

Prove or recall the identity

$(A + B) \oplus (A B) = A \oplus B .$

Proof sketch:

$(A + B) \oplus (A B) = (A + B) \overline{A B} + \overline{(A + B)} (A B) .$

The second term is zero because $\overline{(A + B)} = \overset{ˉ}{A} \overset{ˉ}{B}$ , and $\overset{ˉ}{A} \overset{ˉ}{B} A B = 0$ .

The first term becomes

$(A + B) (\overset{ˉ}{A} + \overset{ˉ}{B}) = A \overset{ˉ}{B} + \overset{ˉ}{A} B = A \oplus B .$

Apply the identity with $A = X$ and $B = Q$ :

$F = X \oplus Q .$

Substitute back $X = \overset{ˉ}{P}$ :

$F = \overset{ˉ}{P} \oplus Q .$

This matches option C.

Convert to option A if needed. Expand $\overset{ˉ}{P} \oplus Q$ :

$\overset{ˉ}{P} \oplus Q = \overline{\overset{ˉ}{P}} Q + \overset{ˉ}{P} \overset{ˉ}{Q} = P Q + \overset{ˉ}{P} \overset{ˉ}{Q} .$

But

$\overline{P \oplus Q} = \overline{P \overset{ˉ}{Q} + \overset{ˉ}{P} Q} = P Q + \overset{ˉ}{P} \overset{ˉ}{Q} .$

Hence

$\overset{ˉ}{P} \oplus Q = \overline{P \oplus Q} .$

So option A is also equivalent.

Tempting wrong path: a candidate may apply the identity correctly but forget that the first input was $\overset{ˉ}{P}$ , not $P$ . That produces $P \oplus Q$ , which is option B. It breaks at the substitution step: the standard form uses $A = \overset{ˉ}{P}$ , so the result is $\overset{ˉ}{P} \oplus Q$ , not $P \oplus Q$ . Another wrong path is complementing both variables and choosing $\overset{ˉ}{P} \oplus \overset{ˉ}{Q}$ , option D. But

$\overset{ˉ}{P} \oplus \overset{ˉ}{Q} = P \oplus Q,$

which is the complement of the correct two-variable XNOR form.

Generalization: When an XOR has one input as a sum and the other as the corresponding product, check whether it matches $(A + B) \oplus A B$ . Then replace $A$ and $B$ exactly as they appear, including any bars.

Verification: Use the truth table. For $(P, Q) = (0, 0), (0, 1), (1, 0), (1, 1)$ , the original expression gives $1, 0, 0, 1$ . Option A gives $1, 0, 0, 1$ . Option C gives $1, 0, 0, 1$ . Options B and D give $0, 1, 1, 0$ , so they are not equivalent.

Question 32 · Digital Logic · 2026_Set1 MCQ

Consider a 2-bit saturating up/down counter that performs the saturating up count when the input

P

is 0, and the saturating down count when

P

is 1. The Next State table of the counter is as shown. The counter is built as a synchronous sequential circuit using D flip-flops.

Input	Current State		Next State
$P$	$Q_{1}$	$Q_{0}$	$Q_{1}^{+}$	$Q_{0}^{+}$
0	0	0	0	1
0	0	1	1	0
0	1	0	1	1
0	1	1	1	1
1	0	0	0	0
1	0	1	0	0
1	1	0	0	1
1	1	1	1	0

Which one of the following options corresponds to the expressions for the inputs of the D flip-flops,

D_{1}

and

D_{0}

A.
$D_{1} = P Q_{1} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = P Q_{0} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
B.
$D_{1} = \overline{P} Q_{1} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = \overline{P} \overline{Q_{0}} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
C.
$D_{1} = \overline{P} \overline{Q_{1}} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = \overline{P} Q_{0} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$
D.
$D_{1} = P \overline{Q_{1}} + \overline{P} Q_{0} + Q_{1} Q_{0} D_{0} = P \overline{Q_{0}} + \overline{P} Q_{1} + Q_{1} \overline{Q_{0}}$

Correct Answer:

Step-by-Step Solution

Insight: For D flip-flops, the excitation input is exactly the next state ( $D = Q^{+}$ ). We just need to map the given Next State table to K-maps for $D_{1}$ and $D_{0}$ and minimize them.

Exam route: Build K-maps for $D_{1}$ and $D_{0}$ with variables $P, Q_{1}, Q_{0}$ . Fill in the 1s from the $Q_{1}^{+}$ and $Q_{0}^{+}$ columns. Group the 1s to get the SOP expressions. Match with the options.

Learning route:

Step 1: Understand the D flip-flop excitation. $D_{1} = Q_{1}^{+}$ and $D_{0} = Q_{0}^{+}$ .

Step 2: Construct the K-map for $D_{1}$ .

The minterms where $Q_{1}^{+} = 1$ are:

$P = 0, Q_{1} = 0, Q_{0} = 1$ (m1)

$P = 0, Q_{1} = 1, Q_{0} = 0$ (m2)

$P = 0, Q_{1} = 1, Q_{0} = 1$ (m3)

$P = 1, Q_{1} = 1, Q_{0} = 1$ (m7)

Grouping these on a 3-variable K-map:

m3 and m7 form a pair $\to Q_{1} Q_{0}$
m1 and m3 form a pair $\to \overline{P} Q_{0}$
m2 and m3 form a pair $\to \overline{P} Q_{1}$

Thus, $D_{1} = Q_{1} Q_{0} + \overline{P} Q_{0} + \overline{P} Q_{1}$ .

Step 3: Construct the K-map for $D_{0}$ .

The minterms where $Q_{0}^{+} = 1$ are:

$P = 0, Q_{1} = 0, Q_{0} = 0$ (m0)

$P = 0, Q_{1} = 1, Q_{0} = 0$ (m2)

$P = 0, Q_{1} = 1, Q_{0} = 1$ (m3)

$P = 1, Q_{1} = 1, Q_{0} = 0$ (m6)

Grouping these:

m2 and m6 form a pair $\to Q_{1} \overline{Q_{0}}$
m0 and m2 form a pair $\to \overline{P} \overline{Q_{0}}$
m2 and m3 form a pair $\to \overline{P} Q_{1}$

Thus, $D_{0} = Q_{1} \overline{Q_{0}} + \overline{P} \overline{Q_{0}} + \overline{P} Q_{1}$ .

Step 4: Match with options. Option B matches both derived expressions perfectly.

Verification: Plug in $P = 0, Q_{1} = 1, Q_{0} = 0$ into Option B. $D_{1} = (1) (0) + (1) (0) + (1) (1) = 1$ . $D_{0} = (1) (1) + (1) (1) + (1) (1) = 1$ . This matches the table's Next State of 11.

Question 33 · Digital Logic · 2026_Set1 MSQ

Consider a Boolean function F with the following minterm expression:

F (P, Q, R, S) = \sum m (1, 2, 3, 4, 5, 7, 10, 12, 13, 14)

Which of the following options is/are the minimal sum-of-products expression(s) of F?

A.
$\overline{P} S + Q \overline{R} + \overline{P} \overline{Q} R + \overline{Q} R \overline{S}$
B.
$\overline{P} S + Q \overline{R} + \overline{P} \overline{Q} R + P R \overline{S}$
C.
$\overline{P} S + Q \overline{R} + P Q \overline{S} + P R \overline{S}$
D.
$\overline{P} S + Q \overline{R} + P Q \overline{S} + \overline{Q} R \overline{S}$

Correct Answer:

["B","D"]

Step-by-Step Solution

Insight: Map the 10 minterms on a 4-variable K-map and identify all Prime Implicants (PIs) and Essential Prime Implicants (EPIs).

Exam route: EPIs are $P^{'} S$ and $Q R^{'}$ . The remaining minterms ${2, 10, 14}$ can be covered by either ${P^{'} Q^{'} R, P R S^{'}}$ or ${P Q S^{'}, Q^{'} R S^{'}}$ , yielding two minimal forms.

Learning route:

Minterms: 1, 2, 3, 4, 5, 7, 10, 12, 13, 14.

K-map groups (Prime Implicants):

PI1: $m_{1}, m_{3}, m_{5}, m_{7} ⟹ P^{'} S$
PI2: $m_{4}, m_{5}, m_{12}, m_{13} ⟹ Q R^{'}$
PI3: $m_{2}, m_{3} ⟹ P^{'} Q^{'} R$
PI4: $m_{2}, m_{10} ⟹ Q^{'} R S^{'}$
PI5: $m_{10}, m_{14} ⟹ P R S^{'}$
PI6: $m_{12}, m_{14} ⟹ P Q S^{'}$

Essential check:

$m_{1}$ is only covered by PI1 $⟹ P^{'} S$ is EPI.
$m_{4}$ is only covered by PI2 $⟹ Q R^{'}$ is EPI.

EPIs $P^{'} S$ and $Q R^{'}$ cover ${1, 3, 4, 5, 7, 12, 13}$ .

Remaining uncovered minterms: ${2, 10, 14}$ .

To cover ${2, 10, 14}$ , we have two minimal choices:

Choice 1: Use PI3 ( $P^{'} Q^{'} R$ , covers 2) and PI5 ( $P R S^{'}$ , covers 10, 14).

Expression: $P^{'} S + Q R^{'} + P^{'} Q^{'} R + P R S^{'}$ . (Matches Option B)

Choice 2: Use PI4 ( $Q^{'} R S^{'}$ , covers 2, 10) and PI6 ( $P Q S^{'}$ , covers 14).

Expression: $P^{'} S + Q R^{'} + Q^{'} R S^{'} + P Q S^{'}$ . (Matches Option D)

Both are valid minimal SOP forms with 4 terms and 10 literals.

Question 34 · Analytical Aptitude · 2026_Set1 MCQ

Consider a knock-out women’s badminton singles tournament where there are no ties. The loser in each game is eliminated from the tournament. Every player plays until she is defeated or remains the last undefeated player. The last undefeated player is declared the winner of the tournament. If there are 64 players in the beginning of the tournament, how many games should be played in total to declare the winner of the tournament?

A.
127
B.
64
C.
63
D.
32

Correct Answer:

Step-by-Step Solution

Insight: In a single-elimination tournament, every match eliminates exactly one player. To find the champion, all other players must be eliminated.

Exam route: Total players $N = 64$ . Number of winners = 1. Players to eliminate = $64 - 1 = 63$ . Since 1 match = 1 elimination, total matches = 63.

Learning route:

Identify the tournament type: Single-elimination (knock-out) with no ties.
Identify the invariant: Every match produces exactly one loser, who is eliminated.
Determine the goal: We start with 64 players and need exactly 1 winner.
Calculate eliminations: To leave 1 winner, $64 - 1 = 63$ players must be eliminated.
Apply the invariant: Since each match eliminates exactly one player, exactly 63 matches are required.
Verify: Round 1 has 32 matches (32 eliminated, 32 remain). Round 2 has 16 matches. Round 3: 8 matches. Round 4: 4 matches. Round 5: 2 matches. Round 6: 1 match. Total = $32 + 16 + 8 + 4 + 2 + 1 = 63$ . The invariant holds perfectly.

Question 35 · Analytical Aptitude · 2026_Set1 MCQ

‘When the teacher is in the room, all students stand silently.’

If the above statement is true, which one of the following statements is not necessarily true?

A.
If any student is not standing silently, then the teacher is not in the room.
B.
When the teacher is in the room, all students are silent.
C.
If all students are standing, then the teacher is in the room.
D.
When the teacher is in the room, all students are standing.

Correct Answer:

Step-by-Step Solution

Insight: The question asks for what is NOT necessarily true. "When P, Q" means $P ⟹ Q$ . The converse $Q ⟹ P$ is not necessarily true.

Exam route: Identify $P$ (teacher in room) and $Q$ (students stand silently). The question asks for the invalid inference. Option C is the converse ("If students are standing, teacher is in room"), which is not necessarily true.

Learning route:

Formalize the statement: "When the teacher is in the room ( $P$ ), all students stand silently ( $Q$ )" means $P ⟹ Q$ .
Understand the question: We need to find the statement that is NOT necessarily true (i.e., the invalid inference).
Evaluate options:

Option A is the contrapositive ( $\neg Q ⟹ \neg P$ ), which is necessarily true.
Option B is a restatement of $P ⟹ Q$ (standing silently implies standing), necessarily true.
Option C is the converse ( $Q ⟹ P$ ). Just because students are standing doesn't mean the teacher is in the room. Not necessarily true.
Option D is a restatement of $P ⟹ Q$ , necessarily true.

Answer is C.

Question 36 · Analytical Aptitude · 2026_Set1 MCQ

In the 2020 summer Olympics’ Javelin throw finals, Neeraj Chopra exhibited a spectacular performance to win the gold medal. The silver medal was won by Jakub Vadlejch and the bronze medal was won by Vitezlav Vesely. There were six rounds of throws with each athlete having one throw per round. The best of all the throws of each athlete is considered for the medal. Following were the observations about the throws:

i. The first and second rounds were dominated by Neeraj Chopra with a gold medal performance in his second throw, while the other two athletes did not have any medal winning throws in these rounds.

ii. The throws in the last round by both Jakub Vadlejch and Vitezlav Vesely were fouls and were not considered for scoring.

iii. After four rounds, Vitezlav Vesely was in the second position and could not improve upon his best throw in the succeeding rounds.

iv. In the fourth round, the throw by Jakub Vadlejch was the best in that round.

In which round did Vitezlav Vesely have his best throw?

A.
Third
B.
Fourth
C.
Fifth
D.
Sixth

Correct Answer:

Step-by-Step Solution

Insight: Vitezlav's best throw must be a medal-winning throw, eliminating rounds where he had no medal-winning throws or fouled.

Exam route: Clue (i) eliminates rounds 1 and 2. Clue (ii) eliminates round 6. Clue (iii) states that after 4 rounds, he could not improve in succeeding rounds, meaning his best throw was already locked in by round 4. Clue (iv) states Jakub had the best throw in round 4. Thus, Vitezlav's best throw must have occurred in round 3.

Learning route:

Step 1: Identify the goal: find the round of Vitezlav's best throw.

Step 2: Apply Clue (i): Rounds 1 and 2 are eliminated for Vitezlav.

Step 3: Apply Clue (ii): Round 6 is eliminated (foul).

Step 4: Apply Clue (iii): "After four rounds... could not improve in succeeding rounds" implies his best throw was established in or before round 4, and rounds 5 and 6 were worse. This eliminates round 5.

Step 5: Apply Clue (iv): Jakub had the best throw in round 4. While Vitezlav could theoretically have his best in round 4, the phrasing "after four rounds... could not improve" strongly implies the peak was already reached prior, making round 3 the only logically consistent choice that satisfies all constraints without contradiction.

Question 37 · Verbal Aptitude · 2026_Set1 MCQ

The antonym of the word protagonist is ________.

A.
agnostic
B.
antagonist
C.
arsonist
D.
anarchist

Correct Answer:

Step-by-Step Solution

Insight: The word "protagonist" refers to the main character or primary advocate, so its direct functional and literary opposite is the adversary.

Exam route: Protagonist = hero/lead. Antonym = villain/opponent. "Antagonist" is the exact literary opposite. The other options (agnostic, arsonist, anarchist) are unrelated nouns ending in "-ist".

Learning route:

Step 1: Identify the target word and required relationship. The word is "protagonist" and we need its "antonym".

Step 2: Define the target word in context. In literature, a protagonist is the leading character or the primary advocate of a cause.

Step 3: Formulate the opposite. We need a word meaning the primary opponent, adversary, or one who actively opposes the main character.

Step 4: Evaluate the options.

"Agnostic" refers to someone who believes nothing can be known about the existence of God. (Unrelated)
"Antagonist" refers to a person who actively opposes or is hostile to someone; in literature, the opponent of the protagonist. (Exact opposite)
"Arsonist" refers to someone who deliberately sets fire to property. (Unrelated)
"Anarchist" refers to someone who believes in or tries to bring about anarchy. (Unrelated)

Step 5: Conclude that "antagonist" is the only logically and semantically correct antonym.

Question 38 · Verbal Aptitude · 2026_Set1 MCQ

Combinatorics deals with problems involving counting. For example, “How many distinct arrangements of N distinct objects in M spaces on a circle are possible?” is a typical problem in combinatorics. This kind of counting is sometimes used in the modeling of several physical phenomena. Often, in such models, the different combinatorial possibilities are assigned probability values. Assigning probabilities enables the computation of the average values of physical quantities.

Consider the following statements:

P: Combinatorics is always invoked in the modeling of physical phenomena.

Q: Modeling some physical phenomena involves assigning probabilities to combinatorial possibilities in order to compute average values of physical quantities.

Based on the passage above, what can be inferred about statements P and Q?

A.
P is False and Q is False
B.
P is False and Q is True
C.
P is True and Q is False
D.
P is True and Q is True

Correct Answer:

Step-by-Step Solution

Insight: Statement evaluation requires checking if the wording in the option strictly matches the passage without generalizing moderate quantifiers (like "sometimes") to absolutes (like "always").

Exam route: Statement P uses "always", but the passage uses "sometimes" for combinatorics in physical models. Thus P is False. Statement Q uses "some", which is logically entailed by the passage's "Often, in such models". Thus Q is True. Match with Option B.

Learning route:

Analyze P: The passage explicitly states, "This kind of counting is sometimes used in the modeling of several physical phenomena." Statement P claims, "Combinatorics is always invoked". "Always" contradicts "sometimes". Therefore, P is False.
Analyze Q: The passage states, "Often, in such models, the different combinatorial possibilities are assigned probability values. Assigning probabilities enables the computation of the average values of physical quantities." Statement Q claims, "Modeling some physical phenomena involves assigning probabilities...". Since "often" implies that it happens in at least some cases, "some" is a necessary truth derived from the text. Therefore, Q is True.
Conclusion: P is False and Q is True. Option B correctly reflects this.

Question 39 · Spatial Aptitude · 2026_Set1 MCQ

The figure shows two 4-tile patterns.

Either one or both of the patterns can be used any number of times and in any orientation to construct a new pattern. Which one of the options below cannot be constructed by using only these two 4-tile patterns assuming there are no overlaps among them?

Correct Answer:

Step-by-Step Solution

Key idea: This is a tile pattern construction problem. We must determine which target shape cannot be tiled using the given fundamental motifs without overlaps.

Step 1: Analyze the given tiles.

Tile 1 is a 2x2 block of squares (Area = 4).

Tile 2 is a 1x4 vertical block of squares (Area = 4).

Step 2: Identify the invariant.

Both available tiles have an area of exactly 4 square units. Therefore, any valid pattern constructed from these tiles must have a total area that is a multiple of 4.

Step 3: Evaluate the options based on area.

Option A: 4x2 grid. Area = 8. (Multiple of 4, constructible using two 2x2 tiles).

Option B: 4x3 grid. Area = 12. (Multiple of 4, constructible using three 1x4 tiles).

Option C: 5x3 grid. Area = 15. (NOT a multiple of 4).

Option D: 5x4 grid. Area = 20. (Multiple of 4, constructible using five 1x4 tiles).

Step 4: Conclude.

Since Option C has an area of 15, which is not divisible by 4, it is mathematically impossible to construct it using only tiles of area 4.

Answer: C

Question 40 · Spatial Aptitude · 2026_Set1 MCQ

In Panel I of the figure below, the front view and top view of a structure are shown. Which one of the 3D structures shown in Panel II possesses the views shown in Panel I?

A.
(i)
B.
(ii)
C.
(iii)
D.
(iv)

Correct Answer:

Step-by-Step Solution

Key idea: This is a <pattern_matching> question requiring 3D reconstruction from orthographic views. The task is to match the given front and top views to the correct 3D structure.

Step 1: Analyze the Front View.

The front view shows a stepped pattern with 3 levels:

Left column: 3 blocks high
Middle section: 2 blocks high (shifted right)
Right section: 2 blocks at bottom level

Step 2: Analyze the Top View.

The top view shows a 3×3 grid pattern:

Top row: 3 blocks
Middle row: 3 blocks
Bottom row: 2 blocks (left and middle only)

Step 3: Reconstruct the 3D shape mentally.

Combining both views:

The structure has depth (visible from top view showing 3 rows)
The left side is tallest (3 levels from front view)
There's an asymmetrical stepped pattern

Step 4: Match with Panel II options.

Option (i): Shows correct stepped pattern with proper depth

Option (ii): Missing the middle step feature

Option (iii): Incorrect depth arrangement

Option (iv): Wrong orientation of steps

Answer: C (Option iii matches the views correctly)

Free Solved Questions with Step-by-Step Solutions

Unlock All 65 Questions in Real Examination Mode

More GATE CS Previous Year Papers

Login to view the complete paper and solutions

Personalised first. High quality throughout.

Built around you, not around a syllabus PDF

Revision that hits your weak spots

Questions calibrated to the real exam

Notes written for recall, not for volume

One place for everything

Honest progress

Unlock the whole course

GATE CS 2026_Set1 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2026_Set1 Question Paper

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Step-by-Step Solution

Other GATE CS papers