GATE CS 2019 Official Paper (Previous Year Paper)

Break down is a phrasal verb which means an explanatory analysis, especially of statistics.

'Break' and 'breaks' are rejected as they do not have 'down' in them, and they do not form a meaningful sentence when filled in the blank.

The sentence is in simple present tense with a singular subject, hence 'breaks down' is the correct answer. 

Hence, 'breaks down' is correct.

The given sentence implies that the search engine’s business model has trust as the main subject.

Revolves around: to have (someone or something) as a main subject or interest.

Plays around: to deal with or treat something in a careless way.

'Plays' is rejected as it does not fit the sentence contextually.

Sinks and bursts are rejected as they are grammatically incorrect with 'around'.

Option 1 is correct.

Let speed of car 1 be 50 km and speed of car 2 be 60 km

Since both are moving in same direction,

relative speed = | 50 - 60 | = 10 km/h

distance = 20 km, time = ?

\(speed = \frac{{distance}}{{time}}\)

\(10 = \frac{{20}}{{time}}\)

∴ time = 2 h

The number of hours it takes for the distance between the two cars to be 20 km is 2 hours.

Let initially, ₹ x be contributed by each friend and ₹ y be gift cost

Therefore, the cost of the gift is \(y = 10x\) (I)

After two friends left, the cost of the gift is not changed and contribution is increased by 150 per friend

Therefore, cost of the gift is \(y = \left( {10 - 2} \right) \times \left( {x + 150} \right)\) (II)

From I and II

\(\begin{array}{l} 10x = 8\left( {x + 150} \right)\ 2x = 1200\ \therefore x = 600 \end{array}\)

\(\begin{array}{l} y = 10x\ y = 10 \times 600\ \therefore y = 6000 \end{array}\)

The cost of the gift was Rs. 6000

Courts employ judges.

Schools employ teachers.

Option 4 is correct.

Let S1: P says “Q committed the crime.”

S2: Q says “S committed the crime.”

S3: R says “I did not do it.”

S4: S says “What Q said about me is false.”

1. Assume that P committed the crime:

S1 is false, S2 is false, S3 is true, S4 is true

Since S3 and S4 are true, R and S says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that P committed the crime is false.

2. Assume that R committed the crime:

S1 is false, S2 is false, S3 is false, S4 is true

Since S4 is true, S says true and only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that R committed the crime is true.

3. Assume that S committed the crime:

S1 is false, S2 is true, S3 is true, S4 is false

Since S2 and S3 are true, Q and R both says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that S committed the crime is false.

4. Assume that Q committed the crime:

S1 is true, S2 is false, S3 is true, S4 is true

Since S1, S3 and S4 are true, P, R and S says true but only one of the statements among S1, S2, S3 and S4 is true. Therefore, assuming that Q committed the crime is false.

Total number of administrators = total number of people in rectangle

Total number of people in rectangle = 10 + 20 + 20 = 50

Total number of people = 70 + 10 + 20 + 20 + 40 = 160

\(percentag{e_{content}} = \frac{{50}}{{160}} \times 100\)

\(percentag{e_{content}} = 31.25\)

the percentage of administrators shall be in the range of 31 to 45

The given sentence means that the High Court refuses the idea of begging to be considered a disease leading to its stigmatization and criminalization and instead claims that begging is a phenomenon taking place due to the 'failure of the state to protect citizens who fall through the social security net'.

Options 1, 3, and 4 are rejected as they contain information which is not provided in the question. 

Option 2 is correct as it is the closest in meaning to the information provided in the question.

Students in respective clubs,

Only Drama Club = 60,

Only Dance Club = 80

Only Maths Club = 30

Drama Club and Dance Club = 38 + 2 = 40

Dance Club and Maths Club = 10 + 2 = 12

Drama Club and Maths Club = 5 + 2 = 7

Drama Club and Dance Club and Maths Club = 2

Total number of students = 60 + 80 + 30 + 38 + 10 + 5 + 2 = 225

Since 75% of students are not included in any of the clubs. Therefore, Venn diagram consists of only 25 percentage of students in the college.

Let x be total number of students in the college

\(x \times \frac{{25}}{{100}} = 225\)

\(\therefore x = 900\)

the total number of students in the college is 900.

Option 1:

Z is staying in the wing located in the north-west direction.

Therefore option 1 is incorrect.

Option 2:

X is in wing closed to Garden

Also, Z is staying in the wing located in the north-west direction.

Therefore option 2 is incorrect.

Option 3:

Z is staying in the wing located in the east direction

Therefore option 3 is incorrect.

Option 4:

X is in wing away from Garden

Y is in wing away from Washroom (WR)

Z is staying in wing located in the south-west direction

Therefore option 4 is correct.

Given:

Cache size = 16 KB = 2¹⁴ B

\({\log _2}{2^{14}}\) = 14 bit

Cache block size = 16 B = 2⁴ B

\({\log _2}{2^{4}}\) = 4 bit (offset)

Physical address = 2³² B = 4 GB //32-bit address

To find:

Number of bits in tag field

Number of bits in Index field

Explanation:

In Fully Associative Mapping:

Physical address:

Physical Address = Tag + block offset

32 = Tag + 4 // use number of bit

Tag = 28 bit

