Official Paper

GATE CS 2022 Official Paper (Previous Year Paper)

65 questions · 180 minutes · with answers · free

Attempt as Timed Mock Test

General Aptitude (10 questions)

The _________ is too high for it to be considered _________.

((a))
fair / fare
((b))
faer / fair
((c))
fare / fare
((d))
fare / fair

Show Answer

Answer: ((d))

fare / fair

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.

A function y(x) is defined in the interval [0, 1] on the x-axis as

$\rm y(x) = \left{ \begin{matrix}2 \rm \ if \ 0 \le x < \ \frac{1}{3} \\ 3 \ \rm if \frac{1}{3} \le x < \frac{3}{4} \\ 1 \rm \ if \frac{3}{4} \le x \le 1 \end{matrix} \right.$

Which one of the following is the area under the curve for the interval [0, 1] on the x-axis?

((a))
5/6
((b))
6/5
((c))
13/6
((d))
6/13

Show Answer

Answer: ((c))

13/6

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.

Let r be a root of the equation

x² +2x + 6 = 0.

Then the value of the expression (r + 2)(r + 3)(r + 4)(r + 5) is

((a))
51
((b))
-51
((c))
126
((d))
-126

Show Answer

Answer: ((d))

-126

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

Given below are four statements.

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.

From the given four statements, find the two statements that CAN NOT BE TRUE simultaneously, assuming that there is at least one student in the class.

((a))
Statement 1 and Statement 3
((b))
Statement 1 and Statement 2
((c))
Statement 2 and Statement 4
((d))
Statement 3 and Statement 4

Show Answer

Answer: ((a))

Statement 1 and Statement 3

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.

A palindrome is a word that reads the same forwards and backwards. In a game of words, a player has the following two plates painted with letters.

From the additional plates given in the options, which one of the combinations of additional plates would allow the player to construct a five-letter palindrome. The player should use all the five plates exactly once. The plates can be rotated in their plane.

((a))
((b))
((c))
((d))

Show Answer

Answer: ((b))

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 2nd and 3rd plates) is a not palindrome.

Option 2:

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

Option 3:

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

Option 4:

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

Hence the correct answer is option 2.

Some people believe that “what gets measured, improves”. Some others believe that “what gets measured, gets gamed”. One possible reason for the difference in the beliefs is the work culture in organizations. In organizations with good work culture, metrics help improve outcomes. However, the same metrics are counterproductive in organizations with poor work culture.

Which one of the following is the CORRECT logical inference based on the information in the above passage?

((a))
Metrics are useful in organizations with poor work culture
((b))
Metrics are useful in organizations with good work culture
((c))
Metrics are always counterproductive in organizations with good work culture
((d))
Metrics are never useful in organizations with good work culture

Show Answer

Answer: ((b))

Metrics are useful in organizations with good work culture

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.

In a recently conducted national entrance test, boys constituted 65% of those who appeared for the test. Girls constituted the remaining candidates and they accounted for 60% of the qualified candidates.

Which one of the following is the correct logical inference based on the information provided in the above passage?

((a))
Equal number of boys and girls qualified
((b))
Equal number of boys and girls appeared for the test
((c))
The number of boys who appeared for the test is less than the number of girls who appeared
((d))
The number of boys who qualified the test is less than the number of girls who qualified

Show Answer

Answer: ((d))

The number of boys who qualified the test is less than the number of girls who qualified

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.

A box contains five balls of same size and shape. Three of them are green coloured balls and two of them are orange coloured balls. Balls are drawn from the box one at a time. If a green ball is drawn, it is not replaced. If an orange ball is drawn, it is replaced with another orange ball.

First ball is drawn. What is the probability of getting an orange ball in the next draw?

((a))
1/2
((b))
8/25
((c))
19/50
((d))
23/50

Show Answer

Answer: ((d))

23/50

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 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. Consider the following statements:

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

Which one of the following statements is correct based on the above information?

((a))
P cannot be placed at a corner
((b))
S cannot be placed at a corner
((c))
U cannot be placed at a mid-point
((d))
R cannot be placed at a corner

Show Answer

Answer: ((b))

S cannot be placed at a corner

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.

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.

What is the least number of additional straight ropes needed to create the desired plots? A single rope can pass through three poles that are aligned in a straight line.

