GATE CS 2021 Official Paper: Shift 1 (Previous Year Paper)

Given:

The ratio of boys and girls in a class is 7 : 3

Calculation:

Let be assume boys and girls in a class is 7x and 3x respectively.

⇒ The sum of boys and girls = 7x + 3x = 10x

⇒ The total number of strength of the class will be multiple of 10 so 50 will be the right answer

∴ The required result will be 50.

Given:

Different types of figures

Calculation:

⇒ In any two points are inside in polygon, then line by joining these points will also be inside same polygon.

⇒ The polygon in the first image is not convex because if you take any two corner points then it will not be inside the polygon.

∴ The required result will be an option "1".

The correct answer is '1 is grammatically correct and 2 is ambiguous'.

Key Points

• Everybody in the class is prepared for the exam. This statement i.e. statement 1 is grammatically correct.
• Babu invited Danish to his home because he enjoys playing chess. This statement i.e. statement 2 is ambiguous as there is no guarantee that Danish knows playing chess. Moreover, it is stated that Babu invited Danish to his home but we can not conclude that he called him to play chess as it has been simply mentioned that Babu enjoys playing chess. There are many possible meanings or derivations of this statement.

Important Points

• Ambiguous means having or expressing more than one possible meaning, sometimes intentionally.

After unfolding the folded figure;

Hence, option (4) is the correct answer.

Doctor does surgery.

Similarly;

Writer writes book.

Hence, "Doctor, book" is the correct answer.

Given:

Two rectangular sheets M and N have the dimension 6 cm × 1 cm each,  in which cylinder will be formed by bringing the short edges of the sheet together. Given that ends of the cylinder are closed.

Concept:

Volume of cylinder = π × r² × h

The volume of the cube = a³

Calculation:

Let be assume the side of the cube is a,

⇒ The area of the sheet N = 6 × a²

⇒ 6 × 1 = 6 × a²

⇒ a = 1

⇒ Volume of the cube = a³ = 1³ = 1

⇒  The circumference  = 6

⇒ 2 × π × r = 6, r = 3/π and height of the cylinder = 1 cm

⇒ Volume of the cylinder = π × (3/π)² × 1 = 9/π 

⇒ The required ratio = 9/π : 1

∴ The required result will be 9/π .

Given:

The Marked price of Q is 10,000

Calculation:

⇒ The cost price of Q = 5400 × (4/3) = 7200

⇒ The selling price of Q = 7200 × (5/4) = 90,00

⇒ Discount % on Q = (10000 - 9000)/10000 × (100) = 10%

∴ The required result will be 10%.

Data:

To find the probability that no two chocolate are identical = P(k)

To find the probability that at least two chocolates are identical = P(x):

Formula:

P(x) = 1 - P(k)

Calculation

No two cholocate identical:

From 1^st bag = Probability = \(\frac{10}{10}\)

From 2^nd bag = Probability = \(\frac{9}{10}\)

From 3^rd bag = Probability = \(\frac{8}{10}\)

From 4^th bag = Probability = \(\frac{7}{10}\)

From 5^th bag = Probability = \(\frac{6}{10}\)

P(k) = \(\frac{10 \times 9 \times 8 \times7\times6}{10\times 10 \times10 \times 10 \times10} = 0.3024\)

P(x) = 1 - P(k) = 1 - 0.3024

∴ The required result will be P(x) = 0.6976.

The least possible Venn diagram is:

Conclusion I: Some pathogens are bacteria → False (There is no direct relation between bacteria and pathogens)

Conclusion II: All pathogens are not bacteria → False (There is no direct relation between bacteria and pathogens, No definite relation)

Hence, Neither I nor II is correct.

The correct answer is AOM are addressing the problem superficially.

Key Points

• The passage talks about the core problems that cause obesity: poverty and income inequality and how measures like AOM addresses such problems.
• But, AOM are not addressing the main problems directly. It is a kind of generic step taken to address obesity. So, AOMs are addressing these problems superficially only and not addressing the real problems.
• Thus, we can conclude that the statement - AOM are addressing the problem superficially, summarizes the passage.
• Hence, option 4 is the most appropriate answer choice.

Concepts:

Operation under which context-free language is not closed: Intersection, complementation, set difference

Operation under which context-free language is closed: Union, Kleene Closure, and Concatenation.

Context-free language is closed under Intersection with regular language.

Explanation:

L1 is a regular and L2 is a context-free language.

Every regular language is context-free language.

Option 1: context-free language

\({L_1}.{L_2}\) it is the context-free language because it is closed under Concatenation.

Option 2:context-free language

L1 ∪ L2 it is the context-free language because it is closed under Union.

Option 3: context-free language

\({L_1} \cap ;{L_2}\) it is the context-free language because context-free language is closed under Intersection with regular language.

Option 4: may not be context-free language

L1 - L2  it may not be context-free language because it is not closed under complementation.

Answer: Option 3

Explanation:

Recurrence Relation For no of comparison for finding Minimum and Maximum of an arbitrary array: T(n) = 2T(n/2) + 2 using divide and conquer tournament method.

after solving

T(n) =  \(3\left( {\frac{n}{2}} \right) - 2\)

(Worst case)

Option 1: t > 2n - 2

It is not correct.

Option 2: ​\(t > 3\left\lceil {\frac{n}{2}} \right\rceil \) and t ≤ 2n - 2

