GATE CS 2022 Official Paper (Previous Year Paper)

The correct answer is 'fare / fair'.

Key Points

• The given words are homophones i.e. similar sounding words.
• Fare is used to mean 'the money paid for a journey on public transport'.
• For eg.- We should go to Seville, but we cannot afford the airfare.
• Fair is used to mean just or appropriate in the circumstances.
• For eg.- To be fair, this subject poses special problems

The complete sentence will be: The fare is too high for it to be considered fair.

• Hence, option 4 is the correct answer.

Additional Information

• A homophone is a word that is pronounced the same as another word but differs in meaning.
• A homophone may also differ in spelling.  
• For eg.- Rose-rose, Reign-rain, etc.

The correct answer is option 3.

Concept:

The given function y(x) is defined in the interval [0, 1] on the x-axis and y-axis is,

The area of the curve for the interval [0, 1]=  \(2 \times {1 \over 3} +3 \times ({3\over4 }- {1\over 3}) +1 \times (1-{3 \over 4}) \space \space \)

Area= \({2 \over 3} +3 \times ({5 \over 12}) +1 \times ({1 \over 4})\)

Area= \({2 \over 3} +{15 \over 12} +{1 \over 4}\)=

Area= \({8+15+3} \over 12\)

Area=\(26 \over 12 \)

Area= \({13} \over 6\)

Hence the correct answer is 13/6

Alternate Method The function is,

Area = \(\rm \int_0^1 y (x) dx\)

⇒ \(\rm \int_0^{\frac{1}{3}} 2 dx + \int_{\frac{1}{3}}^{\frac{3}{4}} 3 dx + \int_{\frac{3}{4}}^1 1dx \)

⇒ \(2 [x]_0^{\frac{1}{3}} + 3[x]_{\frac{1}{3}}^{\frac{3}{4}} + [x]_{\frac{3}{4}} ^1\)

⇒ \(\frac{2}{3} + 3 \left[ \frac{3}{4} - \frac{1}{3} \right] + \frac{1}{4}\)

⇒ \(\frac{8 + 15 + 3}{12}\)

⇒ \(\frac{26}{12}\)

Area = \(\frac{13}{6}\)

Hence the correct answer is 13/6.

The correct answer is option 4.

Concept:

The value r be the root of the equation x² + 2x + 6 = 0

so it will satisfy the, r²+2r+6 =0 ---------(i)

r2+2r =-6 ---------(ii)

The expression (r + 2)(r + 3)(r + 4)(r + 5)

= (r2+5r+6)(r2+9r+20)

=(r2+2r+6+3r)(r2+2r+6+7r+14)

=(0+3r)(0+7r+14)     From (equ i)

=3r(7r+14)

=21(r²+2r) From (equ ii)

=21(-6)

=-126

Hence the correct answer is -126

The correct answer is option 1.

Concept:

The given four statements are, Now draw the basic diagram for the statement that minimal intersection between the elements.

Statement 1: All students are inquisitive.          

 

Statement 2: Some students are inquisitive.

Statement 3: No student is inquisitive.

Statement 4: Some students are not inquisitive.

Option 1: Statement 1 and Statement 3

False, The given two statements are different we can not combine both or can not say both are true.

We can not draw with these statements because if all children are inquisitive is true then no children are inquisitive is false. This possibility both (i) and (iii) can be false. Assume that some children are inquisitive in that case both (i) and (iii) are false.

Option 2: Statement 1 and Statement 2

True, The given two statements are different we can combine both or can say both are true.

This diagram says Some students are inquisitive and all students are inquisitive. Hence it is true.

Option 3: Statement 2 and Statement 4

True, The given two statements are different we can combine both or can say both are true.

This diagram says some students are inquisitive and some students are not inquisitive. Hence it is true.

Statement 4: Statement 3 and Statement 4

True, The given two statements are different we can combine both or can say both are true.

This diagram says no student is inquisitive and some students are not inquisitive. Hence it is true.

Hence the correct answer is statement 1 and statement 3.

The correct answer is option 2.

Concept:

Palindrome:

A palindrome is a word, number, phrase, or other sequence of characters which reads the same backward as forward, such as madam or racecar.

A word, sentence or a number that reads the same backward or forward.

Ex:

RADAR

MADAM

REFER

12321

Option 1:

D D J (after rotating 2^nd and 3^rd plates) is a not palindrome.

Option 2:

R A R (after rotating 2^nd and 3^rd plates) is a palindrome.

Option 3:

Z E D (after rotating 2^nd and 3^rd plates) is a not palindrome.

Option 4:

I L Y after rotating 2^nd and 3^rd plates) is a not palindrome.

Hence the correct answer is option 2.

The correct answer is 'Metrics are useful in organizations with good work culture'.

Key Points

• Let's refer to the passage:
• 'In organizations with good work culture, metrics help improve outcomes.'
• From the above-mentioned statements, it is evident that the correct logical inference is that 'metrics are useful in organizations with good work culture'.
• Hence, option 2 is the correct answer.

Additional Information

• Metrics: a system or standard of measurement.
• ​For eg.- The levels of branching are arbitrary and no precise metric is applied to the distance between the nodes.
• ​Counterproductive: having the opposite of the desired effect.
• ​​For eg.- Child experts fear the Executive's plans may prove counterproductive.

The correct answer is 'The number of boys who qualified for the test is less than the number of girls who qualified'.

Key Points

• Let's refer to the passage:
• 'Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.'
• From the above-mentioned statement, it is evident that the correct logical inference is that  'the number of boys who qualified for the test is less than the number of girls who qualified' since the percentage of the qualified girls is 60% of the total qualified candidates.
• Hence, option 4 is the correct answer.​

Additional Information

• Constituted refers to combined to form a whole.
• For eg.- There were enough members present to constitute a quorum.

The correct answer is option 4.

Concept:

The given data,

A box contains five balls of the same size and shape. Three of them are green colored balls and two of them are orange-colored balls

G = green

O= Orange

If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball. The first ball is drawn,

The event is,

P(E)= \({3 \over 5} \times {2 \over 4} \times {2 \over 5} \times {2 \over 5}\)

P(E)=\({3 \over 10}+ {4 \over 25}\)

P(E)= \({23 \over 50}\)

Hence the correct answer is 23/50.

The correct answer is option 2.

Concept:

The given data

The corners and mid-points of the sides of a triangle are named using the distinct letters P, Q, R, S, T, and U, but not necessarily in the same order.

• The line joining P and R is parallel to the line joining Q and S.
• P is placed on the side opposite corner T.
• S and U cannot be placed on the same side.

Using the above information we can draw, 

 

S can’t be placed at corners because PR is parallel with QS.

Hence the correct answer is S cannot be placed at a corner.

The correct answer is option 4.

Concept:

The given data, 

A plot of land must be divided between four families. They want their individual plots to be similar in shape, not necessarily equal in area. The land has equally spaced poles, marked as dots in the below figure. Two ropes, R1 and R2, are already present and cannot be moved.

R₃= It is the first additional rope.

R₄= It is the second additional rope.

R₅ = It is the third additional rope

So, using 3 additional ropes. We are able to divide into 4 similar shape plots.

Hence the correct answer is 3.

The correct answer is option 1.

Concept:

Option 1: f(n2) = θ(f(n)2), when f(n) is a polynomial.

True, Theta is an Asymptotic Notation used to represent the asymptotically tight bound on the growth rate of an algorithm's runtime.

If f(n) = Θ(g(n)), then there exists positive constants c1, c2 such that 0 ≤ c1.g(n) ≤ f(n) ≤ c2.g(n)

Explanation:

f(n²) = θ(f(n²)) here f(n) is polynomial

f(n) = n³

f(n2) = (n²)³ = n⁶

f(n2) = (n3)² = n6all are equal.

Option 2: f(n2) = o(f(n)2)

False, The little o notation is one of them. Little o notation is used to describe an upper bound that cannot be tight.

If f(n) = o(g(n)), then there exists positive constants c such that 0 ≤ f(n) < c.g(n)

Explanation:

f(n2) = o(f(n)2) then there is no postive constants exists c

such that 0 ≤  f(n2) < 1.f(n)2)  

Option 3: f(n2) = O(f(n)2) when f(n) is an exponential function. 

 

False, Big-O notation represents the upper bound of the running time of an algorithm.

 

If f(n) = O(g(n)), then there exists positive constants c such that 0 ≤ f(n) ≤ c.g(n)

 

Explanation:

 

If f(n) = O(g(n)), then there no positive constants exists c 

such that 0 ≤ f(n2) ≤ c.f(n2)

 

Option 4: f(n2) = Ω(f(n)2)

 

False, Omega notation represents the lower bound of the running time of an algorithm.

 

If f(n) = Ω(g(n)), then there exists positive constants c such that 0 ≤ c.g(n) ≤ f(n)

 

Explanation:

 

If f(n) = Ω(g(n)), then there no positive constants exists  c

such that 0 ≤ c.f(n2)  ≤ f(n2) 

 

Hence the correct answer is f(n2) = θ(f(n)2), when f(n) is a polynomial.

The correct answer is option 4.

Concept:

Finite Automata:

Finite Automata (FA) is the most basic machine for pattern recognition. The finite automata, also known as the finite state machine, is an abstract machine with five components or tuples. It contains a set of states and rules for transitioning from one state to the next, but it is dependent on the input symbol used.

Explanation:

The given automata accept the strings like, {a, b, ab, ba, abb, aba, baa, bab, abbb, abab, baba, baaa, ...}

Option 1: abbab+baaba

False, The strings like {'a', 'b' } accepted by given automata but the given regular expression can not accept those strings. Hence it is false.

Option 2: (abb)ab + (baa)ba

False, The string "abbbbaa" is accepted by given automata but the given regular expression can not accept the string. Hence it is false.

Option 3:(abb + baa)(a + b)*

False, The given regular expression accepts the empty string like epsilon {Є} but the given automata can not accept that empty string. Hence it is false.

Option 4: (baa + abb)(ab + ba)*

True, The given regular expression accepts the strings  {a, b, ab, ba, abb, aba, baa, bab, abbb, abab, baba, baaa, ...} which are accepted by given automata hence it is true.

Hence the correct answer is (baa + abb)(ab + ba*).

The correct answer is option 4.

Concept:

Option 1: The LALR(1) parser for a grammar G cannot have a reduce-reduce conflict if the LR(1) parser for G does not have a reduce-reduce conflict. 

False, If there is no S-R conflict in LR(1) state, it will never be reflected in the LALR(1) state obtained by combining LR(1) states; but, this merging method may create R-R conflict, and the Grammar will not be LALR (1).

Option 2: Symbol table is accessed only during the lexical analysis phase

False, The information in the symbol table is provided during the lexical and syntax analysis phases, but it is needed in subsequent stages of the compiler (semantic analysis, intermediate code generation, code optimization, and code generation).

Option 3:Data flow analysis is necessary for run-time memory management.

False, Data flow analysis is used in control flow graphs for code optimization. It is the analysis of data flow in a control flow graph, that is, the analysis that determines information about data definition and usage in a program. Optimization can be achieved with the use of this analysis.

Option 4: LR(1) parsing is sufficient for deterministic context-free languages

True, LR(k) grammars (also known as deterministic context-free grammars) allow parsing (string recognition) with deterministic pushdown automata (PDA), they can only define deterministic context-free languages.

Hence the correct answer is LR(1) parsing is sufficient for deterministic context-free languages.

The correct answer is option 1.

Concept:

Option 1: A relation with only two attributes is always in BCNF.

True, Relation with two attributes always in BCNF

Example:

A relation R(XY) and functional dependency are {X→Y} it is in BCNF.

{Y→X} it is in BCNF.

{x→Y, Y→X} it is in BCNF.

Option 2: If all attributes of a relation are prime attributes, then the relation is in BCNF.

False, If all prime attributes then the relation is always in 3NF but may not be in BCNF.

Example:

A relation R(ABCD) and functional dependency are {AB→C, B→D, D→B } it is in 3NF.

Candidate key= AB, AD

AB→C is BCNF

B→D is in 3NF

D→B is in 3NF

Hence the relation is 3NF.

Option 3: Every relation has at least one non-prime attribute.

False, It is not mandatory for at least one non-prime attribute in the Relational database management system table.

Option 4: BCNF decompositions preserve functional dependencies.

False, It is not every relation can decompose into BCNF with dependency preserving. Every non-prime attribute in BCNF should be functionally dependent on one of the schema's super keys. If there is any FD that does not follow this, we must divide it into a new relationship in that case. Now, if any other FD employs the prior FD, the FD will not be preserved in BCNF.

The correct answer is option 1.

Concept:

Single linked list:

A single linked list is a sort of unidirectional linked list that may only be traversed in one way, from head to final node (tail). A node is a name for each element in a linked list. A single node includes data as well as a pointer to the next node, which aids in the list's structure.

Explanation:

The time complexity of reversing a linked list is linear in time i.e O(n) where n is the size of the linked list.

Algorithm:

1. Initialize three-pointers prev as NULL, curr as head and next as NULL.
2. Iterate through the linked list. In loop, do following. 

// Before changing next of current, store next node 

next = curr->next

// Now change next of current This is where actual reversing happens 

curr->next = prev 

// Move prev and curr one step forward 

prev = curr 

curr = next

Analysis:

• Initialize three-pointers prev as NULL, curr as head and next as NULL.
• Iterate through the linked list,
• And check whether there are any nodes in the linked list then move forward to the nodes by changing the nodes allocations.
• Before changing the next of current, store the next node.
• Now change next of current This is where actual reversing happens with curr->next = prev.
• Move prev and curr one step forward with, prev = curr  and curr = next.

So we need to traverse the whole linked list in the given linked list it takes n time to travel all elements in the linked list. So the best algorithm for the problem takes θ(n) time in the worst case. 

Hence the correct answer is the best algorithm for the problem that takes θ(n) time in the worst case.

The correct answer is option 2.

Concept:

Hashing is the method or practice of employing a hash function to map keys and values into a hash table. It is done so that items may be accessed more quickly. The effectiveness of the hash function employed determines the efficiency of mapping.

Explanation:

The given data,

Number of keys = n

Number of slots = m

According to the question, we must determine the number of expected keys in each slot, i.e. how many keys are feasible in each slot.

Analysis:

The performance of hashing can be evaluated under the assumption that each key is equally likely to be hashed to any slot of the table (simple uniform hashing). The average number of keys in a slot will be the total number of events that occur to the number of sample spaces i.e total number of slots.

Expected number of keys in a slot = Number of even keys / Total slots.

Expected number of keys in a slot = n/m.

So, each slot expected key should be n/m.

Hence the correct answer is n/m.

The correct answer is option 1.

Concept:

• CPU time is wasted in programmed I/O. In interrupt-driven I/O, the CPU checks for interrupts at regular intervals and transfers data to memory according to interrupt requirements. However, it does not transport data at the highest possible rate.
• In DMA, a bulk amount of data will be transferred from the secondary memory to the main memory without the involvement of the CPU.
• In polling-based I/O, the I/O device is constantly polled to see if it requires a CPU. As a result, it transfers data to the main memory at a slow rate.
• DMA-based I/O transfer does not use the CPU to transmit data to the main memory, therefore it has the highest throughput.

Hence the correct answer is DMA-based I/O transfer.

The correct answer is option 2.

Concept:

Stored numbers in registers R1 and R2 are in 2's complement form. Register size is 4 bits. The range of numbers in 2's complement form is -8 to +7. If R1 + R2, the result is out of the above range, then it is overflow.

The given data,

Given two four-bit registers R1 and R2.

Option 1: R1 = 1011 and R2 = 1110

False,  

R1      =  1 0 1 1 = -(0101)= -5

• R2   =  1 1 1 0 = -(0010)= -2

---

               1 0 0 1  =           = -7        

Here No overflow occurred, because sign bit is same for (R1 + R2 ).

Option 2: R1 = 1100 and R2 = 1010

True,

R1      =  1 1 0 0 = -(0100)= -4

• R2   =  1 0 1 0 = -(0110)= -6

  --------------------------------------------

              0 1 1 0 =            = -10       

Here Overflow occurred because the sign bit is different for (R1 + R2 ).

Option 3: R1 = 0011 and R2 = 0100

False,

R1      =   0 0 1 1 = +(0011)= +3

• R2   =   0 1 0 0 = +(0100)= +4

  --------------------------------------------

                0 1 1 1                 =   +7       

Here No overflow occurred, because the sign bit is the same for (R1 + R2 ).

Option 4: R1 = 1001 and R2 = 1111

False, 

R1      =   1 0 0 1 = -(0111)  = -7

• R2   =   1 1 1 1 = -(0001) = -1

  --------------------------------------------

                1 0 0 0 =               = -8

Here No overflow occurred, because the sign bit is the same for (R1 + R2 ).

Hence the correct answer is R1 = 1100 and R2 = 1010.

The correct answer is option 3.

Concept:

Semaphores are integer variables that are used to address the critical section problem by combining two atomic procedures for process synchronization: wait and signal.

The terms "wait" and "signal" are defined as follows:

Wait:

The wait operation decrements the value of its argument S if it is positive. If S is negative or zero, then no operation is performed.

wait(S)

{ while (S<=0); S--; }

Signal:

The signal operation increments the value of its argument S.

signal(S)

{ S++; }

Explanation:

Analysis:

• Given threads are T1, T2, and T3, and three binary semaphore variable is used for synchronization S1, S2, and S3.
• In order to get the required output, only semaphore S1 should be initialized to 1, other semaphores should be initialized to 0.
• If we initialize S3 or S2 has 1, then it may start with T3 or T2 So those S2 and S3 are must be zero only.
• The first element in this sequence is ‘B’. It means thread T2 should execute first.
• Thus, at this moment. S1 = 1, S2 = 0, S3 = 0.
• Given sequence need to print, BCABCABCA...

Hence the correct answer is S1 = 1; S2 = 0; S3​ = 0.

The correct answer is option 3.

Concept:

The trace of a matrix is the sum of the diagonal elements of the matrix. 

In this question, property of trace is used that is the trace of the product (AB) = trace of the product (BA)