In Fully Associative Mapping, index fields is included in tag field there is no separate field for index in fully Associative Mapping. Hence number of bit in index field is zero

Note:

KB is Kilo Byte (2¹⁰ B)

To enable 5 input AND gate: A₁₅ A₁₄ A̅ ₁₃ A̅ ₁₂ A₁₁

First address: 1100 1000 0000 0000 = C800

Last address: 1100 1111 111 1111 = CFFF

Range of address: C800 to CFFF

28₁₀ = (11100)₂ = (0000 0000 0001 1100)₂

-28₁₀ = 2’s complement of 0000 0000 0001 1100

2’s complement of 0000 0000 0001 1100 = 1111 1111 1110 0100

Note:

Tricks to find: 2’s complement

Start reading the bits from LSB (right hand side) and write it unless first 1 is encounter, leave the first 1 as it is and complement the remaining bits.

Let U = {1, 2}

All Possible subsets of U = {ϕ, {1}, {2}, {1, 2}}

A = (x, X), x ∈ X and X ⊆ U

x can be only {ϕ, 1, 2}

When x = 1

X = (1, {1})

X = {1, {1, 2}}

When x = 2

X = {2, {2}}

X = {2, {1, 2}}

Therefore, total elements in A, |A| = 2 + 2 = 4.

Option 1:

|A| = n × 2^{n - 1} = 2 × 2^{2 - 1} = 4

Option 2:

\(\left| A \right| = \mathop \sum \limits_{k = 1}^n k\left( {\begin{array}{*{20}{c}} n\ k \end{array}} \right) = 1 \times \left( {\begin{array}{*{20}{c}} 2\ 1 \end{array}} \right) + 2 \times \left( {\begin{array}{*{20}{c}} 2\ 2 \end{array}} \right)\)

\(\left| A \right| = 2 + 2 = 4\)

Both the options are correct.

Important Points:

x = ϕ and X = ϕ is not considered since ϕ ∈ ϕ is not true.

Although we cannot generalize just from one example but in general both the cases always hold true for given conditions

1. (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) 

Therefore exclusive OR is associative and hence (x ⊕ y) ⊕ z = x ⊕ (y ⊕ z) 

(x + y) ⊕ z ≠ x ⊕ (y + z) ∴ is it not a valid identity

x + y = x ⊕ y // if xy = 0

(xy + x'y')'

= (x’ + y’).(x+y) // Demorgan’s Law

= x’y +xy’

= x ⊕ y

• Non-deterministic push down automata (NPDA) determines the middle position of the string in the language and start popping until Z(end of stack elements) is meet to tell the acceptance of it .
• As all the string present in the language ww^R accepted by NPDA Hence it is a context free language (CFL).
• From the properties of regular language: Reverse, Suffix, Prefix, Concatenation of Regular language is Regular.
• Every regular language is context free language, but every context free language is not a regular language also ww^R it is not possible to give, DFA, NFA or ϵ - NFA accepting the language. Therefore, it is not Regular language.

No Overflow occurs if two number with opposite signs are added.

Overflow is possible only when two number with same signs are added.

Numbers are in sign-magnitude form

Therefore, X and Y can take any value between - (2^{(n - 1)} - 1) to (2^{(n - 1)} - 1)

Assume n = 4

Therefore, X and Y can take any value between -7 to 7

Z = X - Y

To make X and Y of same sign take X as negative or take Y as negative but do not take both simultaneously. Also take larger number to force overflow

Case I: X = -7 and Y = 7

Z = -7 - 7 = -14 // smallest number possible

Case II: X = 7 and Y = -7

Z = 7 - (-7) = 7 + 7 = 14 // largest number possible

Case I and Case II are extreme overflow conditions

Based on Assumption (4 bit) on sign-magnitude form

Range of n - 1 = 3 bit = -3 to 3

Range of n = 4 bit = -7 to 7

Range of n + 1 = 5 bit = -15 to 15 // capable of handling overflow

Range of n + 2 = 6 bit = -31 to 31 // capable of handling overflow

Minimum number of bit needed = 5 = n + 1

I implies II means ≡ I → II

\({X^{ - 1}} = \frac{{{\rm{Adj}}\left( {\rm{X}} \right)}}{{\left| X \right|}}\)

If |X| ≠ 0 then X^-1

\(\left| X \right| = \frac{{Adj\left( X \right)}}{{{X^{ - 1}}}}\)

If X^-1 then |X| ≠ 0 also |Adj X| = |X|^{n - 1} then |Adj X| ≠ 0

If X^-1 then |X| ≠ 0

I implies II and II implies I

∴ Both I and II are equivalent

Note:

X^-1 means X is invertible

|X| determinant of X

∀ a, b ∈G, aR₁b iff ∃g ∈ G such that a=g⁻¹bg

Reflexive:

aR₁a

a=g⁻¹ag

ga=gg⁻¹ag //Left multiplication by g

gag⁻¹=agg⁻¹ //Right multiplication by g

gag⁻¹=a

a = gag⁻¹

we have aR₁a. So, the relation is reflexive.

Symmetric:

If aR₁b, then ∃g ∈ G such that gag⁻¹ = b then a=g⁻¹bg, so bR₁a. Hence the relation is symmetric.

Transitive:

If aR₁b and bR₁c there are g, h ∈ G such that b=gag⁻¹ and c=hbh⁻¹. Then c = hga(hg)⁻¹ so aR1c.