It is not correct. because lowest upper bound  \(t ≤ 3\left\lceil {\frac{n}{2}} \right\rceil \)

Option 3: t>n and \(t ≤ 3\left\lceil {\frac{n}{2}} \right\rceil \)

It is correct. at least n comparison required to find maximum and Minimum and max will be \( 3\left\lceil {\frac{n}{2}} \right\rceil \).

Option 4: \(t > \left\lceil {{{\log }_2}(n)} \right\rceil \) and t≤ n

It is not correct.

Explanation:

f1 = 10n 

By taking log

f₁ = n× log(10)

f2 = nlogn

By taking log

f2 = logn × logn

f3 = n√n

By taking log 

f3 = √n × logn 

asymptotic growth rate: f2 < f3  < f1

Therefore option 4 is correct

Important Points

Take n equal to very large number  to verify the result

Answer: Option 1

Explanation:

Statement 1:The sequence of procedure calls corresponds to a preorder traversal of the activation tree.

Consider following example 

Fun( int n )

{

 if( n==0 || n==1) 

  return n;

else {

return Fun(n/2) + Fun(n/2) ;

}

Suppose function call made as Fun(8). now recursion tree will be  

The Function call sequence will be (in terms of n): 8, 4, 2, 1, 1, 2, 1, 1, 4, 2, 1, 1, 2, 1, 1 ( Same as pre-order traversal of the tree )

The Function Returning Sequence will be : 1, 1, 2, 1, 1, 2, 4, 1, 1, 2, 1, 1, 2, 4, 8 ( Same as post-order traversal of the tree)

Hence This Statement is correct.

Statement 2:

This Statement is also correct.

Answer: Option 1

Explanation:

Statement 1:Every SLR(1) grammar is unambiguous but there are certain unambiguous grammars that are not SLR(1).

As you can see in the diagram Not all Unambiguous grammars are SLR(1) but All SLR(1) grammars are Unambiguous.

This Statement is True.

Statement 2:For any context-free grammar, there is a parser that takes at most O(n3) time to parse a string of length n.

This Statement is also True. There exists a standard algorithm for general Context-free grammars known as the CYK algorithm whose time complexity is O(n3).

Note:

• LR parsers have linear time(O(n)) complexity.

Concept:

Step 1: Conversion: base 3 to decimal

Step 2: Conversion: decimal to Hexadecimal

Calculation:

Step 1:

Conversion: base 3 to decimal

(210)3 = 2 × 32 + 1 × 3¹ + 0 × 30

= 18 + 3 = 21

Step 2:

Conversion: decimal to Hexadecimal

 

Read the remainder from bottom to top: (15)₁₆

Data:

¬ ≡ NOT ≡ ̅ 

OR ≡ ∨ ≡ +

AND ≡ ∧ ≡ .

Formula:

a → b ≡ a̅ + b

Calculation:

S₁ : (¬p ∧ (p ∨ q)) → q 

S₁ ≡ (p̅.(p + q) → q

S₁ ≡ (p̅.p + p̅.q) → q

S₁ ≡ (p̅.q) → q

S₁ ≡ \(\overline{\overline p.q} + q\)

S₁ ≡ p + q̅ + q ≡ p + 1 ≡ 1

S1 is a tautology

S₂ ≡  q → (¬p ∧ (p ∨ q))

S2 ≡ q → (p̅.(p + q))

S2 ≡ q̅  + (p̅.p + p̅.q)) 

S2 ≡ q̅ + p̅.q ≡ p̅ + q̅  

S2 is not a tautology.

Therefore option 4 is correct

Answer: Option 3

Concept:

Address Resolution Protocol:

• ARP resolves an IP address to a MAC address.
• The purpose of the ARP request packet is to query all the other hosts and routers on the subnet to determine the MAC address corresponding to the IP address that is being resolved.
• The ARP Request Packet, broadcast to all other hosts and routers on the subnet using MAC broadcast address, namely, FF-FF-FF-FF-FF-FF.
• The ARP reply will be a unicast packet that contains the desired mapping.

Explanation:

Statement 1:Destination MAC address of an ARP reply is a broadcast address.

This is not correct as the Destination MAC address of ARP reply will be a unicast address as ARP reply will be a unicast packet.

Statement 2: Destination MAC address of an ARP request is a broadcast address.

This is correct.

Insertion sort:

In Insertion sort, the best-case takes Θ (n) time, the best case of insertion sort is when elements are sorted in ascending order. In that case, the number of comparisons will be n - 1 = 8 - 1 = 7

It is the least  number of comparisons (among the array elements) to sort the above array in ascending order:

The number of swaps needed is zero.

Additional Information

In Insertion sort, the worst-case takes Θ (n2) time, the worst case of insertion sort is when elements are sorted in reverse order. In that case the number of comparisons will be like:

\(\mathop \sum \limits_{{\rm{p}} = 1}^{{\rm{N}} - 1} {\rm{p}} = 1 + 2 + 3 + \ldots . + {\rm{N}} - 1 = {\rm{;}}\frac{{{\rm{N}}\left( {{\rm{N}} - 1} \right)}}{2} - 1\)

This will give Θ (n2) time complexity.

Explanation:

• If an element in a binary search tree is smaller than any other element in the binary search tree then it is smaller than the maximum element.
• All the elements in the binary search tree is distinct.
• Compare only two elements in the binary search tree to find such elements.
• Therefore time complexity is θ(1).

Key Points

• Pages are divided into fixed-size slots and hence no external fragmentation. But applications smaller than page size cause internal fragmentation
• Page tables take extra pages in memory. Therefore incur an extra cost

Therefore option 1 and 2 are correct

Answer: Option 1

Explanation:

Option 1:L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = ∑*}

