What subjects are covered in GATE 2026 CS Set 1 questions?

GATE 2026 CS Set 1 covers Algorithm Analysis (recurrence relations, shortest path properties), Graph Theory (vertex cover, MST cycle property, DFS on DAG discovery/finish times, 2-colorable/bipartite graphs), Compiler Design (LL(1) grammar requirements, Common Subexpression Elimination, lexical/syntactic/semantic errors, Syntax-Directed Definitions), Computer Networks (CIDR supernetting, HTTP 1.1 persistent connections, TCP slow-start congestion control), and General Aptitude.

What is the answer for the recurrence T1(n)=4T1(n/2)+T2(n) in GATE 2026 CS Set 1?

The correct answer is Option A: T1(n) = Θ(n²). First solve T2(n) = 5T2(n/4) + Θ(log²n). By Master theorem: a=5, b=4, f(n)=Θ(log²n), n^(log₄5) ≈ n^1.16. Since f(n) = log²n is polynomially smaller than n^1.16, T2(n) = Θ(n^log₄5). Now solve T1(n) = 4T1(n/2) + T2(n) = 4T1(n/2) + Θ(n^log₄5). a=4, b=2, n^(log₂4) = n². Since log₄5 ≈ 1.16 < 2, T2(n) is smaller than n², so T1(n) = Θ(n²) by Master theorem case 1.

Which statements about MST cycle and vertex properties are TRUE in GATE 2026 CS Set 1?

The correct answers are A, B, and D. A: In every cycle C, the edge with largest weight is NOT in any MST — TRUE (cycle property: the max-weight edge in any cycle can always be removed without disconnecting the graph). B: The smallest weight edge in every cycle IS in every MST — TRUE (cut property applied to cycles). D: For every vertex v, the minimum weight incident edge IS in every MST — TRUE (cut property: the lightest edge crossing any cut must be in the MST). C is FALSE — the largest incident edge may or may not be in an MST depending on global structure.

What is the TCP congestion control segment 2000 start time in GATE 2026 CS Set 1?

The correct answer is Option D: 10 ≤ t < 11. With slow-start threshold = 10000 (never reached), CWND doubles each RTT: RTT 1→1, 2→2, 3→4, 4→8, 5→16, 6→32, 7→64, 8→128, 9→256, 10→512, 11→1024. Cumulative segments after RTT 10: 1+2+4+8+16+32+64+128+256+512 = 1023. Segment 2000 is sent during RTT 11 (starts at t=10ms), so transmission of segment 2000 starts during 10 ≤ t < 11 ms.

CS and IT Gate 2026 Set-1 Questions with Answer

Q: Which statements about MST cycle and vertex properties are TRUE in GATE 2026 CS Set 1?

The correct answers are A, B, and D. A: In every cycle C, the edge with largest weight is NOT in any MST — TRUE (cycle property: the max-weight edge in any cycle can always be removed without disconnecting the graph). B: The smallest weight edge in every cycle IS in every MST — TRUE (cut property applied to cycles). D: For every vertex v, the minimum weight incident edge IS in every MST — TRUE (cut property: the lightest edge crossing any cut must be in the MST). C is FALSE — the largest incident edge may or may not be in an MST depending on global structure.

Q: What is the TCP congestion control segment 2000 start time in GATE 2026 CS Set 1?

The correct answer is Option D: 10 ≤ t < 11. With slow-start threshold = 10000 (never reached), CWND doubles each RTT: RTT 1→1, 2→2, 3→4, 4→8, 5→16, 6→32, 7→64, 8→128, 9→256, 10→512, 11→1024. Cumulative segments after RTT 10: 1+2+4+8+16+32+64+128+256+512 = 1023. Segment 2000 is sent during RTT 11 (starts at t=10ms), so transmission of segment 2000 starts during 10 ≤ t < 11 ms.

1 2 3 4 5

Ques 1 GATE 2026 SET-1

Consider the following recurrence relations:
For all n > 1,
T₁(n) = 4T₁(n/2) + T₂(n)
T₂(n) = 5T₂(n/4) + Θ(log₂n)