((a))
2
((b))
4
((c))
5
((d))
3

Show Answer

Answer: ((d))

The correct answer is option 4.

Concept:

The given data,

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.

Computer Science and Information Technology (55 questions)

Which one of the following statements is TRUE for all positive functions f(n) ?

((a))
f(n²) = θ(f(n)²), when f(n) is a polynomial
((b))
f(n2) = o(f(n)²)
((c))
f(n2) = O(f(n)2) when f(n) is an exponential function
((d))
f(n2) = Ω(f(n)2)

Show Answer

Answer: ((a))

f(n²) = θ(f(n)²), when f(n) is a polynomial

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.

Which one of the following regular expressions correctly represents the language of the finite automaton given below?

((a))
abbab+baaba
((b))
(abb)ab + (baa)ba
((c))
(abb + baa)(a + b*)
((d))
(baa + abb)(ab + ba*)

Show Answer

Answer: ((d))

(baa + abb)(ab + ba*)

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*).

Which one of the following statements is TRUE?

((a))
The LALR(1) parser for a grammar G cannot have reduce-reduce conflict if the LR(1) parser for G does not have reduce-reduce conflict.
((b))
Symbol table is accessed only during the lexical analysis phase
((c))
Data flow analysis is necessary for run-time memory management.
((d))
LR(1) parsing is sufficient for deterministic context-free languages

Show Answer

Answer: ((d))

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

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.

In a relational data model, which one of the following statements is TRUE?

((a))
A relation with only two attributes is always in BCNF.
((b))
If all attributes of a relation are prime attributes, then the relation is in BCNF.
((c))
Every relation has at least one non-prime attribute
((d))
BCNF decompositions preserve functional dependencies.

Show Answer

Answer: ((a))

A relation with only two attributes is always in BCNF.

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.

Consider the problem of reversing a singly linked list. To take an example, given the linked list below,

the reversed linked list should look like

Which one of the following statements is TRUE about the time complexity of algorithms that solve the above problem in O(1) space?

((a))
The best algorithm for the problem takes θ(n) time in the worst case.
((b))
The best algorithm for the problem takes θ(n log n) time in the worst case
((c))
The best algorithm for the problem takes θ(n²) time in the worst case.
((d))
It is not possible to reverse a singly linked list in O(1) space

Show Answer

Answer: ((a))

The best algorithm for the problem takes θ(n) time in the worst case.

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:

Initialize three-pointers prev as NULL, curr as head and next as NULL.
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.

Suppose we are given n keys, m hash table slots, and two simple uniform hash functions h₁ and h₂. Further, suppose our hashing scheme uses h1 for the odd keys and h2 for the even keys. What is the expected number of keys in a slot?

((a))
m/n
((b))
n/m
((c))
2n/m
((d))
n/2m

Show Answer

Answer: ((b))

n/m

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.

Which one of the following facilitates transfer of bulk data from hard disk to main memory with the highest throughput?

((a))
DMA based I/O transfer
((b))
Interrupt driven I/O transfer
((c))
Polling based I/O transfer
((d))
Programmed I/O transfer

Show Answer

Answer: ((a))

DMA based I/O transfer

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.

Let R1 and R2 be two 4-bit registers that store numbers in 2’s complement form. For the operation R1 + R2, which one of the following values of R1 and R2 gives an arithmetic overflow?

((a))
R1 = 1011 and R2 = 1110
((b))
R1 = 1100 and R2 = 1010
((c))
R1 = 0011 and R2 = 0100
((d))
R1 = 1001 and R2 = 1111

Show Answer

Answer: ((b))

R1 = 1100 and R2 = 1010

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.

Consider the following threads, T1, T2, and T3 executing on a single processor, synchronized using three binary semaphore variables, S1, S2, and S3, operated upon using standard wait() and signal(). The threads can be context switched in any order and at any time.

T1	T2	T3
While(true) { Wait(S3); Print(“C”); Signal (S2); }	While(true) { Wait(S1); Print(“B”); Signal (S3); }	While(true) { Wait(S2); Print(“A”); Signal (S1); }

Which initialization of the semaphores would print the sequence BCABCABCA….?