This is not Recursive. As completeness Problem is Undecidable for CFL and Hence no algorithm exists to decide whether or not the Language of PDA is ∑^*.

Option 2: L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = Φ}

This is Recursive. for DFA accept empty language Algorithm exists

Option 3: L = { \(\left\langle M \right\rangle \) | M is a PDA such that L(M) = Φ}

This is also Recursive. for a CFL to checking for empty language problem is decidable. Hence there exists an algorithm to decide whether a PDA accepts empty language or not.

Option 4:L = { \(\left\langle M \right\rangle \) | M is a DFA such that L(M) = ∑*}

This is also Recursive. Completeness problem for regular language is decidable.

Answer: Option 1

Explanation:

Option 1:The same undo and redo list will be used while recovering again.

This Option is correct. Because in log files operations are idempotent, doing undo-redo operations multiple times yields the same results.

Option 2:The database will become inconsistent.

This option is not correct.

Option 3: All the transactions that are already undone and redone will not be recovered again.

This Option is not correct because transactions that are already undone and redone will be recovered with undo and redo list; performing undo and redo again will produce the same result in the Database.

Option 4: The system cannot recover any further.

This Option is not correct.

strlen:

This is a function defined in the standard C library and doesn’t require any system call to perform its function of calculating the string length.

malloc: 

This is a function defined in the standard C library and it does not always invoke the system call. When a process is created, a certain amount of heap memory is already allocated to it, when required to expand or shrink that memory, it internally uses sbrk/brk system call on Unix/Linux

exit:

This is a function defined in standard C library and it always invokes system call every time, flushes the streams, and terminates the caller.

sleep:

This is not even a standard C library function, it is a POSIX standard c library function. Unix and Windows use different header files for it.

Therefore option 3 and 4 are correct options

Answer: Option 1 and Option 4

Explanation:

Option 1: Renaming of an existing file in foo.

This Option is correct as for the Renaming operation of a file in a directory the New name must not create conflict to any of the existing file names. Hence a full scan is required for successful completion.

Option 2: Opening of an existing file in foo.

This option is not correct as Opening the file does not require a full scan.

Option 3:Deletion of an existing file from foo.

This Option is not Correct. as Deletion of a file does not require a full scan.

Option 4: Creation of a new file in foo.

This Option is correct as While Creating a new file we need to check whether the newly created file name must not create conflict to any of the existing file names. Hence a full scan is required for successful completion.

Data

Number of vertices = V = 8

Number of faces = 5

Number of edges = E

Euler's formula:

V + F = E + 2

Calculation

⇒ E = V + F - 2

⇒ E = 8 + 5 - 2

⇒ E = 11 

∴ Number of edges is 11

Answer:3 to 3

Concept:

A minimum spanning tree (MST) or minimum weight spanning tree is a subset of the edges(V – 1 ) of a connected, edge-weighted undirected graph G(V, E) that connects all the vertices together, without any cycles and with the minimum possible total edge weight.

Explanation:

The minimum weight in the graph is 0.1 choosing this we get.

Suppose we get two trees T₁ and T_2.

To connect to those two trees we got 3 possible edges of weight 0.9.

Hence we can choose any one of those 3 edges.

No of Minimum weight spanning tree is 3.

Answer:0.35 to 0.39 

Formula:

Exponential Distribution:

P(X>b) = e^-λb

P(X<=b) = 1-e^-λb

Expected Value (Mean) = \(\frac{1}{λ }\)

Calculation: 

We are Required to find the probability that, its lifetime exceeds the expected lifetime then

P(X>\(\frac{1}{λ }\)) = e^{-λ×\(\frac{1}{λ }\)} = e^-1 ≈ 0.37

Answer: 65 to 65

Explanation:

There are 6 jobs each with a distinct difficulty level and 3 computers each with distinct processing speed.

C₁ being the fastest computer assigned the toughest job and C₃ being the slowest assigned easiest job.

Hence 4 job left 

Now if we can assign any of the jobs to any computer then 3⁴ = 81 possibility

Every computer gets at least one job then we have to subtract the scenario where computer C₂ has not got any job because C₁ and C₃ got at least one job already according to the first constraint.

= 2⁴          //  where C₂ not getting any job to execute

 81-16 = 65

\(let ;L=\mathop {\lim }\limits_{x \to -3} \frac{{\sqrt {2x + 22} - 4}}{{x + 3}}\)

Since it is of the \(\frac{0}{0} \) form

Apply L Hopital's rule

\(L=\mathop {\lim }\limits_{x \to -3} \frac{\frac{d}{dx}({\sqrt {2x + 22} - 4)}}{{\frac{d}{dx}(x + 3)}}\)

\(L=\mathop {\lim }\limits_{x \to -3} \frac{{\frac{2}{2\sqrt {2x + 22 }} }}{{1 }}\)

Substitute the value

L = \(\frac{1}{4} = 0.25\)