Hence the relation is transitive.

R1 is an equivalence relation.

∀ a, b ∈ G, aR₂b iff ∃g ∈ G such that a=b⁻¹

Reflexive:

aR₂a,

a=a⁻¹. this may not be true. So, the relation is not reflexive.

R₂ is not an equivalence relation.

R₁ is true and R₂ is false.

Strict 2PL allows only schedules whose precedence graph is acyclic i.e. schedule is Conflict Serial.

In 2PL, transactions do not release exclusive locks until the transaction has committed or aborted i.e. schedule is recoverable.

Time stamp ordering schedule with Thomas write rule generate View serial schedule with BLIND WRITE. Because of BLIND WRITE it won't be Conflict Serial.

Option 3 is correct.

A simple circuit in a graph G that passes through every vertex exactly once is called a Hamiltonian circuit.

In Hamiltonian cycle is a Hamiltonian circuit in which initial and final vertex are same.

In an undirected complete graph on n vertices, there are n permutations are possible to visit every node. But from these permutations, there are: n different places (i.e., nodes) you can start; two (clockwise or anticlockwise) different directions you can travel. So, any one of these n! cycles is in a set of 2n cycles which all contain the same set of edges.

So, there are = \(\frac{{n!}}{{2n}} = \frac{{\left( {n - 1} \right)!}}{2}\) distinct Hamilton cycles.

\(\begin{array}{*{20}{c}} {{\rm{lim}}}\ {x \to 3} \end{array}\frac{{{x^4} - 81}}{{2{x^2} - 5x - 3}}\)

\(\frac{{{3^4} - 81}}{{{{2.3}^2} - 5.3 - 3}} = \frac{0}{0}\)

Applying L Hospital’s rule

\(\begin{array}{*{20}{c}} {{\rm{lim}}}\ {x \to 3} \end{array}\frac{{4{x^3}}}{{4x - 5}}\)

\(\frac{{{{4.3}^3}}}{{4.3 - 5}} = \frac{{108}}{7}\)

Properties of B+ trees:

• B+ tree is height balance tree.
• Non leaf node has pointer to a node (leaf or non-leaf) and not pointer to data record
• Key value in each node is in sorted order.
• Leaf node has pointer to next leaf node.

Structure of non-leaf(internal) node of B+ tree:

Structure of leaf of B+ tree:

Option 2 is not correct.

Regular language L = {x|x = a^2+3k or x = b^10+12k k ≥ 0}.

L = {a², a⁵, a⁸, a¹¹ … ∪ b¹⁰, b²², b³⁴…}

Pumping Lemma:

Let L be an infinite regular language. Then there exists some positive integer m such that any w ϵ L with |w|≥ m can be decomposed as

w = xyz

with |xy|≤ m such that w_i = xyⁱz

is also L for all i = 0, 1, 2, …

Therefore, minimum Pumping Length should be 11, because string with length 10 (i.e., w = b¹⁰) does not repeat anything, but string with length 11 (i.e., w = b¹¹) will repeat states.

Hence option 1, 2, and 3 are eliminated.

Therefore 24 can be the pumping lemma length.

• Simple Mail Transfer Protocol (SMTP) is the standard protocol for sending emails across the Internet.

• IMAP and POP3 are the Internet mail protocols used for retrieving emails.

• MIME allows the users to exchange different kinds of data files in an email: audio, video, images, etc.

• SMPT, POP3 and SMTP, IMAP are the possible correct answer in which only SMTP, POP3 is present in option 2.

From the table it is clear that fork is called 5 times

Formula:

If n times fork is called the number of child processes created = 2ⁿ - 1

Since n = 5 in the given code then number of child processes created = 2⁵ - 1 = 31

A → BD

FOLLOW of B from is first of D

FIRST of D is {d, ϵ}

put ϵ in A → BD

A → B

Now FOLLOW of B is FOLLOW of A

FOLLOW of A is {a}

∴ FOLLOW set of B is {a, d}

a = 3 and d = 1

ad = 31$

Since the given array is sorted

Let given array be 1, 2, 3, 4, 5, 6, 7, …. 25

Probability of choosing each element is \(\frac{1}{25}\)

Worst case for quick sort will only we arise if 1 is chosen or 25 is chosen as pivot element

Assume 1 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (1^st position), this gives rise to worst case in quick sort since the complexity will be O(n²).

Assume 25 is chosen as a pivot element

After first round of partitioning, pivot will be in its same position (last position), this gives rise to worst case, in quick sort since the complexity will be O(n²).

P(X = 1) = \(\frac{1}{25}\) = 0.04

and P(X = 50) = \(\frac{1}{25}\) = 0.04

P(X = 1 or X = 25)

= 0.04 + 0.04

= 0.08

Calculation

3 mod 5 = 3

9 mod 5 = 4

27 mod 5 = 2

81 mod 5 = 1

243 mod 5 = 3

729 mod 5 = 4

2187 mod 5 = 2

6561 mod 5 = 1 and so on

Repeating sequene: {3, 4, 2, 1,}

3⁵¹ mod 5 = (3^{4 × 12 + 3}) mod 5 ≅ 3³ mod 5 = 2

Therefore, the value of 3⁵¹ mod 5 is 2.

