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

GATE CS 2021_Set2 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: 9 · Theory of Computation: 6 · Programming and Data Structures: 6 · Computer Organization and Architecture: 6 · Algorithms: 6 · Databases: 5 · Compiler Design: 5 · Quantitative Aptitude: 4 · Operating System: 4 · Digital Logic: 4 · Computer Networks: 4 · Verbal Aptitude: 2 · Spatial Aptitude: 2 · Analytical Aptitude: 2

Free sample questions from GATE CS 2021_Set2 Question Paper

Question 1 · Engineering Mathematics · 2021_Set2 MSQ

Consider the following sets, where

n \geq 2

S_{1}

: Set of all

n \times n

matrices with entries from the set

{a, b, c}

S_{2}

: Set of all functions from the set

{0, 1, 2, \dots, n^{2} - 1}

to the set

{0, 1, 2}

Which of the following choice(s) is/are correct?

A.
There does not exist a bijection from $S_{1}$ to $S_{2}$ .
B.
There exists a surjection from $S_{1}$ to $S_{2}$ .
C.
There exists a bijection from $S_{1}$ to $S_{2}$ .
D.
There does not exist an injection from $S_{1}$ to $S_{2}$ .

Correct Answer:

["B","C"]

Step-by-Step Solution

Key idea: This is a cardinality comparison question, recognizable by the need to compare the sizes of two differently described sets.

Step 1: Calculate the cardinality of $S_{1}$ . An $n \times n$ matrix has $n^{2}$ entries. Each entry can be independently chosen from the set ${a, b, c}$ , which has 3 elements. Thus, $∣ S_{1} ∣ = 3^{n^{2}}$ .

Step 2: Calculate the cardinality of $S_{2}$ . The set of all functions from a domain of size $k$ to a codomain of size $m$ is $m^{k}$ . Here, the domain is ${0, 1, \dots, n^{2} - 1}$ , which has size $n^{2}$ . The codomain is ${0, 1, 2}$ , which has size 3. Thus, $∣ S_{2} ∣ = 3^{n^{2}}$ .

Step 3: Compare the cardinalities. Since $∣ S_{1} ∣ = ∣ S_{2} ∣ = 3^{n^{2}}$ and both are finite sets, there exists a bijection between them.

Step 4: Evaluate the options. Since a bijection exists, Option C is true. A bijection is also a surjection, so Option B is true. Options A and D are false because they claim a bijection or injection does not exist.

Answer: Options B and C.

Question 2 · Engineering Mathematics · 2021_Set2 MSQ

Choose the correct choice(s) regarding the following propositional logic assertion

S

S : ((P \land Q) \to R) \to ((P \land Q) \to (Q \to R))

A.
$S$ is neither a tautology nor a contradiction.
B.
$S$ is a tautology.
C.
$S$ is a contradiction.
D.
The antecedent of $S$ is logically equivalent to the consequent of $S$ .

Correct Answer:

["B","D"]

Step-by-Step Solution

Key idea: This is a logical equivalence and tautology verification question, recognizable because it asks you to classify a complex implication $S$ and compare its antecedent to its consequent. The key method is to simplify both sides algebraically using the definition of implication and De Morgan's laws.

Step 1: Identify the antecedent and consequent of $S$ .

Let $X = (P \land Q) \to R$ (the antecedent).

Let $Y = (P \land Q) \to (Q \to R)$ (the consequent).

Step 2: Simplify the antecedent $X$ .

Using the definition $A \to B \equiv \neg A \lor B$ :

$X \equiv \neg (P \land Q) \lor R$

Applying De Morgan's law $\neg (A \land B) \equiv \neg A \lor \neg B$ :

$X \equiv \neg P \lor \neg Q \lor R$

Step 3: Simplify the consequent $Y$ .

First, simplify the inner implication $Q \to R$ :

$Q \to R \equiv \neg Q \lor R$

Now substitute back into $Y$ :

$Y \equiv (P \land Q) \to (\neg Q \lor R)$

Apply the definition of implication:

$Y \equiv \neg (P \land Q) \lor (\neg Q \lor R)$

Apply De Morgan's law:

$Y \equiv (\neg P \lor \neg Q) \lor (\neg Q \lor R)$

By associativity and idempotence ( $\neg Q \lor \neg Q \equiv \neg Q$ ):

$Y \equiv \neg P \lor \neg Q \lor R$

Step 4: Compare $X$ and $Y$ .

Both simplify to $\neg P \lor \neg Q \lor R$ , so $X \equiv Y$ .

Therefore, $S$ is of the form $X \to X$ , which is always true.

This means $S$ is a tautology, and the antecedent is logically equivalent to the consequent.

Answer: B, D

Question 3 · Engineering Mathematics · 2021_Set2 NAT

For a given biased coin, the probability that the outcome of a toss is a head is 0.4. This coin is tossed 1,000 times. Let $X$ denote the random variable whose value is the number of times that head appeared in these 1,000 tosses. The standard deviation of $X$ (rounded to 2 decimal places) is __________.

Correct Answer:

15.49

Step-by-Step Solution

Insight: The number of heads in $n$ independent tosses of a biased coin follows a Binomial distribution $B (n, p)$ .

Exam route: Identify $n = 1000$ , $p = 0.4$ , $q = 0.6$ . Variance $= n pq = 1000 \times 0.4 \times 0.6 = 240$ . Standard deviation $= 240 \approx 15.49$ .

Learning route:

Recognize the distribution: $X \sim Binomial (1000, 0.4)$ .
Recall the variance formula for a Binomial random variable: $Var (X) = n p (1 - p)$ .
Calculate the variance: $Var (X) = 1000 \times 0.4 \times 0.6 = 240$ .
Standard deviation is the square root of variance: $σ_{X} = 240 \approx 15.4919$ .
Round to two decimal places as requested: $15.49$ .

Question 4 · Theory of Computation · 2021_Set2 MCQ

Let $L \subseteq {0, 1}^{*}$ be an arbitrary regular language accepted by a minimal DFA with $k$ states. Which one of the following languages must necessarily be accepted by a minimal DFA with $k$ states?

A.
$L - {01}$
B.
$L \cup {01}$
C.
${0, 1}^{*} - L$
D.
$L \cdot L$

Correct Answer:

Step-by-Step Solution

Key idea: This is a state complexity and language equivalence question, recognizable because it asks about the minimal DFA state count after applying language operations.

Step 1: Analyze the given condition. We have a minimal DFA for $L$ with exactly $k$ states.

Step 2: Evaluate option 3 (Complementation). The complement of $L$ , denoted $\overline{L} = {0, 1}^{*} - L$ , is accepted by the exact same DFA structure, but with final and non-final states swapped.

Step 3: Check minimality preservation. Two states are distinguishable in $L$ if and only if they are distinguishable in $\overline{L}$ . Therefore, the swapped DFA is already minimal and has exactly $k$ states.