The value of the above expression is 0.25

Stack:

push(54)

 

push(52)

 

pop()

 

push(55)

 

push(62)

 

s = pop() = 62

Queue

enqueue(21)

 

enqueue(24)

 

dequeue()

 

enqueue(28)

 

enqueue(32)

 

q = dequeue() =  24

s + q = 62 + 24 = 86

The value of s + q is 86

Concept

Memory address = 232 bytes

Data Cache = 32  KB = 215 B

Block Size = 64 bytes = 26 B

Formula:

In a direct Mapped, main memory can be represented as

 

32 = tag + lines + Block offset (In bits)

Calculation:

Assume byte addressable:

\({\rm{number;of;lines;in;cache;memory}} = \frac{{{2^{15}}}}{{{2^6}}} = {2^{9}}\)

32 = tag + 9 + 6

∴ tag = 17 bits

Alternate Method

32 = tag + Cache size (in bits)

∴ tag = 32 - 15 = 17

Answer: 819 to 820 OR 205 to 205

Explanation:

σ(A>10)∨(B=18)(r) 

case 1: (A >10) 

Allowed A values are (11, 12, 13, 14, 15, 16, 17, 18, 19, 20) total 10

This can map to all values of B (1, 2, 3, ......, 20) total 20 

Hence number of (A,B)  pairs = 10× 20 = 200 (Remember Here 10 pairs are also counted where B = 18 )

case 2:(B=18)

Allowed B values are (18) 

This can map to all values of  A (6, 9, 10, 11,...,20) total 15 

Hence number of (A,B)  pairs = 15 × 1 = 15 

Since OR operation is used in condition part 

Total pairs = 215 But we have to subtract the tuples which are being counted twice 

= 215 - 10 => 205

Note:

This Question can be done in a probabilistic way since the estimated number of the tuple is asked

P(A>10) = 10/15 = 2/3

P(B=18) = 1/20

P[(A>10) ∧  (B=18)] = (2/3)× (1/20) = 1/30

P[(A>10) ∨ (B=18)] =  P(A>10) + P(B=18) - P[(A>10) ∧  (B=18)]

 P[(A>10) ∨ (B=18)]  = (2/3) + (1/20) - (1/30) = 41/60

Estimated Number of tuples = (41/60) × 1200 = 820

Concept:

In IEEE- 754 single-precision format, a floating-point number is represented in 32 bits.

 

Sign bit value 0 means a positive number, and 1 means a negative number.

The floating-point number can be obtained by formula: (-1)s × 1.M × 2E – 127

Explanation: 

 

Exponent = 10000001 = 129

decimal value = (-1)1 × 1.1111...0 × 2129 – 127 =  (-1)1 ×1.1111 × 22 

The decimal value corresponding to the above representation (rounded to 2 decimal places) is -7.75

Key Points

The scheduler has prior knowledge about the length of the CPU bursts and it is non-preemptive.

Therefore shortest job first algorithms while giving minimum achievable average waiting

Gantt chart:

0            10           26            46

Process table:

 

Average waiting time = \(\frac{0~+10+26}{3} = 12; ms\)

Average waiting time = 12 ms

Important Points:

TAT = CT – AT

WT = TAT – BT

Answer: Option 4

Explanation:

Option 1:The actions will lead to an infinite loop.

This statement is not correct.

Option 2:The actions can be used to correctly type-check any syntactically correct program.

This statement is not correct. Because These SDT actions can not type-check boolean expressions or float expressions.

for example :

float a=3.46;

bool b = 0,c;

c = a+b; 

Option 3:The actions can be used to type-check syntactically correct boolean variable declarations and boolean expressions.

This statement is not correct. Because the SDT actions can not be used to correctly type check boolean expressions.

for example : 

bool a = 0;

bool b = 1;

bool c = a+b;

Option 4:The actions can be used to type-check syntactically correct integer variable declarations and integer expressions.

This statement is Correct. Because These SDT actions can be used to correctly type check both integer variables and integer expressions as well.

Answer: Option 2

Explanation:

Consider the empAge(empNo, age) Table

We run the following Query on above Table 

IIempNo(empAge ⋈ (age>age1) ρempNo 1, age1(empAge))

We get Output Table as 

Hence the Output is "Employees whose age greater than at least one employee" or "Employees whose age is no minimum".

Answer: Option 3

Concept:

XOR Operation :

Explanation:

T_P = R Hence P⁺ = R⊕ P

TQ = P̅  Hence Q+ = P̅ ⊕ Q

T_R = Q̅ Hence R⁺ = Q̅ ⊕ R

Next 3 states are 000 → 011 →101 → 000

Answer: Option 4

Data: 

 

Codeword =  d8d7d6d5c8d4d3d2c4d1c2c1

Codeword = 

 

C₁=B1 ⊕ B3 ⊕ B5 ⊕ B7 ⊕ B9 ⊕ B11 = 0 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ x ⊕ 1; for even parity x=0

C₂ = B2 ⊕ B3 ⊕ B6 ⊕ B7 ⊕ B10 ⊕ B11 = 1 ⊕ 1 ⊕ 1 ⊕ 0 ⊕ 0 ⊕ 1;

C₄ = B4 ⊕ B5 ⊕ B6 ⊕ B7 ⊕ B12 = 0 ⊕ 0 ⊕ 1 ⊕ 0 ⊕ 1; 