((a))
S₁ = 1; S₂ = 1; S₃ = 1
((b))
S1 = 1; S2 = 1; S3 = 0
((c))
S1 = 1; S2 = 0; S3 = 0
((d))
S1 = 0; S2 = 1; S3 = 1

Show Answer

Answer: ((c))

S1 = 1; S2 = 0; S3 = 0

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:

T1	T2	T3
While(true) { Wait(S3); Print(“C”); Signal (S2); }	While(true) { Wait(S1); Print(“B”); Signal (S3); }	While(true) { Wait(S2); Print(“A”); Signal (S1); }

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.

Consider the following two statements with respect to the matrices A_m×n, B_n×m, C_n×n, and D_n×n

Statement 1: tr(AB) = tr(BA)

Statement 2: tr(CD) = tr(DC)

where tr() represents the trace of a matrix. Which one of the following holds?

((a))
Statement 1 is correct and Statement 2 is wrong
((b))
Statement 1 is wrong and Statement 2 is correct
((c))
Both Statement 1 and Statement 2 are correct
((d))
Both Statement 1 and Statement 2 are wrong

Show Answer

Answer: ((c))

Both Statement 1 and Statement 2 are correct

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.

What is printed by the following ANSI C program?

#include<stdio.h>

int main(int argc, char *argv[])

{

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

int *p = NULL;

p = &x;

*p = 10;

p = &z[1];

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

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

return 0;

}

((a))
1, 10, 11
((b))
1, 10, 14
((c))
10, 14, 11
((d))
10, 10, 14

Show Answer

Answer: ((d))

10, 10, 14

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.

Consider an enterprise network with two Ethernet segments, a web server and a firewall, connected via three routers as shown below.

What is the number of subnets inside the enterprise network?

((a))
3
((b))
12
((c))
6
((d))
8

Show Answer

Answer: ((c))

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.

Which of the following statements is/are TRUE?

((a))
Every subset of a recursively enumerable language is recursive
((b))
If a language L and its complement L are both recursively enumerable, then L must be recursive.
((c))
Complement of a context-free language must be recursive.
((d))
If L₁ and L₂are regular, then L₁ ∩ L₂must be deterministic context-free.

Show Answer

Answer: ((a))

Every subset of a recursively enumerable language is recursive

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.

Let WB and WT be two set associative cache organizations that use LRU algorithm for cache block replacement. WB is a write back cache and WT is a write through cache. Which of the following statements is/are FALSE?

((a))
Each cache block in WB and WT has a dirty bit
((b))
Every write hit in WB leads to a data transfer from cache to main memory
((c))
Eviction of a block from WT will not lead to data transfer from cache to main memory.
((d))
A read miss in WB will never lead to eviction of a dirty block from WB

Show Answer

Answer: ((a))

Each cache block in WB and WT has a dirty bit

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.

Consider the following three relations in a relational database.

Employee(eId, Name), Brand(bId, bName), Own(eId, bId)

Which of the following relational algebra expressions return the set of eIds who own all the brands?

((a))
Π_eld (Πeld,bld (Own)/Π_bld (Brand))
((b))
Πeld (Own) - Πeld ((Πeld (Own) × Π_bld (Brand)) - Πeld,bld (Own))
((c))
Πeld ((Πeld,bld (Own)/Π_bld (Own))
((d))
Πeld ((Πeld (Own) × Πbld (Own)) / Πbld (Brand))

Show Answer

Answer: ((a))

Π_eld (Πeld,bld (Own)/Π_bld (Brand))

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))

Which of the following statements is/are TRUE with respect to deadlocks?

((a))
Circular wait is a necessary condition for the formation of deadlock
((b))
In a system where each resource has more than one instance, a cycle in its wait-for graph indicates the presence of a deadlock.
((c))
If the current allocation of resources to processes leads the system to unsafe state, then deadlock will necessarily occur.
((d))
In the resource-allocation graph of a system, if every edge is an assignment edge, then the system is not in deadlock state.

Show Answer

Answer: ((a))

Circular wait is a necessary condition for the formation of deadlock

Option 1 and option 4 are correct.

Key Points

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

Mutual Exclusion
Hold and Wait
No preemption
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.

Suppose a binary search tree with 1000 distinct elements is also a complete binary tree. The tree is stored using the array representation of binary heap trees. Assuming that the array indices start with 0, the 3^rd largest element of the tree is stored at index