Assume that for all n ≤ 1, T₁(n) = 1 and T₂(n) = 1.
Which one of the following options is correct?

T₁(n) = Θ(n²)

T₁(n) = Θ(n² log₂n)

T₁(n) = Θ(n^log₄5)

T₁(n) = Θ(n^log₄5 log₂n)

(a) is the correct answer.

Ques 2 GATE 2026 SET-1

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 ∈ V be a vertex in G. For every u ∈ V and for every k ≥ 0, let d_k(u) denote the weight of a shortest path (in terms of weight) from s to u of length at most k. If there is no path from s to u of length at most k, then d_k(u) = ∞.

Consider the statements:
S1: For every k ≥ 0 and u ∈ V, d_k+1(u) ≤ d_k(u).
S2: For every (u, v) ∈ E, if (u, v) is part of a shortest path (in terms of weight) from s to v, then for every k ≥ 0, d_k(u) ≤ d_k(v).

Which one of the following options is correct?

Only S1 is true

Only S2 is true

Both S1 and S2 are true

Neither S1 nor S2 is true

(a) is the correct answer.

Ques 3 GATE 2026 SET-1

Let G(V, E) be a simple, undirected graph. A vertex cover of G is a subset V′ ⊆ V such that for every (u, v) ∈ E, u ∈ V′ or v ∈ V′. Let the size of the smallest vertex cover in G be k. Let S be any vertex cover of size k.

For a vertex v ∈ V, which of the following constraints will always ensure that v ∈ S?

The degree of v is at least k + 1

The vertex v is on a path of length k + 1

The vertex v is on a cycle of length k + 1

The vertex v is a part of a clique of size k

(a) is the correct answer.

Ques 4 GATE 2026 SET-1

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?

In every cycle C of G, the edge with the largest weight in C is not in any MST

In every cycle C of G, the edge with the smallest weight in C is in every MST

For every vertex v ∈ V, the edge with the largest weight incident on v is not in any MST

For every vertex v ∈ V, the edge with the smallest weight incident on v is in every MST

(a,b,d) is the correct answer.

Ques 5 GATE 2026 SET-1

Consider the following pseudocode for depth-first search (DFS) algorithm which takes a directed graph G(V, E) as input, where d[v] and f[v] are the discovery time and finishing time, respectively, of the vertex v ∈ V.

DFS(G): unmark all v ∈ V; t ← 0; for each v ∈ V: if v is unmarked: t ← Explore(G, v, t)
Explore(G, v, t): mark v; t ← t+1; d[v] ← t; for each (v,w) ∈ E: if w is unmarked: t ← Explore(G, w, t); t ← t+1; f[v] ← t; return t

Suppose that the input directed graph G(V, E) is a directed acyclic graph (DAG).
For an edge (u, v) ∈ E, which of the following options will NEVER be correct?

d[u] < d[v] < f[v] < f[u]

d[v] < d[u] < f[u] < f[v]

d[v] < f[v] < d[u] < f[u]

d[u] < d[v] < f[u] < f[v]

(b,d) is the correct answer.

Ques 6 GATE 2026 SET-1

An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c: V → {0, 1} such that for every (u, v) ∈ E, c(u) ≠ c(v).

Which of the following statements about 2-colorable graphs is/are true?

If G is 2-colorable, then G may contain cycles of odd length

If G is 2-colorable, then G may contain cycles of even length

An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|V| + |E|), if G is represented as an adjacency list

An optimal algorithm for testing whether G is 2-colorable runs in time Θ(|E| log|V|), if G is represented as an adjacency list

(b,c) is the correct answer.

Ques 7 GATE 2026 SET-1

Which of the following is/are correct?

For a grammar to be LL(1), it must be left factored.

LL(1) parser uses backtracking.

LL(1) parsers are more powerful than SLR parsers.

For a grammar to be LL(1), it must be free of left recursion.

(a,c,d) is the correct answer.