C₈ = y ⊕ 0⊕ 0 ⊕ 1⊕  ⊕ 1; for even parity y = 0 (putting x = 0)

Answer: Option 4

Explanation:

T(n) = T(n/2) + T(2n/5) + 7n

T(n) = \(7n\left( {1 + ;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + ;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_2}n}}} \right)\) ( for left most subtree base of log is 2 But for rightmost subtree base will be (5/2))

For rightmost subtree:

T(n) =  \(7n\left( {1 + ;\frac{9}{{10}} + \frac{{81}}{{100}} + \ldots + ;{{\left( {\frac{9}{{10}}} \right)}^{{{\log }_{5/2}}n}}} \right)\)

T(n) = 7n(1-n^{\({\log _2}0.9\)})

T(n) = O(n) 

and similarly for right most subtree 

T(n) = Ω(n) 

hence T(n) = θ(n)

Answer: Option 1

Explanation:

For LL1 parsing we need to calculate first and follow set for all Non-terminals in the grammar.

 

 

at 1: S->Rf will be stored.

at 2: again S-> Rf will be stored. 

Because in first set(Rf) = c,f

at 3:T-> ϵ will be stored.

at 4: again T-> ϵ will be stored.

Because first set(T) = {a, b, ϵ}, In the column for 'a' and 'b' corresponding matching Rules are mentioned But first set also contains ϵ then ϵ-corresponding Rules will be filled according to follow set(T) = { c, f, $} in the LL1 table$.

Answer: Option 2

S₁: r1(x) r1(y) r2(x) r2(y) w2(y) w1(x)

Precedence Graph:

S₂:r1(x) r2(x) r2(y) w2(y) r1(y) w1(x)

Precedence Graph:

There exists a Cycle in Precedence of S₁. Hence S₁ is not Conflict Serializable.

Whereas S₂ is Conflict Serializable.

Answer: Option 4

Concept:

Lossless Decomposition:

for a Decomposition of two Relation, R₁ and R₂ to be lossless 2 condition needs to be satisfied that is

1. R1 ∩ R2 → R1 or R₂ i.e. common attributes must be key to either of the relation. 2. attributes of R1 ∪ attributes of R2 ≡ attributes of R

Explanation:

D1 : R = [(P, Q, S, T); (P, T, X); (Q, Y); (Y, Z, W)]

lets first take 2 relations R₁(P, Q, S, T )  R₂(P, T, X) 

common attributes are PT and PT → TX ( according to augmentation property )

so relation becomes R₁(P, Q, S, T, X) R₂(Q, Y) 

The common attribute is Q and Q→ Y is key to R₂ Hence (P, Q, S, T, X, Y)

 So now relation becomes R1(P, Q, S, T, X, Y) R2(Y, Z, W)

 The common attribute is Y and Y is key to R₂.

Hence all attributes get combined into one relation and hence this Decomposition is lossless.

D2 : R = [(P, Q, S); (T, X); (Q, Y); (Y, Z, W)]

If you observe relation (T, X); Its attributes not common to any other relations.

even if we combined all other attributes R₁(P, Q, S, Y, Z, W)  R₂(T, X) 

still no common attributes Hence this decomposition is lossy.

Concept

According to the Lagrange theorem order of subgroups must divide the order of the group.

Property of group says if a group has prime order then it is cyclic.

Explanation:

Since the order of G is 6. Therefore  its subgroup may have order 1,2,3,6

H is one of its subgroups with condition 1< |H| <6 so H may be of order 2 or 3  which is prime 

Hence H must be cyclic

The order of G is 6 which is not prime and hence it may or may not  be cyclic 

Therefore option 2 is correct

Answer: Option 4

Formula:

Covariance(cov):

cov(X, Y) = E[ (X - E[X]) ] [ (Y - E[Y]) ] 

Theorem:

If X and Y be Random Variables and Let the variances of X and Y exist and be finite then

cov(X,Y)² ≤ var(X)var(Y)

Statement 1:There exist random variables X and Y such that

(E[X - E(X)) (Y - E(Y))])2 > Var[X] Var[Y]

This is not correct. The Square of covariance is less than equal to the product of variance of the two random variables not greater than.

Statement 2:For all random variables X and Y,

Cov[X, Y] = E [|X - E[X]| |Y - E[Y]|]

This is also not correct because Covariance may result in negative as well but the given expression will generate positive value.

Answer: Option 3

Option 1: diam(G) < diam(G2) ≤ diam(G) 

This is not correct.

consider the follwing graph G

Adjacency Matrix will be

M = \(\left[ {\begin{array}{*{20}{c}} 0&1&0&0&1\ 1&0&1&1&0\ 0&1&0&1&1\ 0&1&1&0&1\ 1&0&1&1&0 \end{array}} \right]\)

The Diameter for this Graph G is 2.

P = M² = \(\left[ {\begin{array}{*{20}{c}} 0&1&2&2&1\ 1&0&1&1&3\ 2&1&0&1&1\ 2&1&1&0&1\ 1&3&1&1&0 \end{array}} \right]\)

Graph for G₂ is 

and Diameter for G₂ is 2 

Hence diameter of the graphs can be equal and if You observe Edges from Original graph G remains as it is G₂ as well. so Diameter(G) could never be less than Diameter(G₂)