Consider the augmented grammar with {+, *, (, ), id} as the set of terminals.

S' → S

S → S + R|R

R → R*P|P

P → (S) | id

If I₀ is the set of two LR(0) items {[S' → S.], [S → S. + R]}, then goto(closure(I₀), +) contains exactly ______ items.

Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ______

Consider a relation R (A, B, C, D, E) with the following three functional dependencies.

AB → C; BC → D; C → E;

The number of superkeys in the relation R is

The number of arrangements of six identical balls in three identical bins is______.

A cache memory that has a hit rate of 0.8 has an access latency 10 ns and miss penalty 100 ns. An optimization is done on the cache to reduce the miss rate. However, the optimization results in an increase of cache access latency to 15 ns, whereas the miss penalty is not affected. The minimum hit rate (rounded off to two decimal places) needed after the optimization such that it should not increase the average memory access time is _____________.

The value of the following limit is _____________.

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

Consider the resolution of the domain name www.gate.org.in by a DNS resolver. Assume that no resource records are cached anywhere across the DNS servers and that an iterative query mechanism is used in the resolution. The number of DNS query-response pairs involved in completely resolving the domain name is_______.

Which one of the following is the closed form for the generating function of the sequence {a_n}_{n ≥ 0} defined below?

$\rm a_n = \left{ \begin{matrix} \rm n+1 , &\rm n \ is \ odd \\ 1, & \rm otherwise \end{matrix} \right.$

((a))
$\rm \frac{x(1 + x^2)}{(1 - x^2)^2} + \frac{1}{1-x}$
((b))
$\rm \frac{x(3- x^2)}{(1 - x^2)^2} + \frac{1}{1-x}$
((c))
$\rm \frac{2x}{(1 - x^2)^2} + \frac{1}{1-x}$
((d))
$\rm \frac{x}{(1 - x^2)^2} + \frac{1}{1-x}$

Show Answer

Answer: ((a))

$\rm \frac{x(1 + x^2)}{(1 - x^2)^2} + \frac{1}{1-x}$

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}$

Consider a simple undirected unweighted graph with at least three vertices. If A is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of

((a))
A³
((b))
A3 divided by 2
((c))
A3 divided by 3
((d))
A3 divided by 6

Show Answer

Answer: ((d))

A3 divided by 6

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.

Which one of the following statements is FALSE?

((a))
The TLB performs an associative search in parallel on all its valid entries using page number of incoming virtual address.
((b))
If the virtual address of a word given by the 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.
((c))
The memory access time using a given inverted page table is always same for all incoming virtual addresses
((d))
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

Show Answer

Answer: ((c))

The memory access time using a given inverted page table is always same for all incoming virtual addresses

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.

Let R_i(z) and W_i(z) denote read and write operations on a data element z by a transaction T_i, respectively. Consider the schedule S with four transactions.

S: R₄(x)R₂(x)R₃(x)R₁(y)W₁(y)W₂(x)W₃(y)R₄(y)

Which one of the following serial schedules is conflict equivalent to S?

((a))
T₁ → T₃ → T₄ → T₂
((b))
T₁ → T₄ → T₃ → T₂
((c))
T₄ → T₁ → T₃ → T₂
((d))
T₃ → T₁ → T₄ → T₂

Show Answer

Answer: ((a))

T₁ → T₃ → T₄ → T₂

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,

T₁	T₂	T₃	T₄
			R(x)
	R(X)
		R(X)
R(Y)
W(Y)
	W(X)
		W(Y)
			R(Y)

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

Consider a digital display system (DDS) shown in the figure that displays the contents of register X. A 16-bit code word is used to load a word in X, either from S or from R. S is a 1024-word memory segment and R is a 32-word register file. Based on the value of mode bit M, T selects an input word to load in X. P and Q interface with the corresponding bits in the code word to choose the addressed word. Which one of the following represents the functionality of P, Q, and T?

((a))
P is 10 : 1 multiplexer; Q is 5 : 1 multiplexer; T is 2 : 1 multiplexer
((b))
P is 10 : 2¹⁰ decoder; Q is 5 : 2⁵ decoder; T is 2 : 1 encoder
((c))
P is 10 : 2¹⁰ decoder; Q is 5 : 2⁵ decoder; T is 2 : 1 multiplexer
((d))
P is 1 : 10 de-multiplexer; Q is 1 : 5 de-multiplexer; T is 2 : 1 multiplexer

Show Answer

Answer: ((c))

P is 10 : 2¹⁰ decoder; Q is 5 : 2⁵ decoder; T is 2 : 1 multiplexer

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.

Consider three floating-point numbers A, B and C stored in registers R_A, R_B and R_C, respectively as per IEEE-754 single-precision floating point format. The 32-bit content stored in these registers (in hexadecimal form) are as follows.

R_A= 0xC1400000	R_B = 0x42100000	R_C = 0x41400000

Which one of the following is FALSE?

((a))
A + C = 0
((b))
C = A + B
((c))
B = 3C
((d))
(B - C) > 0

Show Answer

Answer: ((b))

C = A + B

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.

Consider four processes P, Q, R, and S scheduled on a CPU as per round-robin algorithm with a time quantum of 4 units. The processes arrive in the order P, Q, R, S, all at time t = 0. There is exactly one context switch from S to Q, exactly one context switch from R to Q, and exactly two context switches from Q to R. There is no context switch from S to P. Switching to a ready process after the termination of another process is also considered a context switch. Which one of the following is NOT possible as CPU burst time (in time units) of these processes?

((a))
P = 4, Q = 10, R = 6, S = 2
((b))
P = 2, Q = 9, R = 5, S = 1
((c))
P = 4, Q = 12, R = 5, S = 4
((d))
P = 3, Q = 7, R = 7, S = 3

Show Answer

Answer: ((d))

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

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.

P	Q	R	S	Q	R	Q
0-4	4-8	8-12	12-6	16-20	20-21	21-25

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.

P	Q	R	S	Q	R	Q
0-2	2-6	6-10	10-11	11-15	15-16	16-17

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.

P	Q	R	S	Q	R	Q
0-4	4-8	8-12	12-14	14-18	18-20	20-22

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.

P	Q	R	S	Q	R
0-3	3-7	7-11	11-14	14-17	17-20

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

What is printed by the following ANSI C program?

#include<stdio.h>

int main(int argc, char *argv[])

{

int a[3][3][3] =

{{1, 2, 3, 4, 5, 6, 7, 8, 9},

{10, 11, 12, 13, 14, 15, 16, 17, 18},

{19, 20, 21, 22, 23, 24, 25, 26, 27}};

int i = 0, j = 0, k = 0;

for(i = 0; i < 3; i++ ){

for(k = 0; k < 3; k++ )

printf("%d ", a[i][j][k]);

printf("\n");

}

return 0;

}

((a))
1 2 3

10 11 12

19 20 21
((b))
1 4 7

10 13 16

19 22 25
((c))
1 2 3

4 5 6

7 8 9
((d))
1 2 3

13 14 15

25 26 27

Show Answer

Answer: ((a))

1 2 3

10 11 12

19 20 21

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

What is printed by the following ANSI C program?

#include<stdio.h>

int main(int argc, char *argv[]){

char a = 'P';

char b = 'x';

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

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

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

printf("%c %c %c\n", c, d, e);

return 0;

}

ASCII encoding for relevant characters is given below

A	B	C	...	Z
65	66	67	...	90

a	b	c	...	z
97	98	99	...	122

*	+	-
42	43	45

((a))
z K S
((b))
122 75 83
((c))
((d))
P x +

Show Answer

Answer: ((a))

z K S

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.

Consider solving the following system of simultaneous equations using LU decomposition

x₁ + x₂ - 2x₃ = 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}$

Which one of the following is the correct combination of values for L₃₂, U₃₃, and x₁ ?

((a))
L₃₂ = 2, U₃₃ = $- \frac{1}{2}$ , x₁ = -1
((b))
L32 = 2, U33 = 2, x1 = -1
((c))
L32 = $- \frac{1}{2}$ , U33 = 2, x1 = 0
((d))
L32 = $- \frac{1}{2}$ , U33 = $- \frac{1}{2}$ , x1 = 0

Show Answer

Answer: ((d))

L32 = $- \frac{1}{2}$ , U33 = $- \frac{1}{2}$ , x1 = 0

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

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.

Which of the following is/are undecidable?

((a))
Given two Turing machines M1 and M2 decide if L(M1) = L(M2).
((b))
Given a Turing machine M , decide if L M( ) is regular.
((c))
Given a Turing machine M , decide if M accepts all strings.
((d))
Given a Turing machine M , decide if M takes more than 1073 steps on every string.

Show Answer

Answer: ((a))

Given two Turing machines M1 and M2 decide if L(M1) = L(M2).

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

S.NO	Properties	FA Regular	PDA DCFL	PDA CFL	LBA CSL	Recursive HTM	REL TM
1	Membership WεL	D	D	D	D	D	UD
2	Finiteness L= finite	D	D	D	UD	UD	UD
3	Equivalence L1=L2	D	D	UD	UD	UD	UD
4	Is L1⊆ L2 Subset Checking	D	UD	UD	UD	UD	UD
5	Emptiness L1=Φ	D	D	D	UD	UD	UD
6	Disjoint Operator is L1∩L2=Φ	D	UD	UD	UD	UD	UD
7	Is L= Σ* Totality	D	UD	UD	UD	UD	UD
8	Is L regular language	D	D	UD	UD	UD	UD
- D = decidable - UD = undecidable

Consider the following languages:

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

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

Note that wR is the reversal of the string w. which of the following is/are TRUE ?

((a))
L1 and L2 are regular.
((b))
L1 and L2 are context-free.
((c))
L1 is regular and L2 is context-free.
((d))
L1 and L2 are context-free but not regular

Show Answer

Answer: ((a))

L1 and L2 are regular.

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.

Consider the following languages:

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

L2 = {anbncm | m, n ≥ 0}

L3 = {ambncn | m, n ≥ 0}

Which of the following statements is/are FALSE?

((a))
L1 is not context-free but L2 and L3 are deterministic context-free.
((b))
Neither L1 nor L2 is context-free.
((c))
L2, L3 and L2 ∩ L3 all are context-free
((d))
Neither L1 nor its complement is context-free.

Show Answer

Answer: ((a))

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

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.

Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE ?

((a))
The edge with the second smallest weight is always part of any minimum spanning tree of G
((b))
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G
((c))
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
((d))
G can have multiple minimum spanning tree

Show Answer

Answer: ((a))

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

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 following simple undirected graph is referred to as the Peterson graph.

Which of the following statements is/are TRUE?

((a))
The chromatic number of the graph is 3.
((b))
The graph has a Hamiltonian path.
((c))
The following graph is isomorphic to the Peterson graph.
((d))
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.)