Tips and Tricks:

For this expression, aspirant can get the answer directly from the GATE calculator, but it is not always the case. Hence go through the standard procedure each time this question is asked.

MSB as 0:

\(P\left( {MSB = 0} \right) = \frac{7}{{13}}\)

Since events are independent

\(P\left( {MSB = 0;and;MSB = 0} \right) = \frac{7}{{13}} \times \frac{7}{{13}} = 0.28994\)

OR

MSB as 1:

\(P\left( {MSB = 1} \right) = \frac{6}{{13}}\)

Since events are independent

\(P\left( {MSB = 1;and;MSB = 1} \right) = \frac{6}{{13}} \times \frac{6}{{13}} = 0.21301\)

Probability that both numbers has same MSB

\(= P\left( {MSB = 0;and;MSB = 0} \right);or;P\left( {MSB = 1;and;MSB = 1} \right)\)

\(= \frac{7}{{13}} \times \frac{7}{{13}} + \frac{6}{{13}} \times \frac{6}{{13}}\)

= 0.50295

= 0.502 or ≈ 503

Maximum value (Y):

• Process P1 reads the initial value 100 during execution P1 will update the value of D to (100 + 20 = 120) and writes it to memory.
• P2 and P3 read the value 120 from the memory.
• P2 will get executed before P1 and write the value (120 - 50 = 70) to memory. Since P3 is holding D = 120 after its execution D will be equal to (120 + 10 = 130) ∴ Y = 130

Minimum value (X):

• P1, P2 and P3 read the value 100 from the memory
• P1 will execute first, after its execution it will update (D = 100 + 20 = 120)
• After P1, P3 will execute and it will update the value to (D = 100 + 10 = 110)
• Finally, P2 will be execute and D will be equal to 100 - 50 = 50 ∴ X = 50
• Y - X = 130 - 50 = 80

int  *ip = arr + 4 //ip is a integer pointer pointing to 5 element of the array

ip[1] = *(ip + 1xsizeofint) = *(address of 6^th element) = 6

Largest Sum Contiguous subarray is from index 2 to 11

Maximum subsequence sum = S(2, 11) = 6, 3, -1, -2, 13, 4, -9, -1, 4, 12 = 29

Code in C++ to find the maximum contiguous sum of array

#include <iostream>

using namespace std;

int kadane(int arr[], int n)

{

int max_so_far = 0;

int max_ending = 0;

for (int i = 0; i < n; i++)

{

max_ending = max_ending + arr[i];

max_ending = max(max_ending, 0);

max_so_far = max(max_so_far, max_ending);

}

return max_so_far;

}

int main()

{

int arr[] = { −5, −10, 6, 3, −1, −2, 13, 4, −9, −1, 4, 12, −3, 0};

int n = sizeof(arr)/sizeof(arr[0]);

cout << "largest sum of contiguous sub-array is " << kadane(arr, n);

return 0;

}

Let us consider n = 1

Since n > 0 else part gets executed

convert(1/2) = convert(0) // integer division in C

Now**, n = 0**

But base condition is n < 0 again else part gets executed

convert(0/2) = convert(0) // recursive calls until stack memory gets exhausted

This code will never satisfy base condition and will not terminate until stack memory gets exhausted

Since this option is not available choose the best possible option

Option d → “It will not print anything and will not terminate”

It is partially correct since it will not print anything but also gets terminated

Note:

Answer key in GATE 2019: D

Output of the code is 52.

Important Points:

Initialization statement is executed only once.

Incremental statement is executed at the end of every iteration

Subnet mask: 255.255.255.252→ 1111 1111. 1111 1111. 1111 1111. 1111 1100

M’s IP address: 100.10.5.2 →        0110 0100. 0000 1010. 0000 0101. 0000 0010

Subnet Mask & M’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0000

∴ Subnet Id = 100.10.5.0

N’s IP address: 100.10.5.5 →        0110 0100. 0000 1010. 0000 0101. 0000 0101

Subnet Mask & N’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0100

∴ Subnet Id = 100.10.5.4

P’s IP address: 100.10.5.6 →        0110 0100. 0000 1010. 0000 0101. 0000 0110

Subnet Mask & P’s IP address → 0110 0100. 0000 1010. 0000 0101. 0000 0100

∴ Subnet Id = 100.10.5.4

N and P belongs to same subnet 100.10.5.4

Tips and Tricks:

& → bitwise AND

Since Network Mask is 255.255.255.252, not have to check first 3-byte because subnet id will same as first 3 byte of IP address. Only 4^th byte need to bitwise AND with given IP address