Option 2: \(\left\lceil {diam(G)/2} \right\rceil \)< diam(G2) < diam(G)

This Option is not correct as stated above the diameter of the graphs (G and G₂) can be equal as well.

Option 3:diam(G2) ≤ \(\left\lceil {diam(G)/2} \right\rceil \)

This Option is correct.

Let's take one more example to prove this. Graph G

and its Adjacency Matrix 

M = \(\left[ {\begin{array}{*{20}{c}} 0&1&0&0&0\ 1&0&1&0&0\ 0&1&0&1&0\ 0&0&1&0&1\ 0&0&0&1&0 \end{array}} \right]\)

and its diameter is 4.

P = M² = \(\left[ {\begin{array}{*{20}{c}} 0&1&1&0&0\ 1&0&1&1&0\ 1&1&0&1&1\ 0&1&1&0&1\ 0&0&1&1&0 \end{array}} \right]\)

and its Graph G₂ is 

Its diameter is 2.

Option 4:diam(G2) = diam(G)

This Option is not correct.

Answer: Option 1

Explanation:

count = 0 and i = 0

if ((j >= 0) && (i++))

{count = count + j;}

• i will be incremented only when J≥0 and j will be added to count

count = count + i;

count = 6 + 4

count = 10

Hence 10 will be printed.

Option 1: Incorrect

string: 0111 is also accepted and it doesn't end with 011.

Option 2: Incorrect

string: 0110 is also accepted and it doesn't end with 011.

Option 3: InCorrect

Diagram in option needs to change

Option 4: correct

w ends with the substring 011

Concept:

A language is called Decidable or Recursive if there is a Turing machine that accepts and halts on every input string w. Every decidable language is Turing-Acceptable.

Explanation:

Algorithms L₁

Does not halt on all input taking more than 2021 steps → Yes

Halt on least one of the input taking less than 2021 steps → No:

Algorithms L2

Does not halt on at least one of the input taking  more than 2021 steps → Yes

Halt on all the input taking less than 2021 steps → No:

Answer: Option 3 and Option 4 

Data:

p[1] = 1, p[2] = 5, p[3] = 8,

p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18

Calculation: 

R₇= max amount and length can be integer 

maximum cost possible is 18 and there are 3 solutions for R₇.

Answer: Option 2

Explanation:

Option 1: If u is an articulation point in G such that x is an ancestor of u in T and y is a descendent of u in T, then all paths from x to y in G must pass through u.

 

Consider the above example U is an articulation point in graph G and x is the ancestor to U and y is the descendent of U. not all paths from X to Y in G pass through U.

Hence This statement is incorrect.

Option 2:Root of T is an articulation point in G if and only if it has 2 or more children.

This is Correct.

Consider the above example only; if we start DFS from U.

we get T as

 

U has 2 children and U is the articulation point in G.

Option 3:Root of T can never be an articulation point in G.

This is incorrect. for example, you can refer to Option 2 Same reasoning can be used to counter this option.

Option 4:A leaf of T can be an articulation point in G.

This is also incorrect. The Articulation point of G will never be a leaf of the DFS tree.

Formula:

(A + B)(A + C) = A + B.C

Calculation:

\(F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)\)

F = (X + Y + Z).(Y̅ + Z).(X̅ + Y)

F = (Z + Y̅.(X + Y)).(X̅ + Y)

F = (Z + X.Y̅ + Y.Y̅).(X̅ + Y)

F = (Z + X.Y̅).(X̅ + Y)   

F = (Z + X.Y̅).(X̅ + Y)

F = Z.(X̅ + Y) + (X.Y̅).(X̅ + Y)

F = Z.(X̅ + Y) + X.Y̅.X̅ + X.Y̅.Y

F = Z.(X̅ + Y)   

Taking complement on both sides

F̅ = \(\overline{Z.(\overline X + Y)}\)    

By Demorgan's law

F̅ = Z̅ + X.Y̅  =  X.Y̅ + Z ................. (B)

\(\overline F= (X + \overline Z ) . (\overline Y + \overline Z ) ...........(D)\)

Option C:

\(F = (X + Y + Z)(\overline X + Y)(\overline Y + Z)\)

Taking complement on both sides

\(\overline F= \overline X \overline Y \overline Z +X\overline Y + Y\overline Z \)

Hence option B, C and D are correct

Answer: Option 3

Concept:

Equivalence Relation:

For a Relation to be Equivalence Relation, Relation has to satisfy 3 property ;

1. Reflexive Property
2. Symmetric property
3. Transitive Property

Explanation:

Let's start with Option 3;

Option 3:if a relation S is reflexive and circular, then S is an equivalence relation.

It is correct.

• S is reflexive and circular; see that if are able to derive Symmetric and transitive property from these given properties.

aRa ∈ S and aRb ∈ S => bRa ∈ S   //Using Reflexive and circular 

aRb and bRa both exist then the relation is Symmetric.

 - Now 

 aRb and bRc together => cRa and according to symmetricity ≡  aRc 

aRb and bRc together => aRc

Hence Transitivity satisfied.

Hence S is an Equivalence Relation.

Example : S = { {a,a) (b.b) (c,c) } (diagonal relation)

Option 1: If a relation S is transitive and circular, then S is an equivalence relation.

It is not correct.

Consider a example of empty relation or S = {(a,b)}; it is transitive and circular but its not Equivalence Relation.