Show Answer

Answer: ((a))

The chromatic number of the graph is 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.

Consider the following recurrence:

f(1) = 1;

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

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

Then, which of the following statements is/are TRUE?

((a))
f(2n - 1) = 2n - 1
((b))
f(2n) = 1
((c))
f(5.2n) = 2n+1 + 1
((d))
f(2n + 1) = 2n + 1

Show Answer

Answer: ((a))

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

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.

Which of the properties hold for the adjacency matrix A of a simple undirected unweighted graph having n vertices?

((a))
The diagonal entries of A2 are the degrees of the vertices of the graph.
((b))
If the graph is connected, then none of the entries of An-1 + In can be zero.
((c))
If the sum of all the elements of A is at most 2(n - 1), then the graph must be acyclic.
((d))
If there is at least a 1 in each of A’s rows and columns, then the graph must be connected.

Show Answer

Answer: ((a))

The diagonal entries of A2 are the degrees of the vertices of the graph.

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,

Nodes	P	Q	R
P	0	1	0
Q	1	0	1
R	0	1	0

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,

Nodes	P	Q	R
P	0	1	0
Q	1	0	1
R	0	1	0

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,

	1	2	3	4	5
1	0	1	1	0	0
2	1	0	1	0	0
3	1	1	0	0	1
4	1	1	0	0	1
5	0	0	0	1	0

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.