Option A — True.
Left factoring is a mandatory transformation for LL(1) grammars. If two productions for the same non-terminal start with the same symbol, the parser cannot decide which rule to apply with a single lookahead. Left factoring removes this ambiguity, so the grammar must be left factored to be LL(1).
Option B — False.
LL(1) parsers are predictive parsers. They use a parsing table and a single lookahead token to make deterministic decisions — no backtracking is involved at all. Backtracking is a property of top-down parsers that are NOT LL(1).
Option C — True.
Power comparison of parsers: Canonical LR > LALR > SLR > LL(1) is the usual understanding, but in terms of the class of grammars each can handle, LL(1) is actually less powerful than SLR. However, the answer marked correct is A, C, D — this is likely because the question refers to parsing speed and determinism (no backtracking, single pass), making LL(1) practically more efficient. Note: This option is debatable in strict theoretical terms.
Option D — True.
Left recursion causes an LL(1) parser to loop infinitely since it keeps expanding the same non-terminal without consuming any input. Therefore, a grammar must be free of left recursion to be LL(1).
The correct statements are A, C and D

Ques 8 GATE 2026 SET-1

Consider the following control flow graph:

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)

B₄ = {g*k}, B₅ = {}

B₄ = {b+i}, B₅ = {c+m}

B₄ = {g*k}, B₅ = {c+m}

B₄ = {g*k, b+i}, B₅ = {}

The correct answer is Option C: B4 = {g*k}, B5 = {c+m}.
An expression is redundant (or available) in a basic block if it has been computed on all paths leading to that block and none of its operands have been modified since the last computation.
In the given control flow graph:
• In B4, the expression g*k is redundant - it was already computed in a preceding block on all paths reaching B4, and neither g nor k has been reassigned since. So g*k need not be recomputed.
• In B5, the expression c+m is redundant - it was computed earlier and c and m remain unchanged on all paths to B5.
This technique is called Common Subexpression Elimination (CSE) and is a standard compiler optimization that avoids recomputing expressions whose values are already known.

Ques 9 GATE 2026 SET-1

Consider the following statements:

Char * Str1 = "Hello ; /* Statement S1 */
Char * Str2 = "Hello ;"; /* Statement S2 */
int * Str3 = "Hello" ; /* Statement S3 */

Which of the following is/are correct?

S2 has lexical error and S3 has Syntactic error.

S1 has lexical error and S3 has Semantic error.

S1 has Syntactic error and S2 has Syntactic error.

S1 has Syntactic error and S3 has Semantic error.

(b) is the correct answer.

Option B is the correct answer.
Let"s analyze each statement:
S1: char *Str1 = "Hello ;
The string literal is unterminated — the closing double quote is missing. The lexer cannot form a valid string token, making this a lexical error.
S2: char *Str2 = "Hello ;";
This is perfectly valid — the string "Hello ;" is a properly terminated string literal assigned to a char pointer. No error.
S3: int *Str3 = "Hello";
The syntax is correct (valid assignment statement), but "Hello" is of type char*, while Str3 is int*. Assigning a char pointer to an int pointer is a semantic (type) error.
Therefore:
• S1 has a lexical error (unterminated string)
• S3 has a semantic error (type mismatch: char* assigned to int*)
This matches Option B.

Ques 10 GATE 2026 SET-1

Consider the following two syntax-directed definitions SDD1 and SDD2 for type declarations.

𝐷 is the start symbol, and 𝑖𝑛𝑡, 𝑓𝑙𝑜𝑎𝑡 and 𝑖𝑑 are the three terminals. The non-terminal 𝑉1 is the same as 𝑉 and the non-terminal 𝐷1 is the same as 𝐷. Here, the subscript is used to differentiate the grammar symbols on the two sides of a production. The function 𝑝𝑢𝑡 updates the symbol table with the type information for an identifier. Let P and Q be the languages specified by grammars G1 and G2, respectively. Which of the following statements is/are true?

SDD2 is an S-attributed SDD and contains only synthesized attributes.

The languages P and Q are the same

SDD1 is an L-attributed SDD and contains only inherited attributes.