Statement I:

 tr(A_{m x n} x B_{n x m}) =tr(Bm x n x An x m)

\(\A= {\begin{bmatrix} 1 & 2 & 3\ 4 & 5 & 6 \end{bmatrix} }_{2\times3}, B= {\begin{bmatrix} 1 & 4 \ 2 & 5 \ 3&6 \end{bmatrix}}_{3 \times 2} \tr(AB)= {\begin{bmatrix} 14 & 22 \ 32 & 77 \end{bmatrix} }_{2\times 2} =14+77 =91 \\tr(BA)= {\begin{bmatrix} 17 & 22 & 27 \ 22 & 29 &36 \27 & 36& 45 \end{bmatrix} }_{3\times 3} =17+19+45=91 \)

Hence statement 1 is true.

Statement II:

 tr(An x n x Bn x n) =tr(Bn x n x An x n)

\(\ C= {\begin{bmatrix} 2 & 2 \ 3 & 5 \end{bmatrix} }_{2\times2}, D= {\begin{bmatrix} 1 & 2 \ 3 & 4 \end{bmatrix}}_{2 \times 2} \tr(CD)= {\begin{bmatrix} 8 & 12 \ 18 & 26 \end{bmatrix} }_{2\times 2} =8+26 =34 \\tr(DA)= {\begin{bmatrix} 8 & 12 \ 18 & 26 \end{bmatrix} }_{2\times 2} =26+8=34 \)

Hence statement II is also true.

Hence the correct answer is Both Statement 1 and Statement 2 are correct.

The correct answer is option 4.

Concept:

The given C program is,

Line 0: int x = 1, z[2] = {10, 11};

LIne 1: int *p = NULL;

Line 2: p = &x;

Line 3: *p = 10;

Line 4: p = &z[1];

Line 5: *(&z[0] + 1) += 3;

Line 6: printf("%d, %d, %d\n", x, z[0], z[1]);

Line 5: *(&z[0] + 1) += 3;

=*(&z[0] +1) + = 3

=*(3000+1)+=3

=*(3002)+=3

=11+=3

=14

X=10

Z[0]=10

Z[1]=14

Hence the correct answer is 10, 10, 14.

Option 3 is right

The number of interfaces of routers is the number of subnets. Each interface has a different IP address and each IP address can be stored in a routing table with a different Subnet Mask.

There are 7 interfaces where 1 interface is common between two routers. Hence, there are total of 6 subnets.

Option 2,3,4 are correct.

Solution :

Option 1 : False: Every subset of a recursively enumerable language is NOT recursive.

• Every language is a subset of Σ, and Σ is a recursively enumerable language.
• Now, assume any non-recursive language L and L is a subset of Σ^*, but L is a non-recursive language, So, we can conclude that “Every subset of a recursively enumerable language is NOT recursive".

 

Option 2 : True: Let a language L and its complement L' be a recursively enumerable language. The recursively enumerable language means that L is accepted by some Turing machine M1, and L' is accepted by some Turing machine M2. Now, for a language L, assume any string w∈Σ^*, which runs on M1, M2 in parallel or in an interleaved way, then at least one of M1 or M2 will definitely halt on w. That is:

• If w∈L then M1 will definitely halt on w.
• If w∉L then w∈L', So, M2 will halt on w.
• So, for any string w∈Σ^*, at least one of M1 or M2 will definitely halt, hence, for every string, we can decide whether w belongs to L or w belongs to L'.

 

Option 3 : True: The complement of a CFL may or may not be CFL because the CFLs are not closed under complementation.

• Every CFL is Context-sensitive language (CSL), and CSLs are closed under complementation. So, the complement of CSL is always CSL which means that the complement of a CFL must be recursive.

 

Option 4 : True: The regular languages are closed under the intersection. So any two languages must be closed under intersection and every regular language is CFL. Hence, the intersection is deterministic context-free language.

Option 1,2,4 are correct.

Solution :

Option 1: False : A dirty bit is necessary for WB in order to avoid the redundant writes to the main memory but it is not required in WT as all the changes are reflected after a write operation is done.

Option 2: False : The primary use of WB cache memory is to increase the throughput and for the speed mismatch between main memory and processor.However, when the multiple writes are done for the same cache block, these are not reflected immediately. So, every hit in WB does not necessarily lead to the data transfer from cache  to main memory

Option 3: True : The goal of WT cache is to maintain the consistency overwrite performance while as the cache block is used to reflect the changes to the main memory.

Option 4: False : There are replacement strategies in LRU for dirty and regular blocks which means that a read miss might or might not remove a dirty block.

Option 1 and option 2 are correct.

Concept:

• The "Division operator" in relational algebra return all the entities that are associated with entities of different relation.

 

The result of the query in option 1:

It will display all the eId of relation "Own" which are associated with all the bId of relation "Brand".

The result of the query in option 2: 

At first, the cartesian product is performed between Own(eId) and Brand(bId). Which results in the association of all eId with all bId. 

Now, subtract the Own relation entities from the newly generated relation which contains the cartesian product. This will result in eIds that are not associated with bIds.

Subtracting these resulted eIds from the Own relation to retrieve the eIds that are associated with bId in the Brand relation, which is similar to the option 1 result.

Πeld (Πeld,bld​ (Own)/Πeld​ (Brand)) = Πeld​ (Own) - Πeld​ ((Πeld​ (Own) × Πeld​ (Brand)) - Πeld,bld​ (Own))

Option 1 and option 4 are correct.

Key Points 

There are four necessary conditions that should be hold simultaneously for a deadlock.

1. Mutual Exclusion

2. Hold and Wait

3. No preemption

4. Circular wait.

• For the set of processes {P0,P1,P2,...,Pn},the circular wait indicates that the resource which is requested by the process P0 is held by the process P1, similarly the resource requested by the process P1 is held by the process P2 and so on. Finally, the resource required by the process Pn is held by the process P0. In this situation, the processes will never be able to complete because the resources required will be held by one or other process, thereby causing the deadlock.
• If in a system, a resource has only one instance, then the cycle is the necessary and sufficient condition for deadlock. However, in a multi-instance resource system, a cycle is not a sufficient condition for deadlock because each resource may have more than one instance.
• In an unsafe state, there is no resource allocation method that can help in preventing the deadlock while if the system is in safe state, the resource allocation is done in such a way that all the processes will complete their execution and hence deadlock will never occur.
• The resource allocation graph illustrates the future requirements of resources which is indicated by the request edges. So, if every edge is an assignment edge which means that there are no request edges, which in turn satisfies all the resource requirements and the system will never be in a deadlock state.

The correct answer is 509.

Concept:

A binary search tree (BST) is a binary tree in which each node has a Comparable key (and an associated value) and the key in any node is greater than the keys in all nodes in that node's left subtree and less than the keys in all nodes in that node's right subtree.

Explanation:

The given data,

A binary search tree with 1000 different elements has been provided. The tree is also stored using the binary heap tree's array representation. The indices of an array begin with 0.

The index number of the first node at each level may be determined using (2^h –1), where "h" is the tree's height. Also, the number of nodes at each level may be calculated using (2ⁿ –1), where n is the number of levels.

At 10^th level number of nodes = 2^10-1 = 512.

At height 9, the index number of the first node = 2⁹-1 = 511. Since the total number of nodes is 1000, we need to check the upper level. Because the rightmost number in the binary search tree is maximum.

At 9^th level, no. of nodes = 2^9-1 = 256. At height 8, index no. of first node = 2⁸-1 = 255 .

The index number of the last node in 9 th level, = 255 × 2 = 510

So the third largest value is stored at = 509

Hence the correct answer is 509.

The correct answer is 5.

Concept:

LR(0) parser:

The LR parser is a fast bottom-up syntax analysis approach that can handle a wide range of context-free grammar. This method is also known as LR(0) parsing.

• L stands for the left to right scanning.
• R stands for rightmost derivation in reverse.
• 0 stands for no. of input symbols of lookahead.

Augmented grammar:

If P is a grammar with the starting symbol S, then G' (augmented grammar for G) is a grammar with the starting symbol S' and the productions S->.S'. The goal of this new beginning production is to tell the parser when to cease parsing. The '.'preceding S indicates that the left side of '.'has been read by a compiler and the right side of '.'has yet to be read by a compiler.

Explanation:

LR(0) parser of the below is,

S' → S

S → S + R|R

R → R*P|P

P → (S) | id

Hence the correct answer is 5.

The correct answer is 36.

Concept:

Let us consider vertices = n

The maximum number of possible edges in an undirected graph with ‘n’ vertices and ‘k’ components is = ^n-(k-1)C₂ = ((n-k)(n-k+1)) /2

Explanation:

To get maximum edges, take one vertex each for each complement, except the last component. Now, (K–1) components have 1 vertex each and the last component has n–(K–1) vertices. Make the last component complete i.e. it has

 = n-(k-1)C2 = ((n-k)(n-k+1)) /2

Number of edges (e) =  ((n-k)(n-k+1)) /2

From the given data,

components = 2

vertices =10

Number of edges (e) =  ((10-2)(10-2+1)) /2

Number of edges (e) =  (8 x 9)/ 2 