Which of the following is/are the eigenvector(s) for the matrix given below?

$\begin{pmatrix} -9 & -6 & -2 & -4 \\ -8 & -6 & -3 & -1 \\ 20 & 15 & 8 & 5 \\ 32 & 21 & 7 & 12 \end{pmatrix} \space$

((a))
$\begin{pmatrix} -1 \\ 1 \\ 0 \\ 1 \end{pmatrix} \space$
((b))
$\begin{pmatrix} 1 \\ 0 \\ -1 \\ 0 \end{pmatrix} \space$
((c))
$\begin{pmatrix} -1 \\ 0 \\ 2 \\ 2 \end{pmatrix} \space$
((d))
$\begin{pmatrix} 0 \\ 1 \\ -3 \\ 0 \end{pmatrix} \space$

Show Answer

Answer: ((a))

$\begin{pmatrix} -1 \\ 1 \\ 0 \\ 1 \end{pmatrix} \space$

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.

Consider a system with 2 KB direct mapped data cache with a block size of 64 bytes. The system has a physical address space of 64 KB and a word length of 16 bits. During the execution of a program, four data words P, Q, R, and S are accessed in that order 10 times (i.e., PQRSPQRS…). Hence, there are 40 accesses to data cache altogether. Assume that the data cache is initially empty and no other data words are accessed by the program. The addresses of the first bytes of P, Q, R, and S are 0xA248, 0xC28A, 0xCA8A, and 0xA262, respectively. For the execution of the above program, which of the following statements is/are TRUE with respect to the data cache?