Hence S is not an equivalence Relation.

Option 2: If a relation S is reflexive and symmetric, then S is an equivalence relation.

It is not correct. For a Relation S to be Equivalence Reflexive, Symmetric and Transitive are required.

Option 4: if a relation S is circular and symmetric, then S is an equivalence relation.

It is not correct.

Consider a example of empty relation or S = {(a,b) , (b,a), (a,a)}; It is circular and symmetric but its not Equivalence relation.

Hence S is not an equivalence Relation.

Answer: Option 1, Option 2 and Option 4

Option 1:If the client sends a packet after the server reboot, it will receive an RST segment.

This Option is correct.

Because in Absence of Keepalive timer, after reboot TCP server does not remember info regarding previous connections and If it receives a packet from the client, it may generate reset segment.

Option 2:If the client was waiting to receive a packet, it may wait indefinitely.

This Option is also correct.

There is no Keepalive timer exists, then there is a possibility that the Client may keep waiting Indefinitely for the packet from the server.

Option 3: If the client sends a packet after the server reboot, it will receive a FIN segment.

This Option is not correct.

Fin Segment is not possible in the given scenario.

Option 4:The TCP server application on S can listen on P after reboot.

Thi Option is correct.

Suppose that TCP Server dedicated to only one process then it is possible that it will start listening to the process at client even after reboot.

Answer: Option 2 and Option 3

Explanation:

TCP Segment Size = 1400

Packet size = segment size + IP Header Size = 1400+ 20 = 1420 

At R Packet will be Fragmented 

MTU = 800 + 20 (Header) 

Hence Packet's Data (1400) will be divided in two packets = (800 + 600)

First Fragment  = (800 + 20) //Data + Header

Second Fragment  = ( 600 + 20 ) 

Option 1: The TCP destination port can be determined by analyzing only the second fragment.

This Option is not correct as Destination Port Number can be identified by looking at any packet or Fragment. not just only from Second Fragment.

Option 2:If the second fragment is lost, P is required to resend the whole TCP segment.

This is correct. If any of the Fragments is lost then the entire packet/TCP segment has to be retransmitted this one of the drawbacks of fragmentation.

Option 3:Two fragments are created at R and the IP datagram size carrying the second fragment is 620 bytes.

This is correct.

Option 4: If the second fragment is lost, R will resend the fragment with the IP identification value 0 × 1234.

This Option is not correct As If any of the Fragments is lost then the entire packet/TCP segment has to be retransmitted.

Answer: Option 1, Option 2 and Option 3

Explanation:

Increment operation in Line 7 is not atomic means while incrementing the variable process/thread can be preempted.

Increment Generally performed below mentioned 3 steps in assembly language.

load R₁, counter; // load value of counter from memory to register R₁

add R₁,#1;           //add 1 to the content of register R₁.

store R₁, counter;  //Store incremented value in counter (Memory)

Option 1:There is a deadlock involving all the threads.

This Option is Correct.

Now Thread 1 executes till line 5 and preempts; Now S=4,

Thread 2 executes till line 5 and preempts; Now S=3,

Thread 3 executes till line 5 and preempts; Now S=2,

Thread 4 executes till line 5 and preempts; Now S=1,

Thread 0 executes till line 5 and preempts; Now S=0 and if any of threads Resumes; they all will perform unsuccessful down operation and all will be blocked no one to wake up the threads. This is a Deadlock situation.

Option 2:The value of the counter is 5 after all the threads successfully complete the execution of parop.

This Option is Correct.

Option 3:The value of the counter is 1 after all the threads successfully complete the execution of parop.

This Option is Correct.

Thread 1 start execution and line 7, it performs the following

load R1, counter;

add R1,#1; //R₁ contains 1

and now it preempts 

Thread 2 start execution and finishes.

Thread 3 start execution and finishes

Thread 4 start execution and finishes

Thread 5 start execution and finishes.

and Now Thread 1 Resumes.

store R1, counter;  // it overwrite counter as 1;

Option 4:The value of the counter is 0 after all the threads successfully complete the execution of parop.

This is incorrect. Counter =0 not possible after all the threads successfully complete, Minimum value possible is 1.

Answer: Option 1

Explanation:

Option 2 and Option 3 are directly eliminated because slot 10 should have exactly 2 keys and in option 2 slot 10 have only one key and in option 3 slot 10 have 3 keys.

Hence Option 2 and Option 3 are rejected.

Consider Option 1: 10, 9, 6, 7, 5, 13

Insert 10 (1010) 

 Insert 9 (1001)

Insert 6 (0110) 

at 10 binary tree will be constructed according to 3^rd least significant bit

Insert 7 (0111)

Insert 5 (0101)

Insert 13 (1101)

now again collision will occur at 01 and according to the 3^rd least significant bit and 4^th least significant bit binary tree will be constructed.

and Above HashTable same as the given Hash table. If you see in Option 4; 1 (0001) is also mentioned which clearly not present in the HashTable as well.

Answer: 1023 to 1023

Explanation:

SimpleFunction(Z , 10 , 2)

x = 2 , n=2 , total = 1

return total = 1023;

Shortcut Trick

If you Observe carefully at each iteration i; the value of total = 2ⁱ⁺¹-1.

So value of total at end of 9^th iteration will be 2⁹⁺¹-1 = 1023