• It is mentioned that X (source) and Y (destination) both are in the same subnet. Therefore, local gateways aren’t needed.
• The sender (X) knows its own IP address and MAC address. X also knows the IP address of the target (Y). Find MAC address of Y.
• IP asks ARP to create an ARP request message, filling in X's IP and MAC address and Y's IP address. The destination MAC address is set to all 0’s.
• The message is passed to Data Link layer where it is encapsulated in a frame using MAC address of X as the source address and physical broadcast address (FF:FF:FF:FF:FF:FF)  as the destination address.
• Every host in subnet receives the request message because we have used broadcast MAC address in the destination address. All machines except Y (we have specified Y's IP address in our ARP request message) drop the ARP request message.
• Y replies with an ARP reply message that contains its MAC address. When X receives this message, it gets to know the MAC address of Y.

Important Points:

Host uses its own IP address and network mask to decide if target IP address is in its own network or not.

If it is in its network, it uses ARP to resolve the MAC address.

If target IP address is not in its network, it takes the help of default gateway to resolve MAC address using ARP.

Let X = f₁.f₂

= (0, 2, 5, 8, 14).(2, 3, 6, 8, 14, 15)

= (2, 8, 14)

X ⊕ f₃

= (2, 8, 14) ⊕ (2, 7, 11, 14)

= (2, 8, 14).(2, 7, 11, 14)’ + (2, 8, 14)’.(2, 7, 11, 14)

= (2, 8, 14).(0, 1, 3, 4, 5, 6, 8, 9, 10, 12, 13, 15) + (0, 1, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 15).(2, 7, 11, 14)

= (8) + (7, 11)

=(7, 8, 11)

(f₁.f₂) ⊕ f₃ = ∑ (7, 8, 11)

• {waⁿbⁿw^R |w ϵ {a, b}^*, n ≥ 0} is accepted by a non-deterministic pushdown automaton and hence it is a context-free language
• {ww^R |w ϵ {a, b}^*} is accepted by a non-deterministic pushdown automaton and hence it is context-free language.
• {waⁿw^Rbⁿ|w ϵ {a, b}^*, n ≥ 0} is not accepted by a pushdown automaton and hence it is not a context-free language.
• i = n, 2n, 3n, 4n, etc. forms and arithmetic series. aⁿbⁿ, aⁿb²ⁿ and aⁿb³ⁿ is accepted by a deterministic pushdown automaton and context-free language are closed under union and hence aⁿbⁿ ∪ aⁿb²ⁿ ∪ aⁿb³ⁿ is a context-free language. Hence {aⁿbⁱ |i ϵ {n, 3n, 5n}, n ≥ 0} is a context-free language.

X = (PQRS)

Set of functional dependencies

F = {QR → S, R → P, S → Q}

QR → {Q, R, S, P}

SR → {S, R, P, Q}

QR and SR are keys of Relation schema X

R → P …

part of key (R) → non key(P)

It is partial dependency and hence not in 2^nd normal form and therefore not in BCNF (Given)

X is decomposed into two schemas Y and Z, where Y = (PR) and Z = (QRS)

For Y = (PR)

R → P

Y is in BCNF because binary attribute (R is a key).

For Z = (QRS)

QR → S

S → Q

SR → {R, S, Q}

QR → {R, Q, S}

QR and SR are keys of Relation schema X

Z is not in BCNF because

S → Q and S is not Super key.

∴ statement I is incorrect

Dependency Preserving:

R → P is in Y

QR → S in Z

S → Q is in Z

Hence, it is dependency preserving.

Lossless:

Y ∩ Z = R which is key of Y.

Therefore, it is Lossless

Statement II is correct.

Hence, option 3 is the answer

Memory is word addressable.

1 word = 4 bytes

Virtual Address (VA) = 64 bits

∴ Virtual Address Space (VAS)= 2⁶⁴ words

Physical Address (PA) = 48 bits

∴ Physical Address Space (PAS) = 2⁴⁸ words

Page size (PS) = 8 KB = 2¹¹ words

∴ page offset = 11 bit

∴ number of pages possible = \(\frac{{VAS}}{{PS}} = \frac{{{2^{64}}}}{{{2^{11}}}} = {2^{53}}\)

∴ number of frames possible = \(\frac{{PAS}}{{PS}} = \frac{{{2^{48}}}}{{{2^{11}}}} = {2^{37}}\)

VA = Page number + page offset

Translation Lookaside Buffer (TLB)

Entries in TLB = 128 = 2⁷

If a page number is found in TLB then there will be a hit for all the words (Word addresses) of that Page.

1 - page hit implies 2¹¹ distinct virtual address hits.

So 2⁷page hit implies 2⁷ × 2¹¹=2⁸ × 2¹⁰= 256 × 2¹⁰ virtual address hits.

Therefore, at most 256 × 2¹⁰ distinct virtual addresses can be translated without any TLB miss.

Tips and Tricks:

distinct virtual addresses can be translated without any TLB miss is

the number of entries in TLB × page size

• Every Recursively enumerable language has a Turing Machine, and a set of all Turing Machine's is countable. Therefore, the set of all Recursively enumerable languages is countable.
• There exists a one to one equivalence for all valid C programs and all valid TM encodings. Since the set of all valid TM encodings is countable, it means that the set of all syntactically valid C programs is also countable.
• Set of all languages is uncountable and the set of all Regular Languages is countable. So, the set of all non-regular languages should be uncountable as the union of two countable sets cannot make an uncountable set.

S3 and S4 are uncountable sets.

Important Points:

Every TM can be encoded with 0's and 1's, that is, every TM can be represented by a unique binary number.

Σ = {0,1} then set of all binary strings = Σ^∗. Σ^∗ is countable → Set of all TM's is countable.

∀x [(∀z z|x ⇒ ((z=x) ∨ (z=1))) ⇒ ∃w (w > x) ∧ (∀z z|w ⇒((w=z) V (z=1)))]

Let, X ≡ (∀z z|x ⇒ ((z =x) ∨ (z=1)))

Y ≡ ∃w (w > x)

Z ≡ (∀z z|w ⇒ ((w = z) ∨ (z=1))

∀x [X ⇒ Y ⇒ Z]

X is true: If x is prime number

Y is true: If there exist a w which is greater than x

Z is true. If w is prime

S1 = {1,2,3, ... , 100}

Let x = 97

z = 97

∴ z|x ⇒ (z = 1) ≡ T ⇒ T ≡ T

prime number greater than 97 is 101

But S1 is not included in set. Hence there doesn’t exist w which is greater than x

T ⇒ F.Z ≡ T ⇒ F ≡ F

Therefore, S1 does not satisfy φ

S2. Set of all positive integers satisfy φ

S3. Set of all integers

If x is negative, X ≡ T

F ⇒ Y.Z ≡ T

Also, set of all positive integers satisfy φ

Therefore, option 3 is correct.

Concepts:

Synthesized attributes:

A Synthesized attribute is an attribute of the non-terminal on the left-hand side of a production. Synthesized attributes represent information that is being passed up the parse tree. The attribute can take value only from its children.

S-attributed SDT

If an SDT uses only synthesized attributes, it is called as S-attributed SDT.

Inherited attributes:

An attribute of a nonterminal on the right-hand side of a production is called an inherited attribute. The attribute can take value either from its parent or from its siblings.

L-attributed SDT

If an SDT uses both synthesized attributes and inherited attributes with a restriction that inherited attribute can inherit values from left siblings only, it is called as L-attributed SDT.

In SDT:

D → T L {X₁.type = X₂.type}

L.type = T.type (Inherited attributed )

∴ X₁ = L and X₂ = T

T can be int or float

In SDT:

L → L₁, id {X₃.type = X₄.type}

L₁.type = L.type (Inherited attributed)

∴ X₃ = L₁ and X₄ = L

Hence option 1 is correct.

Total number of unsorted arrays is n and each array contain n distinct element.

Time complexity to find median from an array is O(n).

Since there is ‘n’ such array. Therefore, total time complexity to find medians of all arrays is O(n²)

Store the ‘n’ medians in an array. Find the medians of the array with time complexity of 0(n)

Total Time complexity:

T(n) = O(n²) + O(n) = O(n²)

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.

I. G has a unique minimum spanning tree if no two edges of G have the same weight

This statement is true.

Example:

Graph G(V, E)

G(V, V – 1) → minimum spanning tree

If edge weights are distinct then there exist unique MST.

II. G has a unique minimum spanning tree if, for every cut of G, there is a unique minimum-weight edge crossing the cut

This statement is also true.

Theorem:

If for every cut of a graph there is a unique light edge crossing the cut then the graph has a unique minimum spanning tree, but converse may not be true.

The cut property states that if an edge has the minimum weight among all the edges crossing a particular cut in the graph, then it will be part of any minimum spanning tree. If, for every cut in the graph, there is a unique minimum-weight edge crossing that cut, then there can be only one set of edges that forms the minimum spanning tree. This ensures the uniqueness of the minimum spanning tree in the graph.

Hence, the correct answer is option 3.

All instances of ‘R’ are currently in use. Therefore, available resource = 0

Additional need of process p and q are 0. Therefore, process p and q will release the instances X_p and X_q held by it after its execution.

Available resource = X_p + X_q

To guarantees that no other process apart from p and q can complete execution

Available Resource < minimum of additional resource needed

X_p + X_q < Min {Y_k | 1 ≤ k ≤ n, k ≠ p, k ≠ q}

Correct answer is 

 Key Points

I. The smallest element in a max-heap is always at a leaf node - This statement is generally true. A max-heap is a specialized tree-based data structure that satisfies the heap property. In a max-heap, for any given node I, the value of I is greater than or equal to the values of its children. Therefore, in general, the leaf nodes should contain the smallest elements. However, the smallest element isn't guaranteed to be in a specific leaf node; it could be in any of the leaf nodes.

II. The second largest element in a max-heap is always a child of the root node - This statement is true. In a max heap, the root node is the maximum element, and its children are the next candidates for the maximum values. Therefore, the second largest element must be a child of the root node.

III. A max-heap can be constructed from a binary search tree in Θ(n) time - This statement is true. A binary search tree can be traversed in-order to create a sorted list in Θ(n) time. Then we can build a max-heap from this sorted list in Θ(n) time.

IV. A binary search tree can be constructed from a max-heap in Θ(n) time - This statement is false. Constructing a binary search tree from a heap is more complex and would take O(n log n) time because each insertion into a binary search tree can take up to O(log n) time and there are n such insertions, hence resulting in O(n log n) time complexity.

So, the true statements are I, II, and III.

Additional Information

Max-heap: 

• Smallest element (12) of the max heap is always at the leaf.
• Second largest element (25) in a max heap is always a child of the root node

Binary Search Tree:

INORDER: 14, 15, 18, 20, 22, 23, 25, 30

Traversal time complexity = O(n)

Store the element in an array in reverse order

Filling the array in reverse order. Time complexity = Θ(n)

Total time complexity = Θ(n) + Θ(n) = Θ(n)

MAX heap:

Statement I, II and III are correct

Important Points:

A binary search tree can be constructed from a max heap in Θ(n²) time

Assume that distinct elements are present

Assume that: P4 < P3

Gantt chart:

0           1            2            3           4          4+Z        7+Z

Process Table1:

Average waiting time = 1

\(\frac{{1 + 0 + \left( {1 + z} \right) + 0}}{4} = 1\)

The value of Z is 2.

Assume that: P4 ≥p3

Gantt chart:

0           1            2            3           4            7          7+Z

Process Table2:

Given average waiting time = 1

\(But;\frac{{1 + 0 + 1 + 3}}{4} \ne 1\)

\(\frac{5}{{4}} \ne 1\)

\(∴ p4 > p3;is;not;possible;\)

∴ Z = 2

Data:

In index node of a Unix-like file system,

Direct Block pointer = 12

Single Indirect Block pointer = 1

Double Indirect Block pointer = 1

Disk block address = disk block entries size = 32 bit = 4 bytes

Disk Block size = 4 KB

Calculation:

Number of entries in a block = \(\frac{{4KB}}{{4B}} = 1;K = {2^{10}}\)

File size = (12 direct + 1 single indirect block + 1 double indirect) × block size

File size = (12 × 1 + 1 × 2¹⁰ + 1 × 2¹⁰ × 2¹⁰) × 4 KB

File size = 48 KB + 4 MB + 4 GB

File size = 4.003952 GB ≈ 4 GB

Important Points:

Range given in GATE CS answer key is 4.0 to 4.1

GOTO (I₀, <)

S → < .L >

L → .L,S

L → .S

S → .< L >

L → .id

∴ number of items in the set GOTO (I₀, <) is 5

Concept:

Properties of eigenvalue:

Product of eigenvalues of a matrix(R) = Determinant of a matrix(R)

Calculation:

Determinant of the given matrix is

\(\left| {\begin{array}{*{20}{c}} 1&2&4&8\ 1&3&9&{27}\ 1&4&{16}&{64}\ 1&5&{25}&{125} \end{array}} \right|\)

It is of the form

\(\left| {\begin{array}{*{20}{c}} 1&a&{{a^2}}&{{a^3}}\ 1&b&{{b^2}}&{{b^3}}\ 1&c&{{c^2}}&{{c^3}}\ 1&d&{{d^2}}&{{d^3}} \end{array}} \right|\)

\({\rm{\Delta }} = \left( {a - b} \right)\left( {a - c} \right)\left( {a - d} \right)\left( {b - c} \right)\left( {b - d} \right)\left( {c - d} \right)\)

\(a = 2,;b = 3,;c = 4,;d = 5\)

\(\therefore {\rm{\Delta }} = 12\)

Therefore, the absolute value of the product of eigenvalues is 12.

Tips and Tricks:

Determinant of the given matrix can also be calculated using row or column operation

Data:

1 word = 4 bytes

Cache block size: 8 word

Frequency = 60 MHz clock

\(1;cycle = \frac{1}{{60;M;Hz}} = \frac{{{{10}^{ - 6}}}}{{60}};s\)

In case of a miss,

To accept the starting address = 1 cycle

To fetch all the eight words of the block = 3 cycle

To transmit the words of the requested block = 1 cycle/word

Formula:

\(Bandwidth = \frac{{data;tranfer;}}{{Total;cycles;}}\)

Calculation:

In case of a cache miss, 8 words need to be transmitted

∴ Total cycles = 1 + 3 + 1× 8 = 12 cycle

Data transfer for a block = 8 word = 8 × 4 bytes = 32 bytes 

\(Bandwidth = \frac{{32;byte}}{{12;cycle;}}\)

\(Bandwidth = \frac{{32;byte;}}{{\begin{array}{*{20}{c}} {12 × \frac{{{{10}^{ - 6}}}}{{60}};}\ ; \end{array}sec;}}\)

Bandwidth = 160 × 10⁶ bytes/sec

Important points:

1 M = 10⁶

SI unit of Hz: s^-1

Full binary tree with 8 leaves:

Since any two leaves is chosen uniformly and independently at random

Possible distance: 0, 2, 4, and 6

Leaves with 0 distance:

{(p, p), (q, q), (r, r), (s, s), (t, t), (u, u), (v, v), (w, w)}

 Leaves with 2 distance:

{(p, q), (q, p), (r, s), (s, r), (t, u), (u, t), (v, w), (w, v)}

Leaves with 4 distance:

{(p, r), (r, p), (p, s), (s, p), (q, r), (r, q), (q, s), (s, q),

(t, v), (v, t), (t, w), (w, t), (u, v), (v, u), (u, w), (w, u),}

Leaves with 6 distance:

{(p, t), (t, p), (p, u), (u, p), (p, v), (v, p), (p, w), (w, p),

(q, t), (t, q), (q, u), (u, q), (q, v), (v, q), (q, w), (w, q),

(r, t), (t, r), (r, u), (u, r), (r, v), (v, r), (r, w), (w, r),

(s, t), (t, s), (s, u), (u, s), (s, v), (v, s), (s, w), (w, s)}

Total nodes possible with 0, 2, 4, and 6 distance is 64.

\(E\left( {{x_i}} \right) = \mathop \sum \limits_{i = 1}^4 {x_i}{p_i}\)

\(E\left( {{x_i}} \right) = 0 \times \frac{8}{{64}} + 2 \times \frac{8}{{64}} + 4 \times \frac{{16}}{{64}} + 6 \times \frac{{32}}{{64}}\)

\(E\left( {{x_i}} \right) = \frac{1}{4} + 1 + 3 = 4.25\)

The expected value of the distance between a and b in T is 4.25.

Since Y is uniformly distributed in (1, 6)

\(f\left( Y \right) = \frac{1}{{b - a}},1 < Y < 6\)

Otherwise f(Y) = 0

3x² + 6xY + 3Y + 6

Comparing with

ax² + bx + c = 0

∴ a = 3, b = 6Y, c = 3Y + 6

Also, it has only real roots

b² - 4ac ≥ 0

(6Y)² - 4(3) (3Y + 6) ≥ 0

Y² - Y - 2 ≥ 0

(Y - 2) (Y + 1) ≥ 0

Product of two number (assume a and b) is ≥ 0 if and only if

1. a > 0 and b > 0
2. a < 0 and b < 0
3. a = 0 or b = 0

Condition 1:

Y - 2 > 0 and Y + 1 > 0

Y > 2 and Y > -1

∴ Y > 2

Condition 2:

Y - 2 < 0 and Y + 1 < 0

Y < 2 and Y < -1

∴ Y < -1

Condition 3:

Y - 2 = 0 or Y + 1 = 0

∴ Y = 2 or Y = -1

Value of Y satisfying the condition of real roots falls in the range: [2, 6)

area = Base × height

\(area = \left( {2 - 6} \right) \times \frac{1}{5}\)

∴ area = 0.8

Therefore, the probability that the polynomial 3x² + 6xY + 3Y + 6 has only real roots is 0.8

Tips and Tricks:

From the diagram:

If diagram is divided into 5 different parts (1, 6), then range which satisfy condition that the equation has only has real roots occupy the 4 parts [2, 6) of it.

The probability that the polynomial 3x² + 6xY + 3Y + 6 has only real roots = \(\frac{4}{5} = 0.8\)

Total number of bijective from A → A where A = {1,2 3, 4, 5} is 5! = 120.

The DFA for accepting L will have 5! = 120 states, since we need one state for every possible permutation function on 5 elements.

Concepts:

An Ethernet Switch is a LAN interconnection device which operates at the data link layer (layer 2) of the OSI reference model.

A switch is fundamentally similar to a bridge, but usually supports a larger number of connected LAN segments and has a richer management capability.

Number of machines = 15

In a LAN, Ethernet switches is having 8 port

Diagram:

Therefore, number of switches is 3

Let us assume that A, B, C, and D are the 4 variables.

K- map for given function:

f(A, B, C, D) = BD + B̅ D̅

Implementing the above function by using XOR gates with complements of variables:

\(f\left( {A,;B,;C,;D} \right) = \overline {\overline {B + \bar D} + \overline {\bar B + D} }\)

\(f\left( {A,;B,;C,;D} \right) = \left( {B + \bar D} \right).\left( {\bar B + D} \right)\)

f(A, B, C, D) = BD + B̅ D̅

Therefore, the minimum number of 2-input NOR gates needed to implement the function is 3.

S × P = 5 × 6 = 30 rows

since marks > 84

∴ number of rows = 30 – 5 = 25

Let X ≡ S × P where P > 84

Modified Query:

SELECT S.Student_name, sum(P.Marks)

FROM X GROUP BY S.Student_name;

Final output:

The number of rows returned by the above SQL query is 5.

Therefore, number of times the variable sum will be printed is 5.

integer pointer b points to 5^th element of an static array a

*b = 10 // dereferencing

sum = 0 // initially

Let p and q be two prime number that generated the modulus parameter n in RSA cryptosystem

n = p*q = 3007

φ(n) = φ(pq) = (p - 1)(q - 1) = 2880

p*q - p - q + 1 = 2880

3007 - p - q + 1 = 2880

p + q = 128

p + 3007/p = 128

p² - 128p + 3007 = 0

p = 31 or p = 97

if p = 31 then q = 97 and vice versa

Hence answer is 97

Alternate Method:

n = p*q = 3007

From question it is clear that one prime number is less than 50

Prime number less than are: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47

Now find which prime number will give remainder 0 on division with 3007

3007%31 = 0

3007/31 = 97

Tips to generate prime number:

Prime number is multiple of (6k ± 1) (except 2 and 3) where k is natural number but vice versa is not true

P × R:

\(let~A\equiv {{\pi }_{X}}\left( {{\sigma }_{\left( P.Y=R.Y\wedge ~R.V=V2 \right)}}\left( P\times R \right) \right)\)

A:

Q × R

\(let~B\equiv {{\pi }_{X}}\left( {{\sigma }_{\left( Q.Y~=~R.Y\wedge ~Q.T>2 \right)}}\left( Q\times R \right) \right)\)

B:

\(Let~R\equiv ~{{\pi }_{X}}\left( {{\sigma }_{\left( P.Y=R.Y\wedge ~R.V=V2 \right)}}\left( P\times R \right) \right)-{{\pi }_{X}}\left( {{\sigma }_{\left( Q.Y~=~R.Y\wedge ~Q.T>2 \right)}}\left( Q\times R \right) \right)=A-B~\)

Number of rows = 1