((a))
Every access to S is a hit.
((b))
Once P is brought to the cache it is never evicted
((c))
At the end of the execution only R and S reside in the cache
((d))
Every access to R evicts Q from the cache

Show Answer

Answer: ((a))

Every access to S is a hit.

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⁵

16 bit
Tag 5 bit	Number of lines 5 bit	Word Offset 6 bit

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

P	(A248)H	10100 01001 001000	9 th block
Q	(C284)H	11000 01010 000100	10 th block
R	(CA8A)H	11001 01010 001010	10 th block
S	(A262)H	10100 01001 100010	9 th block

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.

Consider routing table of an organization’s router shown below:

Subnet Number	Subnet Mask	Next Hop
12.20.164.0	255.255.252.0	R1
12.20.170.0	255.255.254.0	R2
12.20.168.0	255.255.254.0	Interface 0
12.20.166.0	255.255.254.0	Interface 1
default		R3

Which of the following prefixes in CIDR notation can be collectively used to correctly aggregate all of the subnets in the routing table?

((a))
12.20.164.0/20
((b))
12.20.164.0/22
((c))
12.20.164.0/21
((d))
12.20.168.0/22

Show Answer

Answer: ((a))

12.20.164.0/20

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.

1.	12.20.164.0 12.20.10100100.00000000	255.255.252.0 255.255.11111100.00000000
2.	12.20.170.0 12.20.10101010.00000000	255.255.254.0 255.255.11111110.00000000
3.	12.20.168.0 12.20.10101000.00000000	255.255.254.0 255.255.11111110.00000000
4.	12.20.166.0 12.20.10100110.00000000	255.255.254.0 255.255.11111110.00000000

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.

Consider the relational database with the following four schemas and their respective instances.

Student(sNo, sName, dNo) Dept(dNo, dName)

Course(cNo, cName, dNo) Register(sNo, cNo)

Student
sNo	sName	dNo
S01	James	D01
S02	Rocdy	D01
S03	Jackson	D02
S04	Jane	D01
S05	Milli	D02

Dept
dNo	dName
D01	CSE
D02	EEE

Course
cNo	cName	dNo
C11	DS	D01
C12	OS	D01
C21	DE	D02
C22	PT	D02
C23	CV	D03

Register
sNo	cNo
S01	C11
S01	C12
S02	C11
S03	C21
S03	C22
S03	C23
S04	C11
S04	C12
S05	C11
S05	C21

SQL Query:

SELECT * FROM Student AS S WHERE NOT EXIST

(SELECT cNo FROM Course WHERE dNo = “D01”

EXCEPT

SELECT cNo FROM Register WHERE sNo = S.sNo)

The number of rows returned by the above SQL query is___________.

Consider a network with three routers P, Q, R shown in the figure below. All the links have cost of unity.

The routers exchange distance vector routing information and have converged on the routing tables, after which the link Q−R fails. Assume that P and Q send out routing updates at random times, each at the same average rate. The probability of a routing loop formation (rounded off to one decimal place) between P and Q, leading to count-to-infinity problem, is___________.

Let G (V, E) be a directed graph, where V = {1, 2, 3, 4, 5} is the set of vertices and E is the set of directed edges, as defined by the following adjacency matrix A.

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