Number of edges (e) = 36

Hence the correct answer is 36.

The correct answer is 8.

Concept:

The given data,

Given three functional dependencies,

AB→C

BC→D

C→ E

Finding the key of the relation, Compute closure of attribute,

{AB}⁺ =  {A, B, C, D, E}

{BC}⁺ = {B,C,D,E}

{C}⁺ = {CE}

Only one candidate key is possible for given relation = AB

Superkeys of the relation = 2^{Total number attributes in relations - Total number of attributes in each key.}

Superkeys of the relation = 2^5-2

Superkeys of the relation = 2³ = 8 keys

(or)

Number of superkeys in relation R,

Zero attributes combine with the key = {AB}

One attributes combine with the key = {ABC, ABD, ABE}

Two attributes combine with the key = {ABCD, ABCE, ABDE}

Three attributes combine with the key = {ABCDE}

Hence the correct answer is 8.

The correct answer is 7.

Concept:

Given that the item consists of six identical balls, it makes no difference. It makes no difference which things are put together; what matters is how many objects are placed in each container. Furthermore, because the bins are similar, the order of the bins is irrelevant.

So, balls and bins are identical, the possible ways are,

We have three bins,

B1 B2 B3

6    0    0

5    1    0

4    1    1

4    2    0

3    2    1

3    3    0

2    2    2

So total number of ways is 7.

Hence the correct answer is  7.

The correct answer is 0.85.

Concept:

Average Memory Access Time (AMAT):

The "absolute hit rate" is the percentage of all memory accesses that hit in this cache level. The "relative hit rate" is the percentage of memory accesses that failed at all previous levels but succeeded at this one.

The given data,

Cache memory hit rate H_c = 0.8

Access Latency Tc = 10 ns.

Miss penalty = 100 ns.

Optimization increases cache access latency to 15 ns. Miss penalty is not affected.

Memory with optimization Tc = 15 ns

Formula:

Average memory access time Tavg = Tc+ (1-Hc) miss penalty

Calculation:

Average memory access time in first case ,

AMAT = 0.8 * 10 ns + 0.2 * 100 ns = 8 ns + 20 ns = 28 ns

= 28 ns

Cache memory hit rate = ?

T_avg = 28 ns

Average memory access time in the second case,

T_avg = (Tc) + (1-H_c) miss penalty

28 = (15) + (1-H_c) 100 ns

Hc = 85/100

x = 0.85 minimum hit rate (rounded off to two decimal places).

Hence the correct answer is 0.85.

Concept:

L-Hospital Rule: Let f(x) and g(x) be two functions

Suppose that we have one of the following cases,

I.  \(\mathop {\lim }\limits_{{\rm{x}} \to {\rm{a}}} \frac{{{\rm{f}}\left( {\rm{x}} \right)}}{{{\rm{g}}\left( {\rm{x}} \right)}} = \frac{0}{0}\)

II. \(\mathop {\lim }\limits_{{\rm{x}} \to {\rm{a}}} \frac{{{\rm{f}}\left( {\rm{x}} \right)}}{{{\rm{g}}\left( {\rm{x}} \right)}} = \frac{\infty }{\infty }\)

Then we can apply L-Hospital Rule as:

\(\mathop {\lim }\limits_{{\bf{x}} \to {\bf{a}}} \frac{{{\bf{f}}\left( {\bf{x}} \right)}}{{{\bf{g}}\left( {\bf{x}} \right)}} = \mathop {\lim }\limits_{{\bf{x}} \to {\bf{a}}} \frac{{{\bf{f}}'\left( {\bf{x}} \right)}}{{{\bf{g}}'\left( {\bf{x}} \right)}}\)

Calculation:

Given:

Check for the limit existence,

\(\lim_{x \rightarrow 0+} \frac{\sqrt x}{1 - e^{2\sqrt x}}\)

put 0 in the equation = 0/1-1 = 0/0 form so limit is exist. 

Apply L' hospital rule, we get (differentiate numerator and denominator)

\(=\lim_{x \rightarrow 0+} \frac{1\over {2\sqrt x}}{0 - e^{2\sqrt x}.{2 \over {2 \sqrt{x}}}} \= \lim_{x \rightarrow 0+} \frac{1\over2 {\sqrt x}}{ -2 e^{2\sqrt x}.{1 \over {2 \sqrt{x}}}} \)

\(\= \lim_{x \rightarrow 0+}{{ 1} \over -2 e^{2 \sqrt {x}}} \= {{-1}\over 2} \=-0.5 \)

Hence the correct answer is -0.5.

The correct answer is 4.

Concept:

The given domain name, www.gate.org.in Iterative query mechanism is used in the resolution,

The DNS resolver travels to the root server, then forwards to the top-level domain, then forwards to the second level domain, and obtains the IP address from the authoritative DNS server in the iterative query. There are 4-pairs involved in completely resolving the domain name.

The correct answer is option 1.

Concept:

a_n = n+1 if 'n' is odd.

    = 1      otherwise.

For maths formulas is,

Hence the correct answer is \(\rm \frac{x(1 + x^2)}{(1 - x^2)^2} + \frac{1}{1-x}\)

The correct answer is option 4.

Concept:

All pair shortest paths for adjacency matrix = A_{i j} ⁿ.

Represent graph in adjacency matrix format. If adjacency matrix multiply by itself 3 times matrix  = Adjacency matrix x Adjacency matrix x Adjacency matrix

Ai j n = n vertices can walk from i – j.

A [diagonal element] represents the cycle of length 3 with beginning and ending with vertex i.

Trace of A³ =A₁₁³+A₂₂³+A₃₃³+....+A_nn³

Since the cycle has 3 vertices and it is counted for every vertex, we need to divide by 3. To get the three vertex loop for directed graph = (Ai j n)/3.  

For an undirected graph, A-B-C-A is the same as the A-C-B-A cycle. So, 2 possibilities will be formed.

The number of 3-cycle for undirected graph is=  (Ai j n)/3x2.

=  (Ai j n)/6.

Hence the correct answer is A3​ divided by 6.

The correct answer is option 3,

Concept:

Option 1: The TLB performs an associative search in parallel on all its valid entries using the page number of the incoming virtual addresses.

True,  A translation lookaside buffer (TLB) is a memory cache used to speed up access to a user memory address. It is a component of the memory management unit of the chip (MMU). The TLB, also known as an address-translation cache, contains the most recent virtual memory to physical memory translations. TLB perform the parallel search.

Option 2: If the virtual address of a word given by CPU has a TLB hit, but the subsequent search for the word results in a cache miss, then the word will always be present in the main memory.

True, The word will always be present in the main memory if the virtual address of a word provided by the CPU gets a TLB hit but the following search for the word results in a cache miss. TLB hit means word will always present in main memory. 

Option 3: The memory access time using a given inverted page table is always the same for all incoming virtual addresses.

False, Memory access time with an inverted page table is not fast since no indexing is used and there is no equal linear searching. Memory access time using the inverted page table is always not the same. Because there is no indexing applied, we follow no equal linear search.

Option 4: In a system that uses hashed page tables, if two distinct virtual addresses V1 and V2 map to the same value while hashing, then the memory access time of these addresses will not be the same.

True, Virtual address = entry number.

If they map to the same value while hashing, their memory access time of addresses will not same because there is a chance that some elements are present at the end of the linked list. If two distinct virtual addresses map to the same value while hashing, they will be resolved using a linked list, so memory access time will not be the same.

Hence the correct answer is the memory access time using a given inverted page table is always the same for all incoming virtual addresses.

The correct answer is option 1.

Concept:

Conflict-equivalent schedule:

The two schedules S1 and S2 are said to be conflict equivalent if all the conflicts in both S1 and S2 must be the same. 

Test for Conflict-equivalent:

Step 1:

Construct a precedence graph where each transaction represents one vertice. And each conflicting operation represents one edge. i.e If from transaction T_i to T_j then draw an edge from vertices T_i to T_j.

Step 2:

If the precedence graph contains no cycles then the schedule is said to be conflict serializable.

Step 3:

The order of serializability is determined based on the topological sort of the directed graph.

Explanation: 

Given schedule S with four transactions,

 

The order of serializability is determined based on the topological sort of the directed graph. For a Directed Acyclic Graph (DAG), topological sorting is a linear ordering of vertices in which vertex u occurs before v in the ordering for any directed edge u v. If the graph is not a DAG, topological sorting is not feasible.

Serial schedules are conflict equivalent to S: T1 → T3 → T4 → T2 

Hence the correct answer is T1 → T3 → T4 → T2

The correct answer is option 3.

Concept:

Digital Show System:

 As the electronic management of numerical data becomes more common, there is a greater demand for simple systems that can display the data in an easily accessible format. Display devices are components of an electronic representation system that give a visual display of numbers, characters, and symbols in response to electrical input.

​Explanation:

Given digital display system, in which a 16-bit codeword is used.

• S is a 1024-word memory segment. So it needs 10 address lines.  Therefore P must be a decoder, with 10 input lines and 1024 output lines. (10: 2¹⁰ decoder)
• R is a 32-word register file, it needs 5 address lines. Therefore Q must be a decoder, with 5 input lines and 32 output lines. (5: 2⁵ decoder)
• Based on mode bit M, T selects an input word to load X. Therefore T must be 2:1 multiplexer, M is selected input to the multiplexer.