Step 4: Evaluate other options. Adding or removing a finite string (Options 1 and 2) can increase the state count (e.g., if $L = {0, 1}^{*}$ has $k = 1$ , $L - {01}$ requires more states to explicitly reject "01"). Concatenation (Option 4) can increase state complexity up to $k^{2} - k + 1$ .

Answer: ${0, 1}^{*} - L$

Question 5 · Theory of Computation · 2021_Set2 MSQ

Let $L_{1}$ be a regular language and $L_{2}$ be a context-free language. Which of the following languages is/are context-free?

A.
$L_{1} \cap \overline{L_{2}}$
B.
$\overline{\overline{L_{1}} \cup \overline{L_{2}}}$
C.
$L_{1} \cup (L_{2} \cup \overline{L_{2}})$
D.
$(L_{1} \cap L_{2}) \cup (\overline{L_{1}} \cap L_{2})$

Correct Answer:

["B","C","D"]

Step-by-Step Solution

Key idea: This question tests the closure properties of Context-Free Languages (CFLs) when combined with Regular languages using boolean operations. We must determine which expressions are guaranteed to be CFL.

Given: $L_{1}$ is Regular, $L_{2}$ is CFL.

Step 1: Evaluate Option A: $L_{1} \cap \overline{L_{2}}$ .

CFLs are NOT closed under complementation, so $\overline{L_{2}}$ is not necessarily a CFL. The intersection of a Regular language and a non-CFL can be non-CFL.

Counterexample: Let $L_{1} = Σ^{*}$ (Regular) and $L_{2}$ be a CFL whose complement is not CFL. Then $L_{1} \cap \overline{L_{2}} = \overline{L_{2}}$ , which is not CFL. Thus, Option A is NOT always CFL.

Step 2: Evaluate Option B: $\overline{\overline{L_{1}} \cup \overline{L_{2}}}$ .

By De Morgan's Laws, this simplifies to $L_{1} \cap L_{2}$ .

A fundamental theorem states that the intersection of a Regular language and a CFL is always a CFL. Thus, Option B is ALWAYS context-free.

Step 3: Evaluate Option C: $L_{1} \cup (L_{2} \cup \overline{L_{2}})$ .

For any language $L_{2}$ , $L_{2} \cup \overline{L_{2}} = Σ^{*}$ (the set of all strings over the alphabet).

$Σ^{*}$ is a Regular language (and therefore a CFL).

The union of $L_{1}$ (Regular) and $Σ^{*}$ is $Σ^{*}$ , which is Regular, and thus always a CFL. Thus, Option C is ALWAYS context-free.

Step 4: Evaluate Option D: $(L_{1} \cap L_{2}) \cup (\overline{L_{1}} \cap L_{2})$ .

By the distributive law of sets, we can factor out $L_{2}$ :

$(L_{1} \cup \overline{L_{1}}) \cap L_{2} = Σ^{*} \cap L_{2} = L_{2}$ .

Since $L_{2}$ is given as a CFL, the result is exactly $L_{2}$ , which is always a CFL. Thus, Option D is ALWAYS context-free.

Answer: Options B, C, and D are always context-free.

Question 6 · Theory of Computation · 2021_Set2 NAT

Consider the following deterministic finite automaton (DFA).

The number of strings of length 8 accepted by the above automaton is __________.

Correct Answer:

204

Step-by-Step Solution

Key idea: This is a string counting problem on a DFA, recognizable by the request for the number of accepted strings of a specific length. We must analyze the state transitions to determine which strings reach the final state.

Step 1: Analyze the DFA structure from the diagram.