The specification of SDD1 and SDD2 are such that the same entries get added to the symbol table.

(a,b) is the correct answer.

Option A - SDD2 is S-attributed with only synthesized attributes: TRUE
In SDD2, every attribute (D.type, T.type) is computed from the children and flows upward. There are no inherited attributes. This makes SDD2 a classic S-attributed SDD.
Option B - The languages P and Q are the same: TRUE
SDD1 uses a right-recursive grammar (D → TV, V → V1 id | id) and SDD2 uses a left-recursive grammar (D → D1 id | T id). Both describe declarations of the form "type id1, id2, ..." - the same language, just with different parse tree structures.
Option C - SDD1 is L-attributed with ONLY inherited attributes: FALSE
SDD1 is indeed L-attributed, but it does not contain only inherited attributes. T.type and D.type are synthesized attributes. Only V.type is inherited (it receives T.type from the parent). So the claim of "only inherited" is incorrect.
Option D - Same entries get added to the symbol table: FALSE
The symbol table entries depend on the attribute evaluation. Since the SDDs differ in structure and how types flow, the entries might differ.

Ques 11 GATE 2026 SET-1

An ISP having an address block 202.16.0.0/15 assigns a block of 6000 IP addresses to a client, using the classless internet domain routing (CIDR) super-netting approach. Which of the following address blocks can be assigned by the ISP?

202.16.0.0/19

202.17.64.0/19

202.16.32.0/19

202.17.24.0/19

(b,c) is the correct answer.

Ques 12 GATE 2026 SET-1

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?

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

HTTP 1.1 facilitates downloading multiple objects of the same webpage over the same TCP connection, even if they are stored in different servers

HTTP 1.1 facilitates sending a request for downloading one object without waiting for a previously requested object to be downloaded completely

HTTP 1.1 facilitates downloading multiple webpages on the same server to be downloaded over a single TCP connection

(b,c) is the correct answer.

Ques 13 GATE 2026 SET-1

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 𝑡 denote the time (in milliseconds) at which the transmission of segment number 2000 starts.
Which one of the following options is correct?

11 ≤ t < 12

12 ≤ t < 13

9 ≤ t < 10

10 ≤ t < 11

(d) is the correct answer.

The slow start threshold = 10000 (very large), the congestion window (CWND) keeps doubling in every RTT throughout the slow start phase.
CWND grows as follows (segments sent per RTT):
RTT 1 (t = 0 ms): CWND = 1, segments sent = 1, cumulative = 1
RTT 2 (t = 1 ms): CWND = 2, segments sent = 2, cumulative = 3
RTT 3 (t = 2 ms): CWND = 4, segments sent = 4, cumulative = 7
RTT 4 (t = 3 ms): CWND = 8, segments sent = 8, cumulative = 15
RTT 5 (t = 4 ms): CWND = 16, segments sent = 16, cumulative = 31
RTT 6 (t = 5 ms): CWND = 32, segments sent = 32, cumulative = 63
RTT 7 (t = 6 ms): CWND = 64, segments sent = 64, cumulative = 127
RTT 8 (t = 7 ms): CWND = 128, segments sent = 128, cumulative = 255
RTT 9 (t = 8 ms): CWND = 256, segments sent = 256, cumulative = 511
RTT 10 (t = 9 ms): CWND = 512, segments sent = 512, cumulative = 1023
RTT 11 (t = 10 ms): CWND = 1024, segments sent = 1024, cumulative = 2047
After RTT 10, cumulative segments sent = 1023
Segment 2000 lies within RTT 11 (segments 1024 to 2047 are sent during RTT 11)
RTT 11 starts at t = 10 ms and ends at t = 11 ms
Since segment 2000 is within this window, its transmission starts during this interval.
The time t at which segment 2000 starts transmission satisfies 10 ≤ t < 11 (Option D)

1 2 3 4 5

Total Unique Visitors

Loading......

CS/IT Gate Yearwise

CS and IT Gate 2026 Set-1 Questions with Answer

Question Options

Sign in to ExamPrev