Analysis:

​So, there are 10-inputs required for decoder P, and the output of decoder P is 2¹⁰. Similarly, there are 5 inputs required for decoder Q, and the output of decoder Q is 2⁵. And T is a multiplexer, which takes 2 inputs and gives 1 output.

P=10:2¹⁰ decoder

Q=5:2⁵ decoder

T= 2:1 Multiplexer

Hence the correct answer is P is 10: 210 decoder; Q is 5: 2⁵ decoder; T is 2: 1 multiplexer.

The correct answer is option 2.

Concept:

IEEE single-precision floating-point:

IEEE single-precision floating-point computer numbering format is a binary computing format that takes up 4 bytes (32 bits) of memory. Binary32 is the official name for the 32-bit base 2 formats in IEEE 754-2008. IEEE 754-1985 referred to it as single.

IEEE single-precision format:

Explanation:

The given data,

Decimal value =(-1)^s x 1.M x 2^{Base Exponent -Bias}

Bias value in IEEE single-precision format is 127

R_A = 1100 0001 0100 0000 0000 0000 0000 0000

RA sign= 1

RA Base Exponent =100 0001 0 = 130

R_A Mantisa = 100 0000 0000 0000 0000 0000 = 1.100 0000 0000.....

Decimal value = (-1)¹ x1.1 x2^130-127 =-1.1x2³= -1100 = (-12)₁₀

A=-12

RB = 0100 0010 0001 0000 0000 0000 0000 0000

RA sign= 0

RA Base Exponent =100 0010 0= 132

RA Mantisa = 001 0000 0000 0000 0000 0000 = 1.001 000000.....

Decimal value = (-1)0 x1.001 x2132-127 =+1.001x25= + 100100 = (+36)10

B=+36

RC = 0100 0001 0100 0000 0000 0000 0000 0000

RA sign= 0

RA Base Exponent =100 0001 0= 130

RA Mantisa =100 0000 0000 0000 0000 0000= 1.100 0000.....

Decimal value = (-1)0 x1.1 x2130-127 =+1.1x23= + 1100 = (+12)10

C=+12

Option 1: A + C = 0

True, A+C= -12+12=0

Hence it is true.

Option 2: C = A + B

False, A+B= -12+36=+24

it not equal to C. Hence it is false.

Option 3: B = 3C

True, B=3C 

=3x+12 =36 =B

it equal to B. Hence it is true.

Option 4: (B - C) > 0

True, (B-C) >0

=(36-12)=24>0

Hence it is true.

Hence the correct answer is C = A + B.

The correct answer is option 4.

Concept:

The round-robin algorithm is a preventative algorithm. After a defined interval of time, the CPU is transferred to the next process, which is known as time quantum/time slice. The preempted process gets moved to the end of the queue. The round-robin model is a clock-driven hybrid model.

Explanation:

The given data, Given four processes P, Q, R, and S.

Scheduling algorithm: Round Robin

Time quantum = 4-time units.

All the processes arrive at time t = 0.

• Exactly one context switch from S to Q.
• Exactly one context switch from R to Q.
• Exactly two contexts switch from Q to R.
• No context switch from S to P.
• Switching to a ready process after the termination of another process is also considered a context switch.

Analysis:

Different Gantt charts of different processes,

Option 1: P = 4, Q = 10, R = 6, S = 2

Time quantum = 4-time units.

True,  It is a possibility as the CPU bursts time of these processes and accepts all context switches.

Option 2: P = 2, Q = 9, R = 5, S = 1

Time quantum = 4-time units.

True,  It is a possibility as the CPU bursts time of these processes and accepts all context switches.

Option 3:P = 3, Q = 7, R = 7, S = 3

Time quantum = 4-time units.

True,  It is a possibility as the CPU bursts time of these processes and accepts all context switches.

Option 4:P = 3, Q = 7, R = 7, S = 3

Time quantum = 4-time units.

False, there is no context switching exist from R to Q. Hence it is not a possibility as CPU burst time of these processes.

Hence the correct answer is P = 3, Q = 7, R = 7, S = 3.

The correct answer is option 1.

Concept:

An array is defined as a collection of data items of the same type that are stored in contiguous memory locations. Arrays are derived data types in the C programming language that can store primitive data types such as int, char, double, float, and so on.

In C programming, you can create an array of arrays. These arrays are known as multidimensional arrays.

syntax:

int a[size1][size2][size3];

Total number of elements in array 'a' is= size1 x size2 x size 3

Three-dimensional array:

A three-dimensional array is a multi-dimensional array (array of arrays). A 3D array is made up of 2D arrays. Three subscripts are used to specify it: block size, row size, and column size. More dimensions in an array mean that it can store more data.

Explanation:

  

a[0] 2 Dimension:

a[0][0][0]=1

a[0][0][1]=2

a[0][0][2]=3

a[0][1][0]=4

a[0][1][1]=5

a[0][1][2]=6

a[0][2][0]=7

a[0][2][1]=8

a[0][2][2]=9

a[1] 2 Dimension:

a[1][0][0]=10

a[1][0][1]=11

a[1][0][2]=12

a[1][1][0]=13

a[1][1][1]=14

a[1][1][2]=15

a[1][2][0]=16

a[1][2][1]=17

a[1][2][2]=18

a[2] 2 Dimension:

a[2][0][0]=19

a[2][0][1]=20

a[2][0][2]=21

a[2][1][0]=22

a[2][1][1]=23

a[2][1][2]=24

a[2][2][0]=25

a[2][2][1]=26

a[2][2][2]=27

The for loop has prints:

a[000] = 1 ,a [001] = 2, a[002] = 3, a[100] = 10, a[101] = 11, a[102] = 12, a[200] = 19, a[201] = 20, a[202] = 21

Hence the correct answer is 

1 2 3

10 11 12

19 20 21

The correct answer is option 1.

Concept:

The c snippet is,

Initially char a and b is variable which are initialized.

a='P'

b='x'

Here "a" and "b" has stored those with respect to the ASCII values in binary format.

a=80= (0101 0000)₂

b= 120= (0111 1000)₂

char c = (a & b) + '*';

Here & is a bitwise-and operation so it performs the bitwise-and between char variable "a" and "b".

Bitwise-And:

In C or C++, the & (bitwise AND) operator takes two operands and performs AND on each bit of the two numbers. AND returns 1 only if both bits are 1.

Bitwise & = (80 & 120) + 42

80 = 1010000

120 = 1111000

---

a&b= 1010000 = 80+42=122 = z.

char d = (a | b) - '-';

Here & is a bitwise-or operation so it performs the bitwise-or between char variable "a" and "b".

Bitwise-or:

The | (bitwise OR) in C or C++ takes two numbers as operands and does OR on every bit of two numbers. The result of OR is 1 if any of the two bits is 1

 Bitwise | = (80 | 120) + 45

80 = 1010000

120 = 1111000

---

a | b = 1111000 = 120 - 45 = 75 = K

char e = (a ^ b) + '+';

Here & is a bitwise-xor operation so it performs the bitwise-xor between char variable "a" and "b".

Bitwise-Xor:

The ^ (bitwise XOR) in C or C++ takes two numbers as operands and does XOR on every bit of two numbers. The result of XOR is 1 if the two bits are different.

Bitwise ^= (80 ^ 120) + 43

80 = 1010000

120 =1111000

---

a^b = 0101000 =40+43=83 = S

Hence the correct answer is z K S.

The correct answer is option 4.

Concept:

The given data,

The following system of simultaneous equations using LU decomposition

x1 + x2 - 2x3 = 4

x1 + 3x2 - x3​ = 7

2x1 + x2 - 5x3​ = 7

where L and U are denoted as

\(\rm L = \begin{pmatrix} L_{11} & 0 & 0 \\ L_{21} & L_{22} & 0 \\ L_{31} & L_{32} & L_{33} \end{pmatrix} \), \(\rm U = \begin{pmatrix} U_{11} & U_{12} & U_{13} \\ 0 & U_{22} & U_{23} \\ 0 & 0 & U_{33} \end{pmatrix} \)

Let's take the coefficient matrix,

A= \(\begin{bmatrix} 1 & 1 &-2 \1&3 &-1\ 2&1&-5 \end{bmatrix}\)

Perform row-column operation.

R₂ -> R₂ -R₁

R₃ -> R3 -2R₁ 

\(A= \begin{bmatrix} 1 & 1 &-2 \0&2 & 1\ 0&-1&-1 \end{bmatrix}\) 

R₃-> R₃-(-1/2) R₂

\(A= \begin{bmatrix} 1 & 1 &-2 \0&2 & 1\ 0&0 &{-1\over 2} \end{bmatrix} \ A=L*u \ \begin{bmatrix} 1 & 1 &-2 \1&3 &-1\ 2&1&-5 \end{bmatrix}= \begin{bmatrix} 1 & 1 &0 \1 &1& 0\ 2 &{-1\over 2} &1 \end{bmatrix} \begin{bmatrix} 1 & 1 &-2 \0&2 & 1\ 0&0 &{-1\over 2} \end{bmatrix} \)