Let the states be $q_{0}$ (start), $q_{1}, q_{2}, q_{3}, q_{4}$ (top row), and $q_{5}$ (final, bottom right? No, let's trace carefully).

Looking at the SVG:

Start arrow points to left-most state ( $q_{0}$ ).
$q_{0} 0 q_{1}$ (top middle-left), $q_{0} 1 q_{2}$ (bottom middle-left).
$q_{1} 0 q_{3}$ (top middle-right), $q_{1} 1 q_{4}$ (bottom middle-right).
$q_{2} 1 q_{3}$ , $q_{2} 0 q_{4}$ .
$q_{3} 0, 1 q_{5}$ (final state, double circle).
$q_{4} 0, 1 q_{5}$ .
$q_{5} 0, 1 q_{5}$ (self-loop).

Wait, let's re-read the SVG coordinates and labels carefully.

States:

Start -> Circle at (110, 136). Let's call this S.
Circle at (210, 55). Let's call this A.
Circle at (210, 217). Let's call this B.
Circle at (350, 55). Let's call this C.
Circle at (350, 217). Let's call this D.
Circle at (480, 136) with inner circle (Final). Let's call this F.

Transitions:

S -> A on '0'
S -> B on '1'
A -> C on '0'
A -> D on '1' (Arrow from 210,55 to 350,217 labeled '1')
B -> D on '0' (Arrow from 210,217 to 350,55? No, label is near the cross. Let's trace lines.)
Line from B(210,217) goes to C(350,55)? Label '0' is at (272, 164). Yes.
Line from B(210,217) goes to D(350,217)? Label '1' is at (275, 237). Yes.
So:
$S 0 A, S 1 B$
$A 0 C, A 1 D$
$B 0 C$ (Wait, line from B to C? The line from 210,217 to 350,55 has label '0' at 272,164. Correct.)
$B 1 D$ (Line from 210,217 to 350,217 has label '1' at 275,237. Correct.)
From C(350,55): Arrow to F(480,136) labeled '0,1'.
From D(350,217): Arrow to F(480,136) labeled '0,1'.
From F(480,136): Self loop labeled '0,1'.

Step 2: Determine the condition for acceptance.

To reach the final state F, a string must pass through either C or D.

Paths to C or D have length exactly 2.

Any string of length $\geq 2$ will reach F at step 2 and stay there due to the self-loop.

Strings of length 0 or 1 cannot reach F.

Therefore, the DFA accepts all strings of length $\geq 2$ .

Step 3: Count strings of length 8.

Total binary strings of length 8 is $2^{8} = 256$ .

Since all strings of length $\geq 2$ are accepted, and $8 \geq 2$ , all $2^{8}$ strings are accepted.

Wait, let me double check the "trap". Is it possible that some paths don't go to F?

C -> F on 0,1.

D -> F on 0,1.

Yes, once you hit layer 2 (C or D), you go to F and stay there.

Are there any dead states? No, all transitions are defined and lead towards F or are part of the path to F.

So $L = {w ∣ ∣ w ∣ \geq 2}$ .

Number of strings of length 8 is $2^{8} = 256$ .

Let me re-read the diagram. Is it possible that C and D are not "layer 2"?

S->A (len 1)

S->B (len 1)

A->C (len 2)

A->D (len 2)

B->C (len 2)

B->D (len 2)

Yes, all paths of length 2 end in C or D.

From C and D, all inputs go to F.

So any string of length 2 ends in C or D. The next character (3rd char) moves it to F.

So strings of length 3 or more are definitely in F.

What about strings of length exactly 2? They end in C or D. C and D are NOT final.

So strings of length 2 are REJECTED.

Strings of length 1 end in A or B. Rejected.

Strings of length 0 end in S. Rejected.

So the language is $L = {w ∣ ∣ w ∣ \geq 3}$ .

Step 4: Recalculate.

We need the number of strings of length 8.

Since $8 \geq 3$ , all strings of length 8 are accepted.

Total strings = $2^{8} = 256$ .

Let's check if there is any other interpretation.

Maybe the loop on F is not a self-loop?

"path d='M493 123 C538 78 548 166 498 145'" -> This is a loop back to F.

Is it possible that some transitions from S, A, B go elsewhere?

S has only 0,1 outgoing.

A has only 0,1 outgoing.

B has only 0,1 outgoing.

So, any string of length 2 lands in {C, D}.

Any string of length 3 lands in {F}.

Any string of length > 3 stays in {F}.

Thus, $L = {w \in {0, 1}^{*} ∣ ∣ w ∣ \geq 3}$ .

For length 8, all $2^{8}$ strings are in L.

Answer: 256.

Let me check if I missed any "dead" transitions.

The diagram shows all transitions accounted for.

S: 0->A, 1->B.

A: 0->C, 1->D.

B: 0->C, 1->D.

C: 0,1->F.

D: 0,1->F.

F: 0,1->F.

Yes, it is a "width-2, depth-2" tree that collapses into a sink accept state.

Depth 0: S (Reject)

Depth 1: A, B (Reject)

Depth 2: C, D (Reject)

Depth 3+: F (Accept)

So min length is 3.

Length 8 is accepted.

Count = $2^{8} = 256$ .

Question 7 · Programming and Data Structures · 2021_Set2 MCQ

Let $H$ be a binary min-heap consisting of $n$ elements implemented as an array. What is the worst case time complexity of an optimal algorithm to find the maximum element in $H$ ?

A.
$Θ (1)$
B.
$Θ (lo g n)$
C.
$Θ (n)$
D.
$Θ (n lo g n)$

Question 8 · Programming and Data Structures · 2021_Set2 MCQ

Consider the following ANSI C program.

#include <stdio.h>
int main(){
    int arr[4][5];
    int i, j;
    for (i=0; i<4; i++){
        for (j=0; j<5; j++){
            arr[i][j] = 10*i + j;
        }
    }
    printf("%d", *(arr[1] + 9));
    return 0;
}

What is the output of the above program?

A.
14
B.
20
C.
24
D.
30

Correct Answer:

Step-by-Step Solution

Insight: This is a multidimensional array pointer arithmetic question, recognizable by the expression *(arr[1] + 9).

Exam route: arr[1] is an int pointing to arr[1][0]. Adding 9 moves the pointer 9 integers forward. Since each row has 5 elements, this lands on arr[1 + 1][4] = arr[2][4]. Value is 102 + 4 = 24.

Learning route:

arr is a 2D array of size 4x5, stored in contiguous row-major memory.
arr[1] is the name of the second row. In an expression, it decays to a pointer to its first element, i.e., &arr[1][0]. Its type is int *.
The expression arr[1] + 9 performs pointer arithmetic. It adds 9 to the int * pointer.
Since each row has 5 elements, moving 5 steps forward reaches the start of the next row: arr[1] + 5 is equivalent to &arr[2][0].
Moving 4 more steps reaches &arr[2][4]. Thus, arr[1] + 9 is equivalent to &arr[2][4].
Dereferencing this with * gives the value of arr[2][4].
The initialization rule is arr[i][j] = 10i + j. For i=2, j=4, the value is 102 + 4 = 24.

Question 9 · Programming and Data Structures · 2021_Set2 NAT

Consider a complete binary tree with 7 nodes. Let

A

denote the set of first 3 elements obtained by performing Breadth-First Search (BFS) starting from the root. Let

B

denote the set of first 3 elements obtained by performing Depth-First Search (DFS) starting from the root.
The value of

∣ A - B ∣

is __________.

Correct Answer:

1.00

Step-by-Step Solution

Insight: This is a tree traversal set-operation question, recognizable because it asks for the size of the set difference between the first few elements of BFS and DFS.

Exam route: For a complete 7-node tree, BFS starts 1, 2, 3. DFS (preorder) starts 1, 2, 4. Set $A = {1, 2, 3}$ , Set $B = {1, 2, 4}$ . $A - B = {3}$ . Size is 1.

Learning route:

Step 1: Define the tree structure. A complete binary tree with 7 nodes has levels 0, 1, and 2 fully filled.

Level 0: 1

Level 1: 2, 3

Level 2: 4, 5, 6, 7

Step 2: Determine BFS order. BFS visits level by level, left to right.

Sequence: 1, 2, 3, 4, 5, 6, 7.

First 3 elements: $A = {1, 2, 3}$ .

Step 3: Determine DFS order. Standard DFS is preorder (Node, Left, Right).

Sequence: 1, 2, 4, 5, 3, 6, 7.

First 3 elements: $B = {1, 2, 4}$ .

Step 4: Compute set difference $A - B$ .

$A - B$ contains elements in $A$ but not in $B$ .

${1, 2, 3} - {1, 2, 4} = {3}$ .

Step 5: Find the cardinality. $∣ A - B ∣ = ∣ {3} ∣ = 1$ .

Wrong path: Confusing set difference $A - B$ with symmetric difference $(A \cup B) - (A \cap B)$ , which would yield ${3, 4}$ and size 2. Or assuming DFS visits right child first (yielding $B = {1, 3, 7}$ , $A - B = {2}$ , size still 1, but the reasoning is flawed).

Question 10 · Computer Organization and Architecture · 2021_Set2 MCQ

The format of the single-precision floating-point representation of a real number as per the IEEE 754 standard is as follows:

Which one of the following choices is correct with respect to the smallest normalized positive number represented using the standard?

A.
exponent = 00000000 and mantissa = 00000000000000000000000
B.
exponent = 00000000 and mantissa = 00000000000000000000001
C.
exponent = 00000001 and mantissa = 00000000000000000000000
D.
exponent = 00000001 and mantissa = 00000000000000000000001

Correct Answer:

Step-by-Step Solution

Key idea: Identify the conditions for a "normalized" number in IEEE 754 single-precision format and find the minimum possible value.

Step 1: Recall the IEEE 754 single-precision layout.

1 bit for sign, 8 bits for exponent, 23 bits for mantissa (fraction).

Step 2: Understand the "normalized" condition.

A number is normalized if its exponent field is neither all 0s (00000000, which denotes zero or subnormal numbers) nor all 1s (11111111, which denotes infinity or NaN).

Step 3: Find the smallest normalized positive number.

Positive: Sign bit must be 0.
Smallest exponent: The smallest valid exponent field for a normalized number is 00000001 (biased exponent 1, actual exponent 1 - 127 = -126).
Smallest mantissa: To minimize the value, the fraction bits should be as small as possible, which is all 0s (000000000000 is 23 zeros). This gives a significand of exactly 1.0.

Step 4: Match with options.

Exponent = 00000001 and mantissa = 00000000000000000000000.

This corresponds to Option C.

Question 11 · Computer Organization and Architecture · 2021_Set2 NAT

Consider a set-associative cache of size 2KB (1KB = $2^{10}$ bytes) with cache block size of 64 bytes. Assume that the cache is byte-addressable and a 32-bit address is used for accessing the cache. If the width of the tag field is 22 bits, the associativity of the cache is __________.

Correct Answer:

Step-by-Step Solution

Key idea: this is a set-associative cache parameter calculation question, recognisable because it gives the total cache size, block size, address size, and tag field width, and asks to find the associativity.

Step 1: Identify the given parameters. Cache size = 2 KB = $2^{11}$ bytes. Block size = 64 bytes = $2^{6}$ bytes. Address size = 32 bits. Tag bits = 22.

Step 2: Calculate the number of lines in the cache. Number of lines = Cache size / Block size = $2^{11} / 2^{6} = 2^{5} = 32$ lines.

Step 3: Set up the address decomposition equation. Let $K$ be the associativity (number of lines per set).

Number of sets = $32/ K$ .

Set index bits = $lo g_{2} (32/ K) = 5 - lo g_{2} K$ .

Block offset bits = $lo g_{2} (64) = 6$ .

Step 4: Use the tag bits formula. Tag bits = Address size - Set index bits - Offset bits.

$22 = 32 - (5 - lo g_{2} K) - 6$

$22 = 21 + lo g_{2} K$

$lo g_{2} K = 1 ⟹ K = 2$ .

Answer: 2

Question 12 · Computer Organization and Architecture · 2021_Set2 NAT

Consider a computer system with DMA support. The DMA module is transferring one 8-bit character in one CPU cycle from a device to memory through cycle stealing at regular intervals. Consider a 2 MHz processor. If 0.5% processor cycles are used for DMA, the data transfer rate of the device is __________ bits per second.

Correct Answer:

80000

Step-by-Step Solution

Key idea: This is a DMA throughput calculation question, recognisable because it gives processor frequency, cycle fraction, and transfer size.

Step 1: Calculate the total number of CPU cycles per second. The processor is 2 MHz, which is $2 \times 1 0^{6}$ cycles/second.

Step 2: Calculate the number of cycles used for DMA per second. This is 0.5% of the total cycles: $0.005 \times 2 \times 1 0^{6} = 10, 000$ cycles/second.

Step 3: Relate cycles to data transferred. The problem states that 1 CPU cycle transfers one 8-bit character.

Step 4: Calculate the total data transfer rate in bits per second. $10, 000 cycles/sec \times 8 bits/cycle = 80, 000$ bits/second.

Answer: 80000

Question 13 · Algorithms · 2021_Set2 MCQ

Let

G

be a connected undirected weighted graph. Consider the following two statements.

S_{1} :

There exists a minimum weight edge in

G

which is present in every minimum spanning tree of

G

S_{2} :

If every edge in

G

has distinct weight, then

G

has a unique minimum spanning tree.

Which one of the following options 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.

Question 14 · Algorithms · 2021_Set2 MCQ

What is the worst-case number of arithmetic operations performed by recursive binary search on a sorted array of size $n$ ?

A.
$Θ (n)$
B.
$Θ (lo g_{2} (n))$
C.
$Θ (n^{2})$
D.
$Θ (n)$

Correct Answer:

Step-by-Step Solution

Key idea: Recursive binary search divides the problem size by 2 in each step. The depth of the recursion tree determines the number of operations.

Step 1: Analyze the algorithm.

Binary search on a sorted array of size $n$ .
In each recursive call, we calculate the middle index and compare the target with the middle element.
Based on the comparison, we recurse on either the left half or the right half.
The size of the problem reduces from $n$ to $n /2$ .

Step 2: Formulate the recurrence.

Let $T (n)$ be the number of arithmetic operations/comparisons.
$T (n) = T (n /2) + O (1)$ .
The $O (1)$ term accounts for calculating mid and the comparison.

Step 3: Solve the recurrence.

This is a standard recurrence solved by the Master Theorem or iteration.
Depth of recursion = $lo g_{2} n$ .
At each level, constant work is done.
Total operations $\propto lo g_{2} n$ .

Step 4: Determine the asymptotic bound.

Worst-case occurs when the element is not present or is at a leaf.
Number of steps = $⌊ lo g_{2} n ⌋ + 1$ .
This is $Θ (lo g_{2} n)$ .

Step 5: Match with options.

Option B is $Θ (lo g_{2} n)$ .

Answer: B

Question 15 · Algorithms · 2021_Set2 MCQ

Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties:

1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.

Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

A.
21
B.
23
C.
25
D.
30

Question 16 · Databases · 2021_Set2 MCQ

Consider the following statements S1 and S2 about the relational data model:

S1: A relation scheme can have at most one foreign key.
S2: A foreign key in a relation scheme R cannot be used to refer to tuples of R.

Which one of the following choices is correct?

A.
Both S1 and S2 are true.
B.
S1 is true and S2 is false.
C.
S1 is false and S2 is true.
D.
Both S1 and S2 are false.

Question 17 · Databases · 2021_Set2 NAT

A data file consisting of 1,50,000 student-records is stored on a hard disk with block size of 4096 bytes. The data file is sorted on the primary key RollNo. The size of a record pointer for this disk is 7 bytes. Each student-record has a candidate key attribute called ANum of size 12 bytes. Suppose an index file with records consisting of two fields, ANum value and the record pointer to the corresponding student record, is built and stored on the same disk. Assume that the records of data file and index file are not split across disk blocks. The number of blocks in the index file is __________.

Question 18 · Databases · 2021_Set2 MCQ

The relation scheme given below is used to store information about the employees of a company, where empId is the key and deptId indicates the department to which the employee is assigned. Each employee is assigned to exactly one department.

emp(empId, name, gender, salary, deptId)

Consider the following SQL query:

select deptId, count(*)
from emp
where gender = "female" and salary > (select avg(salary) from emp)
group by deptId;

The above query gives, for each department in the company, the number of female employees whose salary is greater than the average salary of

A.
employees in the department.
B.
employees in the company.
C.
female employees in the department.
D.
female employees in the company.

Question 19 · Compiler Design · 2021_Set2 MCQ

Consider the following ANSI C program:

int main() {
Integer x;
return 0;
}

Which one of the following phases in a seven-phase C compiler will throw an error?

A.
Lexical analyzer
B.
Syntax analyzer
C.
Semantic analyzer
D.
Machine dependent optimizer

Correct Answer:

Step-by-Step Solution

Key idea: This is an Error Classification question. We must trace the given code through the compiler phases to see which one first flags an error.

Step 1: Analyze the code snippet.

The code is Integer x;. In ANSI C, Integer is not a reserved keyword (the correct keyword is int).

Step 2: Lexical Analysis Phase.

The lexical analyzer (scanner) reads the characters and groups them into tokens based on regular expressions. Since Integer is not a reserved keyword, the scanner treats it as a standard identifier (id).

The token stream produced is: <id, "Integer">, <id, "x">, <;>.

No lexical error is thrown because Integer is a perfectly valid identifier.

Step 3: Syntax Analysis Phase.

The syntax analyzer (parser) receives the token stream and tries to build a parse tree using the context-free grammar of C.

A variable declaration in C requires a type specifier followed by an identifier and a semicolon (e.g., type_specifier id ;).

The parser sees <id> <id> ;. This sequence does not match any valid production rule for a declaration or statement in the C grammar.

Therefore, the parser fails to parse the tokens and throws a Syntax Error.

Step 4: Semantic Analysis Phase.

The semantic analyzer never receives this code because the compilation halts (or at least flags the primary error) at the syntax analysis phase. Even if it did, it would look for type compatibility, but the structural grammar violation is caught first.

Answer: Syntax analyzer

Question 20 · Compiler Design · 2021_Set2 MSQ

In the context of compilers, which of the following is/are NOT an intermediate representation of the source program?

A.
Three address code
B.
Abstract Syntax Tree (AST)
C.
Control Flow Graph (CFG)
D.
Symbol table

Question 21 · Compiler Design · 2021_Set2 MCQ

Consider the following ANSI C code segment:

z = x + 3 + y->f1 + y->f2;
for (i = 0; i < 200; i = i + 2){
    if (z > i) {
        p = p + x + 3;
        q = q + y->f1;
    } else {
        p = p + y->f2;
        q = q + x + 3;
    }
}

Assume that the variable y points to a struct (allocated on the heap) containing two fields f1 and f2, and the local variables x, y, z, p, q, and i are allotted registers. Common sub-expression elimination (CSE) optimization is applied on the code. The number of addition and dereference operations (of the form y->f1 or y->f2) in the optimized code, respectively, are:

A.
403 and 102
B.
203 and 2
C.
303 and 102
D.
303 and 2

Question 22 · Quantitative Aptitude · 2021_Set2 MCQ

If $θ$ is the angle, in degrees, between the longest diagonal of the cube and any one of the edges of the cube, then, $cos θ =$

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

Correct Answer:

Step-by-Step Solution

Insight: The angle between a cube's body diagonal and any of its edges is a constant, independent of the cube's size.

Exam route: Recall the standard formula for a cube: $cos θ = \frac{1}{3}$ .

Learning route:

Let the cube have edge length $a$ .
The body diagonal stretches from one corner to the opposite corner through the interior. Its length is $d = a^{2} + a^{2} + a^{2} = a 3$ .
The angle $θ$ between the body diagonal and an edge forms a right triangle where the edge is the adjacent side (length $a$ ) and the body diagonal is the hypotenuse (length $a 3$ ).
Therefore, $cos θ = \frac{adjacent}{hypotenuse} = \frac{a}{a 3} = \frac{1}{3}$ .

Wrong path: Confusing the body diagonal with a face diagonal. A face diagonal has length $a 2$ , which would give $cos θ = \frac{1}{2}$ (Option C). This is incorrect because the question specifies the "longest diagonal".

Question 23 · Quantitative Aptitude · 2021_Set2 MCQ

If $(x - \frac{1}{2})^{2} - (x - \frac{3}{2})^{2} = x + 2$ , then the value of $x$ is:

A.
2
B.
4
C.
6
D.
8

Correct Answer:

Step-by-Step Solution

Insight: Recognize the difference of squares pattern $a^{2} - b^{2} = (a - b) (a + b)$ to avoid messy expansion.

Exam route: Let $a = x - 1/2$ and $b = x - 3/2$ . Then $a - b = 1$ and $a + b = 2 x - 2$ . The equation becomes $1 \cdot (2 x - 2) = x + 2 ⟹ 2 x - 2 = x + 2 ⟹ x = 4$ .

Learning route:

Expand both squares: $(x^{2} - x + 1/4) - (x^{2} - 3 x + 9/4) = x + 2$ .

Simplify the left side: $x^{2} - x + 1/4 - x^{2} + 3 x - 9/4 = 2 x - 8/4 = 2 x - 2$ .

Equate to the right side: $2 x - 2 = x + 2$ .

Subtract $x$ from both sides and add 2 to both sides: $x = 4$ .

Question 24 · Quantitative Aptitude · 2021_Set2 MCQ

The number of students in three classes is in the ratio 3:13:6. If 18 students are added to each class, the ratio changes to 15:35:21.

The total number of students in all the three classes in the beginning was:

A.
22
B.
66
C.
88
D.
110

Correct Answer:

Step-by-Step Solution

Insight: Adding the same constant to every term of a ratio preserves the absolute difference between terms. Use that invariant to set up a quick equation.

Exam route: Initial ratio $3 : 13 : 6 ⟹$ parts sum $= 22$ . After $+ 18$ , ratio $15 : 35 : 21$ . Using first two terms: $\frac{3 x + 18}{13 x + 18} = \frac{15}{35} = \frac{3}{7} ⟹ 21 x + 126 = 39 x + 54 ⟹ x = 4$ . Total $= 22 x = 88$ .

Learning route:

Step 1: Let initial students be $3 x, 13 x, 6 x$ . Total $= 22 x$ .

Step 2: After adding 18 to each class: $3 x + 18, 13 x + 18, 6 x + 18$ .

Step 3: The new ratio of the first two classes is $\frac{3 x + 18}{13 x + 18} = \frac{15}{35} = \frac{3}{7}$ .

Step 4: Cross-multiply: $7 (3 x + 18) = 3 (13 x + 18) ⟹ 21 x + 126 = 39 x + 54$ .

Step 5: Solve: $18 x = 72 ⟹ x = 4$ .

Step 6: Initial total $= 22 x = 22 \times 4 = 88$ .

Trap warning: Option A ( $22$ ) is just the sum of the ratio parts, forgetting the multiplier. Option B ( $66$ ) and D ( $110$ ) come from mis-solving the equation or mis-scaling.

Verification: Initial $= 12, 52, 24$ . After $+ 18$ : $30, 70, 42$ . Ratio $= 30 : 70 : 42 = 15 : 35 : 21$ . Matches.

Question 25 · Operating System · 2021_Set2 MSQ

Which of the following statement(s) is/are correct in the context of CPU scheduling?

A.
Turnaround time includes waiting time.
B.
The goal is to only maximize CPU utilization and minimize throughput.
C.
Round-robin policy can be used even when the CPU time required by each of the processes is not known apriori.
D.
Implementing preemptive scheduling needs hardware support.

Question 26 · Operating System · 2021_Set2 MSQ

Consider the following multi-threaded code segment (in a mix of C and pseudo-code), invoked by two processes P1 and P2, and each of the processes spawns two threads T1 and T2:

int x = 0;   // global
Lock L1;     // global
main() {
  create a thread to execute foo(); // Thread T1
  create a thread to execute foo(); // Thread T2
  wait for the two threads to finish execution;
  print (x);}

foo() {
  int y = 0;
  Acquire L1;
  x = x + 1;
  y = y + 1;
  Release L1;
  print (y);}

Which of the following statement(s) is/are correct?

A.
Both P1 and P2 will print the value of x as 2.
B.
At least one of P1 and P2 will print the value of x as 4.
C.
At least one of the threads will print the value of y as 2.
D.
Both T1 and T2, in both the processes, will print the value of y as 1.

Question 27 · Operating System · 2021_Set2 MSQ

Consider a computer system with multiple shared resource types, with one instance per resource type. Each instance can be owned by only one process at a time. Owning and freeing of resources are done by holding a global lock (L). The following scheme is used to own a resource instance :

function OWNRESOURCE(Resource R)
    Acquire lock L // a global lock
    if R is available then
        Acquire R
        Release lock L
    else
        if R is owned by another process P then
            Terminate P, after releasing all resources owned by P
            Acquire R
            Restart P
            Release lock L
        end if
    end if
end function

Which of the following choice(s) about the above scheme is/are correct?

A.
The scheme ensures that deadlocks will not occur.
B.
The scheme may lead to live-lock.
C.
The scheme may lead to starvation.
D.
The scheme violates the mutual exclusion property.

Question 28 · Digital Logic · 2021_Set2 MCQ

Which one of the following circuits implements the Boolean function given below?

f (x, y, z) = m_{0} + m_{1} + m_{3} + m_{4} + m_{5} + m_{6}, where m_{i} is the i^{t h} minterm.

Correct Answer:

Step-by-Step Solution

Insight: Use the implementation table method to map an n-variable function onto a 2^(n-1)-to-1 multiplexer by treating the MSB as a variable input.

Exam route: Create a 2-row table with the lower-order variables (y, z) as columns. Compare the minterm values for x=0 and x=1 in each column to determine the MUX data inputs (0, 1, x, or x').

Learning route:

The function is $f (x, y, z) = \sum m (0, 1, 3, 4, 5, 6)$ .
We are using a 4-to-1 MUX, which has 2 select lines. We assign the lower-order variables to the select lines: $s_{1} = y$ , $s_{0} = z$ . The MSB $x$ will determine the data inputs.
Construct the implementation table:

Column 00 (y=0, z=0): minterms $m_{0}$ (x=0) and $m_{4}$ (x=1). Both are in the function list (1 and 1). Rule: (1, 1) $\to$ Input = 1.
Column 01 (y=0, z=1): minterms $m_{1}$ (x=0) and $m_{5}$ (x=1). Both are in the list (1 and 1). Rule: (1, 1) $\to$ Input = 1.
Column 10 (y=1, z=0): minterms $m_{2}$ (x=0) and $m_{6}$ (x=1). $m_{2}$ is absent (0), $m_{6}$ is present (1). Rule: (0, 1) $\to$ Input = MSB = $x$ .
Column 11 (y=1, z=1): minterms $m_{3}$ (x=0) and $m_{7}$ (x=1). $m_{3}$ is present (1), $m_{7}$ is absent (0). Rule: (1, 0) $\to$ Input = $\overline{MSB} = x^{'}$ .

The required data inputs are $I_{0} = 1$ , $I_{1} = 1$ , $I_{2} = x$ , $I_{3} = x^{'}$ .
Matching with the options, the first circuit (Option A) shows exactly these inputs with $s_{1} = y$ and $s_{0} = z$ .

Question 29 · Digital Logic · 2021_Set2 NAT

If $x$ and $y$ are two decimal digits and $(0.1101)_{2} = (0.8 x y 5)_{10}$ , the decimal value of $x + y$ is __________.

Correct Answer:

3.00

Step-by-Step Solution

Insight: Convert the fully known binary fraction to Base 10, then expand the decimal fraction with unknowns and match coefficients.

Exam route:

$(0.1101)_{2} = 1/2 + 1/4 + 1/16 = 0.5 + 0.25 + 0.0625 = 0.812 5_{10}$ .
$(0.8 x y 5)_{10} = 0.8 + x /100 + y /1000 + 5/10000 = 0.8005 + 0.01 x + 0.001 y$ .
Equate: $0.8125 = 0.8005 + 0.01 x + 0.001 y ⟹ 0.012 = 0.01 x + 0.001 y$ .
Multiply by 1000: $12 = 10 x + y$ . Since $x, y$ are single digits, $x = 1, y = 2$ .
$x + y = 1 + 2 = 3$ .

Learning route:

This is a mixed-base fractional equation. The most efficient strategy is to convert the fully known side to Base 10 first.

Step 1: Convert $(0.1101)_{2}$ to Base 10.

The weights are $2^{- 1} = 0.5$ , $2^{- 2} = 0.25$ , $2^{- 3} = 0.125$ , $2^{- 4} = 0.0625$ .

$1 (0.5) + 1 (0.25) + 0 (0.125) + 1 (0.0625) = 0.812 5_{10}$ .

Step 2: Expand the right side $(0.8 x y 5)_{10}$ using decimal positional weights.

$0.8 + x (1 0^{- 2}) + y (1 0^{- 3}) + 5 (1 0^{- 4}) = 0.8 + 0.01 x + 0.001 y + 0.0005 = 0.8005 + 0.01 x + 0.001 y$ .

Step 3: Equate the two Base 10 values.

$0.8125 = 0.8005 + 0.01 x + 0.001 y$

$0.0120 = 0.01 x + 0.001 y$

Multiply the entire equation by 1000 to clear decimals:

$12 = 10 x + y$

Since $x$ and $y$ are single decimal digits (0-9), the only solution is $x = 1$ and $y = 2$ .

Step 4: Calculate $x + y = 1 + 2 = 3$ .

Question 30 · Digital Logic · 2021_Set2 MCQ

Suppose we want to design a synchronous circuit that processes a string of 0’s and 1’s. Given a string, it produces another string by replacing the first 1 in any subsequence of consecutive 1’s by a 0. Consider the following example.

Input sequence: 00100011000011100
Output sequence: 00000001000001100

A Mealy Machine is a state machine where both the next state and the output are functions of the present state and the current input.
The above mentioned circuit can be designed as a two-state Mealy machine. The states in the Mealy machine can be represented using Boolean values 0 and 1. We denote the current state, the next state, the next incoming bit, and the output bit of the Mealy machine by the variables

s

t

b

and

y

respectively.
Assume the initial state of the Mealy machine is 0.

What are the Boolean expressions corresponding to

t

and

y

in terms of

s

and

b

A. $t = s + b$
$y = s b$
B. $t = b$
$y = s b$
C. $t = b$
$y = s \overline{b}$
D. $t = s + b$
$y = \overline{s b}$

Correct Answer:

Step-by-Step Solution

Insight: The problem describes a sequence processor that replaces the first '1' in a block of consecutive '1's with '0', while leaving subsequent '1's unchanged. This requires tracking whether we are currently inside a block of '1's.

Exam route: Define state s=0 as "not in a block of 1s" and s=1 as "inside a block of 1s". Trace transitions: from s=0, input b=1 gives output y=0 (replaced) and next state t=1. From s=1, input b=1 gives output y=1 (unchanged) and next state t=1. This matches t=b and y=s AND b.

Learning route:

Step 1: Understand the Mealy machine requirement. Output y depends on current state s and input b.

Step 2: Analyze state s=0. If b=0, we stay in s=0, output y=0. If b=1, this is the first '1', so output y=0, and we move to s=1. Thus, when s=0, t=b and y=0.

Step 3: Analyze state s=1. If b=0, the block of '1's ends, so we move to s=0, output y=0. If b=1, it's a subsequent '1', so output y=1, and we stay in s=1. Thus, when s=1, t=b and y=b.

Step 4: Combine the conditions. For t, in both s=0 and s=1, t=b. For y, y is 1 only when s=1 and b=1, which is the logical AND: y = s AND b.

Step 5: Verify with the example. Input 0010001100... -> Output 0000000100... matches perfectly.

Verification: Plugging s=0, b=1 into t=b, y=sb gives t=1, y=0. Plugging s=1, b=1 gives t=1, y=1. This perfectly matches the required behavior.

Question 31 · Computer Networks · 2021_Set2 MCQ

Consider the three-way handshake mechanism followed during TCP connection establishment between hosts P and Q. Let X and Y be two random 32-bit starting sequence numbers chosen by P and Q respectively. Suppose P sends a TCP connection request message to Q with a TCP segment having SYN bit = 1, SEQ number = X, and ACK bit = 0. Suppose Q accepts the connection request. Which one of the following choices represents the information present in the TCP segment header that is sent by Q to P?

A.
SYN bit = 1, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 0
B.
SYN bit = 0, SEQ number = X+1, ACK bit = 0, ACK number = Y, FIN bit = 1
C.
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X+1, FIN bit = 0
D.
SYN bit = 1, SEQ number = Y, ACK bit = 1, ACK number = X, FIN bit = 0

Question 32 · Computer Networks · 2021_Set2 MCQ

Consider the cyclic redundancy check (CRC) based error detecting scheme having the generator polynomial $X^{3} + X + 1$ . Suppose the message $m_{4} m_{3} m_{2} m_{1} m_{0} = 11000$ is to be transmitted. Check bits $c_{2} c_{1} c_{0}$ are appended at the end of the message by the transmitter using the above CRC scheme. The transmitted bit string is denoted by $m_{4} m_{3} m_{2} m_{1} m_{0} c_{2} c_{1} c_{0}$ . The value of the checkbit sequence $c_{2} c_{1} c_{0}$ is

A.
101
B.
110
C.
100
D.
111

Question 33 · Computer Networks · 2021_Set2 MSQ

Consider a computer network using the distance vector routing algorithm in its network layer. The partial topology of the network is as shown below.

The objective is to find the shortest-cost path from the router

R

to routers

P

and

Q

. Assume that

R

does not initially know the shortest routes to

P

and

Q

. Assume that

R

has three neighbouring routers denoted as

X

Y

, and

Z

. During one iteration,

R

measures its distance to its neighbours

X

Y

, and

Z

as 3, 2, and 5, respectively. Router

R

gets routing vectors from its neighbours that indicate that the distance to router

P

from routers

X

Y

, and

Z

are 7, 6, and 5, respectively. The routing vector also indicates that the distance to router

Q

from routers

X

Y

, and

Z

are 4, 6, and 8, respectively. Which of the following statement(s) is/are correct with respect to the new routing table of

R

, after updation during this iteration?

A.
The distance from $R$ to $P$ will be stored as 10.
B.
The distance from $R$ to $Q$ will be stored as 7.
C.
The next hop router for a packet from $R$ to $P$ is $Y$ .
D.
The next hop router for a packet from $R$ to $Q$ is $Z$ .

Question 34 · Verbal Aptitude · 2021_Set2 MCQ

Gauri said that she can play the keyboard __________ her sister.

A.
as well as
B.
as better as
C.
as nicest as
D.
as worse as

Correct Answer:

Step-by-Step Solution

Insight: The correlative conjunction "as ... as" strictly requires the positive degree of an adjective or adverb.

Exam route: The sentence compares Gauri's ability to her sister's. The structure "as [adverb] as" demands the base (positive) form. "Well" is the positive adverb. "Better" and "worse" are comparative, and "nicest" is superlative. Thus, "as well as" is the only grammatically valid choice.

Learning route:

Step 1: Identify the comparison structure. The sentence uses "as ... as", which is the standard marker for the positive degree of comparison.

Step 2: Evaluate the options based on degrees.

"well" is the positive degree of the adverb (good $\to$ better $\to$ best; well $\to$ better $\to$ best).
"better" is comparative and must be followed by "than", not "as".
"nicest" is superlative and requires "the" and a group context.
"worse" is comparative and requires "than".

Step 3: Conclude that only "well" fits the "as ... as" sandwich.

Common trap: Students might think "better" sounds more natural in casual speech, but "as better as" is a severe grammatical error in formal English.

Verification: "Gauri said that she can play the keyboard as well as her sister." This correctly compares their skills using the positive degree.

Question 35 · Verbal Aptitude · 2021_Set2 MCQ

Listening to music during exercise improves exercise performance and reduces discomfort. Scientists researched whether listening to music while studying can help students learn better and the results were inconclusive. Students who needed external stimulation for studying fared worse while students who did not need any external stimulation benefited from music.

Which one of the following statements is the CORRECT inference of the above passage?

A.
Listening to music has no effect on learning and a positive effect on physical exercise.
B.
Listening to music has a clear positive effect both on physical exercise and on learning.
C.
Listening to music has a clear positive effect on physical exercise. Music has a positive effect on learning only in some students.
D.
Listening to music has a clear positive effect on learning in all students. Music has a positive effect only in some students who exercise.

Correct Answer:

Step-by-Step Solution

Insight: Inference must combine the explicit facts from the passage without generalizing partial effects ("some students") to universal effects ("all students").

Exam route: Fact 1 states music improves exercise. Fact 2 states music helps learning only for students who do not need external stimulation (i.e., "some" students). Option C combines these accurately.

Learning route:

Analyze the first sentence: "Listening to music during exercise improves exercise performance and reduces discomfort." This establishes a clear positive effect on physical exercise.
Analyze the second and third sentences: The results on learning were "inconclusive" overall. Why? Because "students who needed external stimulation... fared worse" while "students who did not need any external stimulation benefited".
Synthesize the learning effect: Music does NOT help everyone learn. It helps a specific subset (those who don't need external stimulation). Therefore, it has a positive effect on learning "only in some students".
Evaluate Option A: Claims music has "no effect on learning". False, it benefited some students.
Evaluate Option B: Claims a "clear positive effect... on learning". False, the overall results were inconclusive because it made some students fare worse.
Evaluate Option C: "Clear positive effect on physical exercise" (Matches sentence 1). "Positive effect on learning only in some students" (Matches sentences 2 & 3). Correct.
Evaluate Option D: Claims positive effect on learning in "all students". False, contradicts the text.
Conclusion: Option C is the correct inference.

Question 36 · Spatial Aptitude · 2021_Set2 MCQ

A transparent square sheet shown above is folded along the dotted line. The folded sheet will look like ________.

Correct Answer:

Step-by-Step Solution

Key idea: Folding a transparent sheet reflects the drawn patterns across the fold line, and because it is transparent, both the original and mirrored patterns are visible simultaneously (superposition).

Step 1: Identify the fold line and direction.

The dotted line is vertical, passing through the center ( $x = 110$ ). The options show the right half remaining, implying the left half is folded over onto the right half.

Step 2: Reflect the left-side patterns onto the right side.

Original patterns on the LEFT ( $x < 110$ ):

A curve segment in the bottom-left quadrant.
Two vertical line segments.

Original patterns on the RIGHT ( $x > 110$ ):

A curve segment in the bottom-right quadrant.
Two slanted/horizontal line segments.

Step 3: Analyze the superposition on the right half.

The left curve mirrors across $x = 110$ to perfectly overlap with the existing right curve (they form a continuous symmetric wave).
The two vertical lines on the left will mirror to become two vertical lines on the right side.
The original right-side patterns (two slanted lines) remain unchanged and visible through the transparent sheet.

Step 4: Evaluate the options.

Option A shows both the two vertical lines (mirrored from the left) and the two slanted lines (original on the right). This matches our superposition analysis.
Option B distorts the curves and misses the line reflections.
Option C only shows the slanted lines, ignoring the mirrored vertical lines from the left half.
Option D shows a connected loop, which does not result from reflecting disjoint vertical lines.

Answer: A

Question 37 · Spatial Aptitude · 2021_Set2 MCQ

A jigsaw puzzle has 2 pieces. One of the pieces is shown above. Which one of the given options for the missing piece when assembled will form a rectangle? The piece can be moved, rotated or flipped to assemble with the above piece.

Correct Answer:

Step-by-Step Solution

Key idea: This is a shape assembly problem requiring us to find the complementary piece that forms a rectangle when combined with the given jigsaw piece.

Step 1: Analyze the given piece.

The provided piece has a complex boundary with specific protrusions (outward bumps) and indentations (inward cuts).

Step 2: Determine the required negative space.

To form a rectangle, the missing piece must have the exact geometric inverse of this boundary. Every protrusion on the given piece must fit into an indentation on the missing piece, and vice versa.

Step 3: Check the outer boundary requirements.

The combined shape must be a rectangle. Therefore, the missing piece must supply the straight outer edges that the given piece lacks to complete the rectangular perimeter.

Step 4: Evaluate the options.

Option A, when appropriately rotated or flipped, provides the exact complementary boundary features and the necessary straight edges to form a perfect rectangle without gaps or overlaps. Options B, C, and D have mismatched sequences of bumps and cuts.

Answer: A

Question 38 · Analytical Aptitude · 2021_Set2 MCQ

Pen : Write :: Knife : _________

Which one of the following options maintains a similar logical relation in the above?

A.
Vegetables
B.
Sharp
C.
Cut
D.
Blunt

Correct Answer:

Step-by-Step Solution

Insight: This is a Tool-to-Function analogy. The relationship is "A [Tool] is primarily used to [Action]".

Exam route: A Pen is used to Write. Applying the same bridge sentence, a Knife is used to Cut.

Learning route:

Step 1: Isolate the given pair: Pen : Write.

Step 2: Formulate the Bridge Sentence: "A [Pen] is a tool used to [Write]."

Step 3: Test this exact sentence structure on the target: "A [Knife] is a tool used to [?]."

Step 4: Evaluate options. "Cut" fits perfectly. "Vegetables" is the object acted upon, not the action. "Sharp" is an attribute, not a function. "Blunt" is the opposite attribute.

Step 5: Verify directionality. Tool $\to$ Function. Pen $\to$ Write. Knife $\to$ Cut. The logical relation is perfectly maintained.

Question 39 · Analytical Aptitude · 2021_Set2 MCQ

Six students P, Q, R, S, T and U, with distinct heights, compare their heights and make the following observations.

Observation I: S is taller than R.

Observation II: Q is the shortest of all.

Observation III: U is taller than only one student.

Observation IV: T is taller than S but is not the tallest.

The number of students that are taller than R is the same as the number of students shorter than ______.

A.
T
B.
R
C.
S
D.
P

Correct Answer:

Step-by-Step Solution

Insight: Anchor the extremes (shortest, tallest) first, then chain the relative inequalities to build the complete order.

Exam route: Q is shortest (Rank 1). U is taller than only one (Rank 2). Remaining: P, R, S, T for Ranks 3, 4, 5, 6. We know T > S > R. Since T is not the tallest, P must be Rank 6 (tallest). This forces T = 5, S = 4, R = 3. Students taller than R (Ranks 4, 5, 6) = 3. Students shorter than S (Ranks 1, 2, 3) = 3. Match is S.

Learning route:

Step 1: Assign absolute ranks to extremes. Q = 1 (shortest). U = 2 (taller than only Q).

Step 2: Identify the remaining pool: {P, R, S, T} for ranks {3, 4, 5, 6}.

Step 3: Chain the relative clues: T > S and S > R $\to$ T > S > R.

Step 4: Apply the negative constraint: "T is not the tallest". Since T > S > R, T must be at least Rank 4. If T were Rank 6, it would be the tallest. Thus, P must be Rank 6.

Step 5: Fill the remaining slots: T = 5, S = 4, R = 3.

Step 6: Answer the specific query. Taller than R (Ranks 4, 5, 6 $\to$ S, T, P) is 3 students. We need someone with exactly 3 students shorter than them. S (Rank 4) has Ranks 1, 2, 3 (Q, U, R) shorter than them. Count = 3. Match confirmed.

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 2021_Set2 Question Paper with Solutions: 65 Questions, Answer Key & Section-wise Analysis

Paper breakdown

Free sample questions from GATE CS 2021_Set2 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