Answer: 50 to 52

Formula:

Efficiency (η ) = \(\frac{{Useful;Time}}{{Total;time}}\)

Explanation:

Propagation Delay = 100 ms

Transmission delay of the packet = \(\frac{{2000}}{{1000000}}\) = 0.002 = 2 ms

Transmission delay of the ack frame = \(\frac{{10}}{{1000000}}\) = 0.00001 = 0.01 ms

∴ 0.5 = \(\frac{w\times 2}{{2 + 100+ 0.01 + 100}}\)       //w=sender window size

0.5 = \(\frac{w\times 2}{202.01}\) 

w = 50.5

Answer:6

Explanation:

we can write g = (b+c) +1 + (b+c)+1

its syntax tree will be

and its DAG will be created by combining all redundant terms.

Hence It contains 6 nodes.

Answer:50 to 50 

Explanation:

According to given pushdown automata

the language accepted is { aⁿb^m |  n>m or |a| > |b| } 

Number of Strings of length 100 accepted= ?

Let's take Assume small length = 10 

Only 5 Strings of length 10 will be accepted

when length = 100

Strings accepted will be a¹⁰⁰ to a⁵¹b⁴⁹; 

a's will be ( 51 , 52 , 53 , ..., 100) Hence total 50 strings.

Explanation:

Let A = \(\left( {\begin{array}{*{20}{c}} 0&1&1&1\ 1&0&1&1\ 1&1&0&1\ 1&1&1&0 \end{array}} \right)\)

\(|A| = \left| {\begin{array}{*{20}{c}} 0&1&1&1\ 1&0&1&1\ 1&1&0&1\ 1&1&1&0 \end{array}} \right|\)

\(|A- λ I| = \left| {\begin{array}{*{20}{c}} - λ&1&1&1\ 1&- λ&1&1\ 1&1&- λ&1\ 1&1&1&- λ \end{array}} \right| = 0\)

R1 → R1 + R2 + R3 + R4

\(\left| {\begin{array}{*{20}{c}} 3- λ&3- λ&3- λ&3- λ\ 1&- λ&1&1\ 1&1&- λ&1\ 1&1&1&- λ \end{array}} \right| = 0\)

\((3- λ)\left| {\begin{array}{*{20}{c}}1&1&1&1\ 1&- λ&1&1\ 1&1&- λ&1\ 1&1&1&- λ \end{array}} \right| = 0\)

R2 → R2 - R1

R3 → R3 - R1

R4 → R4 - R1

\((3- λ)\left| {\begin{array}{*{20}{c}}1&1&1&1\ 0&- λ-1&0&0\ 0&0&- λ-1&0\ 0&0&0&- λ-1 \end{array}} \right| = 0\)

(3- λ)(-λ - 1)³ = 0

λ = 3, -1, -1, -1

∴ The largest value is 3.

Data:

Number of Instructions = n = 100

Number of stages = 5;

Stage delay = 5 ns

Calculation:

Time taken by five stage pipeline processor of singel instruction = T = Max (150, 120, 150, 160,140)  + stages delay

= 160 + 5 = 165 ns

The time required to execute n instructions with pipeline = [k + (n – 1)]T

= (5 + (100 - 1))×165 = 17160 ns

Answer:0.04 to 0.04

Data:

P(H_S) = Probability of Sender sending SIgnal H = 0.1 

P(L_S)  = Probability of Sender sending SIgnal L = 0.9 

P(H_R/H_S) = Probability of receiving H Signal at R Given that Sender has transmitted Signal H. = 0.3

P(HR/LS) = Probability of receiving H Signal at R Given that Sender has transmitted Signal L = 0.8

Similarly 

P(L_R/H_S) = 0.7

P(L_R/L_S) = 0.2 

P(H_S/H_R) = ? 

Calculation:

According to Bayes Theorem : P(HS/HR) = [P(H_S ∩ H_R)] / P(H_R)

P(H_R) = P(H_S)P(HR/HS) + P(L_S)P(HR/LS)      //according to Total Probability Theorem

P(H_R) = 0.1× 0.3 + 0.9× 0.8 = 0.75 

∴ P(HS/HR) = [P(HS ∩ HR)] / P(HR) ≡  [P(HS)P(HR/HS)] / 0.75 

P(HS/HR) = [0.1× 0.3] / 0.75 = 0.03/0.75 = 0.04

Answer: 50 to 50 

Explanation: 

Consider following memory cells

After Executing till 3 instruction we have the following value in Registers

After 4^th instruction, M[R₃] ( M[3000]) will be updated as 50 + 10 = 60 

R₃ => R₃ +1 => 3001

R₁ = 9 Hence it is Nonzero; It will Branch to 1004 (which is instruction 2)

• R₂ = 50

R₂= R₁+R₂ = 59

M[R3] ( M[3001]) will be updated as 59.

R₁  = R₁ - 1 => 9-1 =>8 Hence it is Nonzero; It will Branch to 1004 (which is instruction 1)

If you try to observe the Pattern

Here M[3001] is updated as 59

M[3002] will be updated as 58

M[3003] will be updated as 57

M[3004] will be updated as 56

M[3005] will be updated as 55

M[3006] will be updated as 54

M[3007] will be updated as 53

M[3008] will be updated as 52

M[3009] will be updated as 51

R1 = 0

M[3010] will be updated as 50