U₃₃ = -1/2

L₃₂= -1/2

Hence the correct answer is L32 = \(- \frac{1}{2}\), U33 = \(- \frac{1}{2}\), x1​ = 0.

The correct answer is option 1, option and option 3.

Concept:

Option 1, option 2 and option 3 are all non-trivial properties of recursively enumerable language (recursively enumerable language means are the language of Turing machine) are not proved by Rice's theorem. So all the options are UNDECIDABLE.

Refer to the additional information table.

option 4:Given a Turing machine M, decide if M takes more than 1073 steps on every string.

Turing Machine M decide if language L takes more than 1073 steps. Language L' takes almost 1073 steps, So, it is decidable. Then its complement is also decidable. Hence, L is decidable. A Turing Machine sees only at most the first 1073 symbols of input in its first 1073 steps. Hence whether it stops on the first 1073 steps depends only on the first 1073 symbols of input.

Since the number of strings of length 1073 is finite, it gives a way to decide this. Run the input machine M on all inputs of length 1073 and check whether any of them stops within 1073 steps. If so, reject, otherwise accept.

Hence the correct answer is option 1, option 2 and option 3.

Additional Information

The correct answer is option 1, option 2 and option 3.

Concept:

Given language,

L1 = {anwan | w ∈ {a, b}*}

The regular expression can be written for the language L1.

L1 is regular because by putting n=0,  we create a subset {w | w∈ {a,b}* } which contains all possible strings. So if the subset of L1 is (a + b), then L1= (a + b) which is regular.

L2 = {wxwR | w, x ∈ {a, b}*, |w|, |x| > 0}

The regular expression can be written for the language L2.

L2 is regular because by putting w as "a" and "b" we get a regular expression a(a+b)⁺ a+b(a+b)⁺b, which covers all other string which can be obtained by putting w as "aa", "ab", "ba" and "bb", etc.

So  L₂ = a(a+b)⁺a + b(a+b)⁺ b which is regular.

Now every regular is also context-free.

Hence the correct answer is option 1, option 2 and option 3.

The correct answer is option 2, option 3 and option 4.

Concept:

Given languages,

L1 = {ww | w ∈ {a, b}*}

Language L1 is not accepted by PDA, because we can’t figure out the middle element of the string.

Hence it is not context-free language.

L2 = {anbncm | m, n ≥ 0}

Language L2 is accepted by PDA because each element ‘a’ is pushed in the stack and for each element ‘b’ pop operation is performed, and finally, any number of input symbol ‘c’ is possible.

Hence language L2 is context-free language.

L3 = {ambncn | m, n ≥ 0}

Language L3 is accepted by PDA, because after any number of input elements ‘a’, for element ‘b’ push operation is performed and for element ‘c’ pop operation is performed & stack becomes empty.

Hence, language L3  is context-free language.

Explanation:

Option 1: L1 is not context-free but L2 and L3 are deterministic context-free. 

True, L1 is not context-free and L2 and L3 are clearly DCFLs since they have only one comparison and DPDA can accept both.

Option 2: Neither L1 nor L2 is context-free.

False, L2 is DCFL and every DCFL is a CFL.

L2 - Context-free.

L3 - Context-free.

L2 ∩ L3 = {aⁿbⁿcⁿ or a^mb^mc^m , m,n>= 0}

This language is context sensitive language.

Option 3: L2, L3 and  L2 ∩ L3  all are context-free.

False, 

L2 - Context-free.

L3 - Context-free.

L2 ∩ L3 = {aⁿbⁿcⁿ, n>=0} We can not compare the anbncn  with one single stack. Hence it is not context-free.

Option 4: Neither L1 nor its complement is context-free.

False, L1 - Not context-free.

L₁' Complement of L1 is accepted by a context-free grammar is CFL.

Hence the correct answer is option 2, option 3 and option 4.

The correct answer is option 1, option 2, and option 3.

Concept:

Option 1:The edge with the second smallest weight is always part of any minimum spanning tree of G.

True, Consider the following graph,

 

The Second minimum cost edge is always in the minimum spanning tree because the second minimum does not form a cycle in the minimum spanning tree. 

Option 2: One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G.

True, One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of Graph. One of the third or fourth minimum costs in the minimum spanning tree. If the third cost forms a cycle in the minimum spanning tree then the fourth minimum must be in the minimum spanning tree.

Option 3:Suppose S ⊆ V be such that S ≠ ϕ and S ≠ V. Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G.

True, 

Given a cut (S, V−S) of G, recall that an edge (u,v) ∈ E is said to cross the cut if exactly one of u and v is in S. An edge e = (u,v) is a minimum weight edge crossing the cut (S, V−S) if its weight is the smallest of any edge crossing (S, V − S).  Then e = (u,v) must be included in the minimum spanning trees of G.

Let G = (V, E,w) be a connected undirected weighted graph with distinct edge weights. For any cut (U, V − U) of G, the minimum weight edge that crosses the cut is in the minimum spanning tree MST(G) of G.

Option 4:G can have multiple minimum spanning trees.

False,  G can not have multiple minimum spanning trees when all the edges are distinct.

Hence the correct answer is option 1, option 2, and option 3.

The correct answer is options 1,2 and 3.

Concept:

Option 1:The chromatic number of the graph is 3.

True, the Chromatic number of the Peterson graph is 3. We colour the graph with three colours (B, G, R).

Option 2: The graph has a Hamiltonian path.

True, A Hamilton Path is a path that goes through every vertex of a graph exactly once. A Hamilton Circuit is a Hamilton path that begins and ends at the same vertex. 

The Peterson graph has a Hamiltonian path but not a Hamiltonian cycle.

From above graph,

Hamiltonian path= F-B-A-I-E-D-H-G-J

Option 3:The following graph is isomorphic to the Peterson graph.

True, If the adjacency matrices of two graphs are identical, they are said to be isomorphic or If the respective sub-graphs created by removing certain vertices of one graph and their corresponding images in the other graph are isomorphic, then the two graphs are isomorphic.

The given graph is isomorphic to Peterson's graph.

 

Option 4: The size of the largest independent set of the given graph is 3. (A subset of vertices of a graph form an independent set if no two vertices of the subset are adjacent.)

False, A vertex independent set is a set of vertices that are not adjacent. Maximal vertex independent set is a set in which we cannot add one more vertex to it. So, the largest independent set of the Peterson graph is 4.

Hence the correct answer is options 1,2 and 3.

The correct answer is option 1,2,3.

Concept:

Eliminating options is the best way for solving this question. 

f(2n)= it is an even function.

f(2n+1)= it is an odd function.

f(1)=1

f(2)=f(2*1)=2f(1)-1=2-1=1

f(2n) = 2f(n) - 1, for n ≥ 1; where n=1.

f(2+1)= =f(22+1)=2f(1)+1=3

f(2n + 1) = 2f(n) + 1, for n ≥ 1.  where n=1.

By substutuing n values it become,

f(4) = f(22) = 2f(2)–1 = 21–1=1

f(5) = f(22+1) = 2f(2)+1=21+1=3

f(6) = f(23)=2f(3)–1 = 23–1=5

f(7) = f(2*3+1) = 2f(3)+1=7

f(8) = f(23 ) = f(24) = 2f(4)–1 = 21–1 = 1

f(9) = f(24+1) = 2f(4)+1 = 21+1 = 3

f(10) = f(52) = 2f(5)–1 = 23–1 = 5 

.....f(20) = f(54) = f(102) = 2f(10)–1=2*5–1 = 9

Option 1: f(2n - 1) = 2n - 1

True, 

Computation of f(3),f(5) and f(7) show that f(2ⁿ-1)=2ⁿ-1 is correct.

f(2n-1)=2n-1= f(22-1)=22-1=3 

f(2n-1)=2n-1= f(23-1)=23-1=7  are euqal to 

f(2+1)= =f(22+1)=2f(1)+1=3

 f(6+1)= =f(23+1)=2f(3)+1=7

Option 2: f(2n) = 1

True,

Computation of f(2), f(4) and f(8) show that f(2ⁿ) = 1 is correct.

f(2n) = 1= f(21) = 1

f(2n) = 1= f(22) = 1

f(2n) = 1= f(23) = 1  are euqal to,

f(2)=f(2*1)=2f(1)-1=2-1=1

f(4) = f(22) = 2f(2)–1 = 21–1=1

f(8) = f(2³ ) = f(24) = 2f(4)–1 = 21–1 = 1.

Option 3: f(5.2n) = 2n+1 + 1.

True,

Computation of f(10) and f(20) show that f(5.2n) = 2n+1 + 1.

f(5.2n) = 2n+1 + 1= f(5.21) = 21+1 + 1= 5.

f(5.2n) = 2n+1 + 1= f(5.22) = 21+2 + 1= 9  are euqal to,

f(10) = f(52) = 2f(5)–1 = 23–1 = 5 

f(20) = f(54) = f(102) = 2f(10)–1=2*5–1 = 9.

Option 4: f(2n + 1) = 2n + 1.

False, Computation of f(5) and f(9) show that 