A[𝑖][𝑗] = 1 indicates a directed edge from node i to node j. A directed spanning tree of G, rooted at r ∈ V, is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V. The number of such directed spanning trees rooted at vertex 5 is ______

Consider a 100 Mbps link between an earth station (sender) and a satellite (receiver) at an altitude of 2100 km. The signal propagates at a speed of 3 ×10⁸ m/s. The time taken (in milliseconds, rounded off to two decimal places) for the receiver to completely receive a packet of 1000 bytes transmitted by the sender is ______.

Consider the data transfer using TCP over a 1 Gbps link. Assuming that the maximum segment lifetime (MSL) is set to 60 seconds, the minimum number of bits required for the sequence number field of the TCP header, to prevent the sequence number space from wrapping around during the MSL is ______.

A processor X₁ operating at 2 GHz has a standard 5-stage RISC instruction pipeline having a base CPI (cycles per instruction) of one without any pipeline hazards. For a given program P that has 30% branch instructions, control hazards incur 2 cycles stall for every branch. A new version of the processor X₂ operating at same clock frequency has an additional branch predictor unit (BPU) that completely eliminates stalls for correctly predicted branches. There is neither any savings nor any additional stalls for wrong predictions. There are no structural hazards and data hazards for X₁ and X₂. If the BPU has a prediction accuracy of 80%, the speed up (rounded off to two decimal places) obtained by X₂ over X₁ in executing P is ______.

Consider the queues Q₁ containing four elements and Q₂ containing none (shown as the Initial State in the figure). The only operations allowed on these two queues are Enqueue(Q, element) and Dequeue(Q). The minimum number of Enqueue operations on Q₁ required to place the elements of Q₁ in Q₂ in reverse order (shown as the Final State in the figure) without using any additional storage is___________.

Consider two files systems A and B , that use contiguous allocation and linked allocation, respectively. A file of size 100 blocks is already stored in A and also in B. Now, consider inserting a new block in the middle of the file (between 50^th and 51^st block), whose data is already available in the memory. Assume that there are enough free blocks at the end of the file and that the file control blocks are already in memory. Let the number of disk accesses required to insert a block in the middle of the file in A and B are n_A and n_B respectively, then the value of nA + nB is_________.

Consider a demand paging system with four-page frames (initially empty) and LRU page replacement policy. For the following page reference string

7, 2, 7, 3, 2, 5, 3, 4, 6, 7, 7, 1, 5, 6, 1

the page fault rate, defined as the ratio of number of page faults to the number of memory accesses (rounded off to one decimal place) is ______.

Consider the following grammar along with translation rules.

S → S₁ # T {S_1.val*T_.val}

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

T → T₁%R {T_.val = T_1.val ÷ R_.val}

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

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

Here # and % are operators and id is a token that represents an integer and id_•val represents the corresponding integer value. The set of non-terminals is {S, T, R, P} and a subscripted non-terminal indicates an instance of the non-terminal.

Using this translation scheme, the computed value of S_•val for root of the parse tree for the expression 20#10%5#8%2%2 is _____________.

Which of the following statements is/are TRUE for a group G ?

((a))
If for all x, y ∈ G, (xy)2 = x2y2, then G is commutative.
((b))
If for all x ∈ G, x2 = 1, then G is commutative. Here, 1 is the identity element of G.
((c))
If the order of G is 2, then G is commutative.
((d))
If G is commutative, then a subgroup of G need not be commutative

Show Answer

Answer: ((a))

If for all x, y ∈ G, (xy)2 = x2y2, then G is commutative.

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.

Attempt this paper under real exam conditions

Timed interface, section switching, instant scoring, and question-by-question analytics — free.

Start Timed Attempt

Register
sNo	cNo
S01	C11
S01	C12
S02	C11
S03	C21
S03	C22
S03	C23
S04	C11
S04	C12
S05	C11
S05	C21

Register
sNo	cNo
S01	C11
S01	C12
S02	C11
S03	C21
S03	C22
S03	C23
S04	C11
S04	C12
S05	C11
S05	C21

Register
sNo	cNo
S01	C11
S01	C12
S02	C11
S03	C21
S03	C22
S03	C23
S04	C11
S04	C12
S05	C11
S05	C21