f(2n + 1) = 2n + 1=f(21 + 1) = 21 + 1=3

f(2n + 1) = 2n + 1=f(2² + 1) = 22 + 1=5 it not equal to,

f(5) = f(22+1) = 2f(2)+1=21+1=3

f(9) = f(24+1) = 2f(4)+1 = 21+1 = 3

Hence the correct answer is option 1,2, and 3.

The correct answer is option 1.

Concept:

Option 1: The diagonal entries of A2 are the degrees of the vertices of the graph.

True, Assume the adjacency matrix representation of the undirected graph is "A". A²= A x A

Diagonal elements of A² are the degree of vertices or (A_ij²) represents the degree of node i.

K is adjacency matrix is, 

K²= \(\begin{bmatrix} 0 & 1 & 0\ 1 & 0 & 1\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0\ 1 & 0 & 1\ 0 & 1 & 0 \end{bmatrix} \)

K²= \(\begin{bmatrix} 1 & 0 & 1\ 0 & 2 & 0\ 1 & 0 & 1 \end{bmatrix} \)

Degree sequence of (p,q,r)= (1,2,1)

Diagonal elements= (1,2,1)

Option 2: If the graph is connected, then none of the entries of An-1 + In can be zero.

False, 

Take the following connected graph with n=3,

K is adjacency matrix is, 

K^n-1=K^3-1=K²

K2= \(\begin{bmatrix} 0 & 1 & 0\ 1 & 0 & 1\ 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} 0 & 1 & 0\ 1 & 0 & 1\ 0 & 1 & 0 \end{bmatrix} \)

K^n-1= K²+I₃= \(\begin{bmatrix} 1 & 0 & 1\ 0 & 2 & 0\ 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} 1 & 0 & 0\ 0 & 1 & 0\ 0 & 0 & 1 \end{bmatrix} \)= \(\begin{bmatrix} 2 & 0 & 1\ 0 & 3 & 0\ 1 & 0 & 2 \end{bmatrix} \)

We can see that K^n-1+I_n have some entries as zero.

Option 3:If the sum of all the elements of A is at most 2(n - 1), then the graph must be acyclic.

False, Consider following acyclic graph with n=5

A is  adjacency matrix is,

 

So sum of all elements in A=8

here n=5, So 2(n-1)=2(5-1)=8

Here above graph satisfies the condition of the graph but the above graph is not acyclic.

Option 4: If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

False, Consider following acyclic graph with n=5

Consider the above graph in A all rows and columns have at least A 1 but it disconnected the graph. Hence the given option is false.

Hence the correct answer is the diagonal entries of A2 are the degrees of the vertices of the graph.

The correct answer is option 1, option 3, and option 4.

Concept:

Eigenvector for the matrix,

|A-λI| = \(\begin{bmatrix} -9-λ &-6&-2 &-4 \ -8& -6-λ & -3 &-1\ 20 & 15 & 8-λ &5 \ 32& 21& 7&12-λ \end{bmatrix} \space\)

Use Ax = λx in each options. 

λ = Scalar quantity.

Option 1:

\(\begin{bmatrix} -9 & -6 & -2 & -4 \\ -8 & -6 & -3 & -1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{bmatrix} \space \begin{bmatrix} -1 \\ 1 \\ 0 \\ 1 \end{bmatrix} \space =λ \begin{bmatrix} -1 \\ 1 \\ 0 \\ 1 \end{bmatrix} \space \space \space\)

\(=\begin{bmatrix} -1 \\ 1 \\ 0 \\ 1 \end{bmatrix} =λ \begin{bmatrix} -1 \\ 1 \\ 0 \\ 1 \end{bmatrix} \space \space\)

λ= 1

Option 2:

\(\begin{bmatrix} -9 & -6 & -2 & -4 \\ -8 & -6 & -3 & -1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{bmatrix} \space\begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix} \space\space =λ \begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix} \space \=\begin{bmatrix} -7 \\ -5 \\ 12 \\ 25 \end{bmatrix} \space=λ \begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix} \space\)

No real value of λ.

Option 3:

\(\begin{bmatrix} -9 & -6 & -2 & -4 \\ -8 & -6 & -3 & -1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{bmatrix} \space\begin{bmatrix} -1 \\ 0 \\ 2 \\ 2 \end{bmatrix} \space\space =λ \begin{bmatrix} -1 \\ 0 \\ 2 \\ 2 \end{bmatrix} \space \=\begin{bmatrix} -3 \\ 0 \\ 6 \\ 6 \end{bmatrix} \space=λ \begin{bmatrix} 1 \\ 0 \\ -1 \\ 0 \end{bmatrix} \space\)

λ=3

Option 4:

\(\begin{bmatrix} -9 & -6 & -2 & -4 \\ -8 & -6 & -3 & -1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{bmatrix} \space\begin{bmatrix} 0 \\ 1 \\ -3 \\ 0 \end{bmatrix} \space \space\space =λ \begin{bmatrix} 0 \\ 1 \\ -3 \\ 0 \end{bmatrix} \space \space \=\begin{bmatrix} 0 \\ 3 \\ -9 \\ 0 \end{bmatrix} \space \space=λ \begin{bmatrix} 0 \\ 1 \\ -3 \\ 0 \end{bmatrix} \space \space \)

λ=3

Hence the correct answer is option 1, option 3, and option 4.

The correct answer is option 1, option 2, and option 4.

Concept:

The given data,

Cache Memory Size = 2 KB

Main Memory Size = 64 KB

Block Size = 64 B

Calculation:

Number of Lines =Cache Memory Size / Block Size

Number of Lines = 2K/ 64

Number of Lines = 2¹¹/2⁶

Number of Lines = 2⁵

The addresses of the first bytes of P, Q, R, and S are,

But P&S are from the same memory block (10100).

• Every access of S is hit.
• Once P is brought to the cache it is never evicted.
• Every access to R evicts Q from the cache.

Hence the correct answer is option 1, option 2, and option 4.

The correct answer is option 1, option 3.

Concept:

CIDR notation:

CIDR notation (Classless Inter-Domain Routing) is an alternate method of representing a subnet mask. It is simply a count of the number of network bits (bits that are set to 1) in the subnet mask.

Explanation:

IP prefixes can be aggregated, by merging specific, long prefixes into broader, smaller ones. If filtering is done, we may delete those specific prefixes from the forwarding table and save state information. This is a way to improve routing scalability.

Subnet (2) and (3) can be aggregated.

12.20.101010 10.00000000

12.20.101010 00.00000000

---

12.20.101010 00.00000000 = 12.20.168.0/22

Subnet (1) and (4) can be aggregated.

12.20.101001 00.00000000

12.20.101001 10.00000000

---

12.20.101001 10 .00000000 = 12.20.134.0/22

Hence the correct answer is option 2, option 4.

The correct answer is 2.

Concept:

The given tables are,

Student(SNO, SName, dNo)

Dept(dNo, dName)

Course(CNO, CName, dNo)

Register (SNo, CNo)

Explanation:

Step 1:

In the above case, the first inner query return is independent and return <{C11, C12>. The second inner query is dependent on student relations.

Step 2:

The condition is sNo = S.sNo. So, for sNo = S01, second inner query returns <C11, C12>. And the except operation between two inner queries gives an empty result.

Except operation: R1 EXCEPT R2 = R1 – (R1 ∩ R2)

Now, NOT EXIST returns TRUE, and the outer query gives <S01, James, D01> as output.

Step 3:

When the second inner query is checked for sNo = S02. It return <C11>. And the except operation between two inner queries gives a non-empty result. AND NOT EXISTS gives FALSE result. And outer query doesn’t give any result.

Similarly for sNo = S04, the outer query gives output <S04, jane, D01>.  Hence 2 rows were found.

Hence the correct answer is 2.

The correct answer is 0.5

Concept:

Count-to-infinity problem:

 The routing loop in this Distance Vector Routing (DVR) network causes the Count to Infinity issue. Such Routing Loops typically occur when two routers submit an update at the same time or when an interface fails.

Explanation:

 Given that P and Q are sending routing updates at the same average rate, there are two options in a given time period of sending updates: P transmits before Q or Q sends before P.

When the link between Q and R is broken.

The two options are:

• Q sends the update to P first, then P finds the value of R as ∞ and count-to-infinity will not occur​.

• P sends the update to Q first, then Q found that P has a way to reach R, so it is a count-to-infinity problem.

As Q-R is broken So, R can not send updates to anyone.

From the above two conditions only one condition leads to a count-to-infinity problem and each possibility has an equal probability of occurrence, so the probability is 1/2 = 0.5 for count-to-infinity.

Hence the correct answer is 0.5.

The correct answer is 24.

Concept:

According to the adjacency matrix, the graph will be as follows,

The vertexes,

V={1,2,3,4,5}

A matrix 'A' is given in such a way that,

\(\rm A [i][j] = \left{ \begin{matrix} 1, & \rm 1 \le j \le i \le 5\\ 0, & \ \rm otherwise \end{matrix} \right.\)

The adjacency matrix is,

The graph will be,

To find directed spanning tree of the above graph as per the definition given in question r=5 is given,

• To go to node 4 from node 5= (5,4) = 1 way.
• To go to node 3 from node (5,4) ;(5,3), (4,3) = 2 ways.
• To go to node 2 from node (5, 4, 3) ;(5,2), (4,2), (3,2) = 3 ways.
• To go to node 2 from node (5, 4, 3,2 ) ;(5,1), (4,1), (3,1) (2,1) = 4 ways.

Directed spanning tree rooted at vertex 5 is= 4 × 3 × 2 × 1 = 24

Hence the correct answer is 24.

The correct answer is 7.08.

Concept:

The given data,

Bandwidth B= 100 Mbps.

Distance D= 2100 Km.

Propagation speed S= 3 x 10⁸ m/sec.

Packet size L= 1000 bytes 

Explanation:

Time is taken to receive the packet = Transmission time (T_x) + Propagation time(T_P)

Transmission time T_x= Packet size / Bandwidth = L / B

Propagation time Tp= Distance / Propagation speed = D/S

Analysis:​

Transmission time Tx= 1000 bytes / 100 Mbps

Transmission time = 1000 x 8 bits / 100 x 10⁶ bits/sec

Transmission time = 0.08 Msec.

Propagation time T_p= Distance / Propagation speed = D/S

Propagation time = 2100 Km / 3x 10⁸ m/sec

Propagation time = 2100 x 10³ m / 3x 10⁸ m/sec

Propagation time = 7 x 10^-3 sec

Propagation time =7 msec

Time is taken to receive the packet = 7+0.08

Time is taken to receive the packet =7.08 msec

Hence the correct answer is 7.08 msec.

The correct answer is 33.

Concept:

The given data,

Bandwidth = 1 Gbps =2³⁰/8 = bytes sec

Maximum segment lifetime (MSL) = 60 seconds.

Explanation:

Wrap around time = Total sequence number / Bandwidth.

Wrap around time > Maximum segment lifetime

Total sequence number / Bandwidth > Maximum segment life time.

Suppose, minimum number of bits required for the sequence number field = x. 

\({2^x \over 1 \times {2^{30} \over 8} }>60 \2^x={ {60 \times 2^{30} } \over 8} \ log \space 2^x > log({{60 \times 2^{30}} \over 8})\)

x> log 60 +log 2³⁰ - log 8

Minimum value of x = 30+5.9-3

Minimum value of x = 33.

Hence the correct answer is 33.

The correct answer is 1.42.

Concept:

The given data,

Cycle time (tp ) = 2 GHz = 0.5 nanoseconds.

K = 5,

Explanation:

X1:

Without branch prediction.

CPI = 1 + Number of stalls instruction

CPI = 1 + (0.3) × 2

CPI = 1.6

Average serial instruction execution time = CPI * Cycle time

Average serial instruction execution time = 1.6* 0.5nsec 

Average serial instruction execution time = 0.8 ns.

X2:

If BPU predicted the correct branch then it eliminate stalls but if BPU predicted the wrong branch then BPU does not add any additional stalls but the remaining stalls will be present.

CPI = 1+(0.3 ×0.2 ×2)

CPI =1.12

Average parallel instruction execution time = CPI × Cycle time

Average parallel instruction execution time = 1.12 × 0.5 ns

Average parallel instruction execution time = 0.56 ns.

Speedup:

A speedup is a number that measures the relative performance of two systems processing the same problem.

Speedup = Serial Execution Time / Parallel Execution Time.

Speed up= 0.8 / 0.56

Speed up=1.428

Hence the correct answer is 1.428.

The correct answer is 0**.**

Concept:

A queue is a linear structure in which operations are carried out in a specific order. First in, first out is the order (FIFO). It has two operations enqueue and dequeue. Enqueue is used to insert the element and dequeue is used to delete the element from the queue.

Explanation:

Initially, they haven't mentioned the size of the queue and type of queue(circular queue or normal queue).

So consider that Q1 and Q2 are normal queues and there is no restriction on size.

Step1: Given queues Q1 and Q2. These queues are array manner queues look like,

 

**Step 2:**Traverse head of Q2 at the end of queue so Queue format becomes.

Step 3: Now perform the dequeue operation in Q1 at the head position and perform enqueue operation in Q2 at the head position.

• Dequeue(Q1)
• Enqueue(Q2,1)

Step 4: Perform the dequeue operation in Q1 at the head position and perform enqueue operation in Q2 at the head position. Performs the same operation for all elements in Q1.

• Dequeue(Q1)
• Enqueue(Q2,2)

Step 5:

• Dequeue(Q1)
• Enqueue(Q2,3)

Step 6:

• Dequeue(Q1)
• Enqueue(Q2,3)

 

Thus, there are zero enqueue operations performed on queue Q1.

The minimum number of enqueue operations are 0.

Hence the correct answer is 0.

The correct answer is 153.

Concept:

Contiguous allocation:

Contiguous allocation occurs when the blocks are allocated to the file in such a way that all of the file's logical blocks are assigned to the same physical block on the memory.

For contiguous allocation,

we have 100 blocks, in contiguous allocation first, we push the 100^th block to 101 th block (we need two access), then we push the 99 th block to the 100 th block (we need two access again) and so on up to 51 th block. Now, 51 block is empty, then we push new block to 51 position list need one access).

So, Total access are= 50 read operations+ 50 write operations+1 operation to write the newly inserted block.

Total access are=101 operations (n_A)

Linked allocation:

In this scheme, each file is a linked list of disc blocks that do not have to be contiguous. Disk blocks can be placed anywhere on the disc. The directory entry includes a reference to the beginning and end of the file block. Each block carries a reference to the next block occupied by the file.

For linked allocation,

we need to access the block from 1 to 50, new block access that should insert between 50 and 51 blocks, and access 51 blocks. So, the total access is 52.

Total access are= 50 read operations+ 1 operation delete next pointer of 50 th element +1 operation to connect it to the 51 th element.

Total access are=52 operations (nB)

Total operations are required= n_A+ n_B

Total operations are required= 101+52

Total operations are required= 153.

Hence the correct answer is 153.

The correct answer is 0.6

Concept:

Least Recently Used page replacement:

The Least Recently Used page replacement method tracks page consumption over a short time period. It operates on the premise that the pages that have been widely utilized in the past are likely to be heavily used in the future as well.

Explanation:

There are four-page frames are given and an LRU page replacement policy is used.

The given page size= 4,

The given page reference string is =  7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1

Number of Page faults = 9

Number of Page hits = 6

Number of memory access = 15

Page fault rate = Number of page faults / Number of memory access

Page fault rate = 9/15

Page fault rate = 0.6

Hence the correct answer is 0.6.

The correct answer is 80.

Concept:

The given grammar along with translation rules is,

S → S1 # T         {S1.val*T.val}

S → T                 {S.val = T.val}

T → T1%R          {T.val = T1.val ÷ R.val}

T → R                 {T.val = R.val}

R → id                 {R.val = id.val}

The given string is=  20#10%5#8%2%2

Rule 1:

In the given SDT, % has more precedence than # and % because it is away from starting symbol.

Rule 2:

Both % and * are left-associative because the left non-terminal is present left most on the right side grammar.

Explanation:

The given string is=  20#10%5#8%2%2

The given string is=  20x10÷5 x 8÷2÷2

The given string is= 20 x2x4÷2

The given string is= 20 x2x2

The given string is= 40 x2

The given string is= 80

Hence the correct answer is 80.

The correct answer is option 1, option 2, and option 3.

Concept:

Option 1: If for all x, y ∈ G, (XY)2 = X2Y2, then G is commutative. 

True, 

(XY)2 =X2Y2

XY XY=XX YY 

Take X-1 and Y-1 on both side.

X-1 XY XY Y-1=X-1 XX YY Y-1

YX=XY

∀X, Y ∈ G, YX=XY, Here G is commutative.

Option 2: If for all x ∈ G, x2 = 1, then G is commutative. Here, 1 is the identity element of G.

True, ∀ x ∈ G, x2 =1

xx=q

x-1xx= x-1

x=x-1

If every element has its own inverse in a graph, then the graph is commutative.

Option 3: If the order of G is 2, then G is commutative.

True, Every group of prime order is commutative so of O(G)=2, the group 'G' is commutative. If the Group order is a prime number, then it is a cyclic group. And we know that every Cyclic group is an abelian group.

Alternatively, We can think like this, Given that the Order of Group G is 2, one element is the Identity element, So another element x is inverse to itself. By Option B, G is commutative.

Option 4: If G is commutative, then a subgroup of G need not be commutative.

False, If group G is commutative, then a subgroup of G need not be commutative.

Theorem:  Every subgroup of an abelian group has to be abelian. 

Proof: Let G be an abelian group, and suppose that H≤G. 

Now we have to check that,  for any a,b∈H, Do we have ab=ba ??

Since we have: a,b∈H ⊆ G, So a,b are elements of G and since G is abelian, So, ab=ba. Therefore, H is abelian as well.

(or)

If G is commutative then the subgroup is G is also commutative. Let H is the subgroup of group commutative group 'G'.

∀a,b∈ H, we have a,b ∈ G and ab=ba ( ∵  'G' is commutative)

∴ H is commutative.