GATE CS 2017 Official Paper: Shift 2 (Previous Year Paper)

The correct answer is option 4)

1. Aversion - a strong dislike or disinclination towards something**;**  DISLIKE -  to feel distaste for or hostility towards something.
2. Luminous - giving off light; bright or shining;  Radiant - sending out light; shining or glowing brightly.
3. Plunder - steal (goods), typically using force and in a time of disorder;  Loot - steal (goods) in a war, riot, etc.
4. Yielding - giving a product or generating a financial return of a specified amount;  Resistant - offering resistance to something or someone.

we can clearly see in points 1,2 & 3 that words given in pairs are somehow similar in meaning, but in point 4  words Yielding and Resistant are completely different in meaning. So the words of this pair are not synonyms.

The correct answer is option 2)

• In option 1) enough has been before bright (an adjective) which is grammatically incorrect, for "enough" always follows an adjective and precedes a noun. E.g. enough money, intelligent enough, etc.
• For the same reason, option 2) is grammatically correct which is the correct answer.
• 'As' is used with 'enough' when we have some level of expectation involved (जितना हो सके). For e.g. "Yet this high level of commitment to preventative health care is still not seen as enough."

i) V is to the west of W

∴ V ← w

ii) Z is to the east of Y

∴ X → Z

iii) Z is to the west of V

(∵ from 1, 2) ∴ X → Z ← V ← w

iv) W is to the west of Y

∴ X – Z – V – W – Y

∴ V is in the middle.

Solution: Let the no. of multiple choice question be ‘x’

Let the no. of essay question be ‘y’

∴ According to given into

x + y = 20     ---(1)

Now given that

1. Total paper is of 100 marks

2. MCQ question are of 3 marks each

3. Essay questions are of 11 marks each

∴ 3x + 11y = 100   ---(2)

Solving (1) and (2)

x + y = 20    -- (1)

3x + 11y = 100   ---(2) 

Multiply eqn (1) by 3

∴ 3x + 3y = 60   ---(3)

Now subtract eqn (3) from eqn (2)

\(\frac{{\begin{array}{*{20}{c}}
{\therefore ;;3x + 11y = 100}\
{ - 3x + 3y = 60}
\end{array}}}{{\begin{array}{*{20}{c}}
{;;;;;;;;;8y = 40}\
{;;;;;;;;y = 5}
\end{array}}}\)

Put y = 5 in eqn (1)

∴ x = 15

∴ No. of multiple choice questions are 15.

Given: 

Red socks → 3

Green socks → 4

Blue socks → 3

To find that if we choose 2 socks then the probability that they both are of same column.

∴ Probability of same 2 coloured socks

\( = \left( {\frac{{3{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right) + \left( {\frac{{3{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right) + \left( {\frac{{4{{\rm{C}}_2}}}{{10{{\rm{C}}_2}}}} \right)\)

\( = \frac{3}{{45}} + \frac{3}{{45}} + \frac{6}{{45}}\)

\( = \frac{{12}}{{45}}\)

\( = \frac{4}{{15}}\)

Explanation:

Through these lines, the author means to convey that he lived in a culture that did not consider literature important unless it was supporting something that was seen to be more important or urgent, and names 'ideology' as that thing.

By stating that ideology was 'seemingly' more important, he implies that, in his opinion, it wasn't more important than literature but was seen to be.

Therefore, the correct answer is 'seemingly'.

So according to the question there are 3 boxes and all are incorrectly labelled.

→ We have to choose only one box  and inspect one fruit & determine the contents of all three boxes.

→ Here two things are important to notice that labels are incorrect and we can only inspect one fruit from any of the one box.

→ So we will take into consideration the box which is labelled as apples and oranges

As it is incorrectly labelled so there will be only apples or only oranges so lets assume that we got apples.

so the box on which oranges label is attached will have apples and oranges both in it because in the question it is mentioned that they are incorrectly labelled. 

if (apples and orange) will be in the box labelled as apples then only one fruit orange and one label orange is remaining and they cannot be on same box.

Hence orange will be in the box labelled as apple.

Hence when we will choose the box labelled as apple and oranges we will be able to determine the content of all 3 boxes.

Similarly if in the beginning if we assume oranges we wiil be able to determine the contents of every box too but the arrangement will be in the following way

X is a 30-digit number

The first digit is 4, and the rests are 7

i.e. X = 47777 _______ up to 29 terms (digit 7 only)

X = 4.777 × 10²⁹

Taking, Log₁₀ both sides

\({\rm{lo}}{{\rm{g}}_{10}}X = {\log _{10}}\left( {4.777{\rm{;}} \times {\rm{;}}{{10}^{29}}} \right)\)

\( = {\log _{10}}4.777; + \log _{10}^;{10^{29}}\) 

= 0.679 + 29

= 29.679

Also,     

\({\log _{10}}\left( {{X^3}} \right) = 3{\log _{10}}X\) 

\({\log _{10}}\left( {{X^3}} \right) = 3 \times 29.679\)

\({\log _{10}}\left( {{X^3}} \right) = 89.037\)

Taking anti \({\rm{lo}}{{\rm{g}}_{10}}\) both sides,

\({X^3} = {10^{89.037}}\)

\({X^3} = {10^{89}} \times {10^{0.037}}\)

\({X^3} = 1.0889 \times {10^{89}}\)

Thus, there are 90 digits in X³.

Given, \({e^x} + 0.5{x^2} - 2\)

e^x + 0.5x² – 2 = 0   ---(i)

We have to find the number of roots in the range [ -5, 5]

Differentiating both sides,

\(;\frac{d}{{dr}}\left( {{e^x} + 0.5{x^2} - 2} \right) = 0\)

\({e^x} + 0.5 \times 2x = 0\)

\({e^x} = - x\)     ---(ii)

Any dependent variable differentiation w.r.t. the independent variable gives the maximum value of dependent variable at one of the roots when we put the differentiation equals to zero.

As, the value gives a root of the dependent variable,

So from equation (ii), using this as a root of equation (i)

we get,

\(- x + 0.5{x^2} - 2 = 0\)     [putting eqn (ii) in eqn (i)]

\(\frac{{{x^2}}}{2} - x - 2 = 0\)

\({x^2} - 2x - 4 = 0\)

\(x = \frac{{2 \pm \sqrt {4 - 4 \times 1 \times \left( { - 4} \right)} }}{2}\)

\( = 1 \pm \sqrt 5 \)

\(ie.;x = 1 + \sqrt 5 ;& ;1 - \sqrt 5 \)

So, there are two root of the equation.

Possibility of thunderstorm = ?

They defined possibility of thunderstorm is given by low fast air pressure rises or drops over region.

Now if you will closely notice the diagram given in the question then you will notice that only in the region ‘R’ there are 4 contour lines passing i.e. variation of pressure or pressure rise/drop in a that region is very fast and rapid Hence the answer is R.

STEPS:

1. First, convert the given hexadecimal number into binary equivalent.

2. Convert that binary number into an octal number.

Binary equivalent of BCA9: 1011110010101001

Representation of this binary equivalent to octal number system is: 136251

Tips and Tricks:

For hexadecimal number, pair of 4 binary bits are taken from right to left and for octal number, pair of 3 binary bits is taken starting from least significant bits.

• A static variable is the one that remains in the memory while the program is running. So, static char var; => matches with => A variable located in the data section of memory
• m = malloc(10); m = NULL, As here memory is first allocated to m, then m becomes NULL, it means the program has no longer a pointer to memory. This is the problem of lost memory which cannot be freed.
• char *ptr[10]; It is an array of 10 pointers. It means a sequence of memory locations to store addresses.
• Register int var1; Here, variable var1 is declared with register keyword which means the variable can be put into registers. A request to allocate a CPU to store data.

• Recurrence relation for tower of Hanoi problem is T (n) = 2 T (n - 1) + 1, So, time complexity for tower of Hanoi problem is Θ (2 n).
• Binary search algorithm searches a sorted array by repeatedly dividing the search interval in half. If value of search key is less than the item in middle, search in the lower half otherwise, search in upper half. In this way, time complexity of binary search in sorted array becomes Θ (log n).
• Heap sort algorithm worst case time complexity is Θ (n log n).
• Addition of two n × n matrices takes Θ (n 2) time to execute. As there are two for loop used while addition of two n × n matrices.

Concept: Property of context-free languages is:

Context-free languages are closed under union and difference but not closed under complementation and intersection.

Explanation:

Option 1) L1 ∪ L2 is context-free

As context-free languages are closed under union. So it is correct.

Option 2).  L̅1 is context-free

L1 is a context-free language. According to the property, its complement can’t be context-free.

Option 3) L1 – R is context-free

As the difference of a context-free language with regular is context-free. So, it is correct.

Option 4) L1 ∩ L2 is context-free

It violated the context-free language property. The intersection of two CFL’s is not CFL. So, it is incorrect.

Phases of the compiler are:

Diagram

Concept: LR parsers in terms of their power:

CLR > LALR > SLR > LR (0)

Explanation:

I. Canonical LR is more powerful than SLR. TRUE

II. SLR is more powerful than LALR. FALSE

III. SLR is more powerful than Canonical LR. FALSE

Multiple threads of the same process share other resources of process except register, stack and stack pointer. In particular, a process is generally considered to consist of a set of threads sharing an address space, heap, static data, code segments and file descriptors.

Concept:

Internal fragmentation occurs when a process is allocated more memory than required, few space is left unused.

External fragmentation occurs when blocks of memory are there, but they are non-contiguous and can’t fill the upcoming request for memory.

Explanation:

Linked and indexed allocation are free from external fragmentation but contiguous allocation scheme suffered from external fragmentation problem.

Option 1) RIP uses distance vector routing

RIP is a dynamic routing protocol which uses hop count as a routing metric between source and destination. It uses distance vector routing So, it is correct.

Option 2) RIP packets are sent using UDP

RIP uses the UDP protocol for transmission of data. So, it is correct.

Option 3) OSPF packets are sent using TCP

OSPF is a link state routing protocol which uses multicast address to find the best path between source and destination. As, TCP does not support multicasting. So, OSPF packets are not sent using TCP. So, it is incorrect.

Option 4) OSPF operation is based on link-state routing. It is correct.

Given, \(f\left( x \right) = R\sin \left( {\frac{{\pi x}}{2}} \right) + S,;f'\left( {\frac{1}{2}} \right) = \sqrt 2 ;and;\mathop \smallint \nolimits_0^1 f\left( x \right)dx = \frac{{2R}}{\pi }\)

\(f'\left( x \right) = R;{\rm{cos}}\left( {\frac{{\pi x}}{2}} \right) \times \frac{\pi }{2}\)

\(f'\left( {\frac{1}{2}} \right) = R\cos \left( {\frac{{\pi \left( {\frac{1}{2}} \right)}}{2}} \right) \times \frac{\pi }{2} = ;\sqrt {2;} ;{f'}\left( {\frac{1}{2}} \right) = \sqrt 2\)

\(f'\left( {\frac{1}{2}} \right) = R \times \frac{1}{{\surd 2}} \times \frac{\pi }{2} = ;\sqrt 2 \)

\(R = ;\frac{{\sqrt 2 ; \times ;\sqrt 2 ; \times 2}}{\pi } = ;\frac{4}{\pi }\)

Now, f(x) becomes,

\(f\left( x \right) = ;\frac{4}{{\pi ;}} \times \sin \left( {\frac{{\pi \times x}}{2}} \right) + S\)

\(\mathop \smallint \nolimits_0^1 f\left( x \right)dx = ;\mathop \smallint \nolimits_0^1 \left( {\frac{4}{\pi }; \times \sin \left( {\frac{{\pi \times x}}{2}} \right) + S} \right)dx = ;\frac{{2 \times R}}{\pi } = ;\frac{8}{{{\pi ^2}}}\)

\(\frac{4}{\pi }\mathop \smallint \nolimits_0^1 \sin \left( {\frac{{\pi x}}{2}} \right)dx + ;\mathop \smallint \nolimits_0^1 Sdx = ;\frac{8}{{{\pi ^2}}}\)

\({4}{\pi }\left[ { - \cos \left( {\frac{{\pi x}}{2}} \right) \times \frac{2}{\pi }} \right]_0^1 + S\left[ x \right]_0^1 = ;\frac{8}{{{\pi ^2}}}\)

\(\frac{8}{{{\pi ^2}}}\left[ { - 0 + 1} \right] + S = ;\frac{8}{{{\pi ^{2;}}}};\)

\(\therefore ;S = 0\)

Concept:

And operator - ʌ

Only if meaning: q only if means that p is a necessary condition for q , denoted as : q → p

Explanation:

p = it is raining

q = it is cold

r = it is pleasant

 ¬ p = it is not raining

Now, “’ It is not raining, and it is pleasant” =   ¬ p ʌ r

“it is not pleasant only if it is raining and it is cold’’ denoted as =   ¬ r → (p ʌ q)

So, the overall expression for ‘’It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold’’ will be:

( ¬ p ʌ r )  ʌ ( ¬ r → (p ʌ q ) )

Option 1) is true.

Concept:

32-bit floating-point representation of a binary number in IEEE- 754 is

Calculation:

Given binary number is

00111110011011010000000000000000

Here, sign bit is 0. So, number is positive.

Exponent bits = E = 01111100 = 124 (in decimal)

Mantissa bits M = 11011010000000000000000

In IEEE-754 format, 32-bit (single precision)

(-1)^s × 1.M × 2^{E – 127}

= (-1)⁰ × 1.1101101 × 2^{124 – 127}

= 1.1101101 × 2^-3

= (1 + 2^-1 + 2^-2 + 2^-4 + 2^-5 + 2^-7) × 2-3

= 0.231 = 2.31 × 10^-1 ≈ 2.27 × 10^-1

Solution:

Concept:

In a queue, elements are deleted from front and inserted from rear end. Whenever a new element is inserted, rear is incremented.

Explanation:

Diagram

So, in case of a circular queue to make an insert and delete operation in O (1) time, the rear pointer will point to the next node i.e. front node. After storing this pointer rear will point to the newly created node.

For enqueue: struct node *ptr

ptr -> next = rear -> next;

rear -> next = ptr

rear = ptr

For dequeue: ptr(front node)

rear -> next = front ->next

ptr = front

front =rear -> next

free(ptr)

Important Points:

For above enqueue and dequeue,

Assume linked list contains more than one element

Structure:

struct node

{

int data;

struct node *next;

}

When printxy(1, 1) is called, this part of the program will execute.

Code Explanation:

void printxy (int x, int y) {                    //  Here x and y becomes 1

int *ptr;

x = 0 ;                                    // it will make x = 0

ptr = &x;                                // here, ptr contains the address of x,

y = *ptr;                                 //  value of y = 0

*ptr = 1;                                 // value of x = 1

printf (‘’%d, %d’’, x, y);          // it will print x as 1 and y as 0

}

Explanation

y = *ptr;                     

y is pointing to ptr but as * is there, value of ptr will be accesses which is same as value of x

because ptr is pointing to x location.

*ptr = 1;

Sine ptr is pointing at location x, x value chances to 1.

Concept:

Breadth first search involves search through a tree one level at a time. Traverse through one entire level of child node first, before moving to traverse through the grandchildren nodes.

Explanation:

1. MNOPQR

In this, traversal starts from S but O is visited first before child node N and Q of M. So, incorrect.

2. NQMPOR

It is also incorrect, P is traversed before O.

3. QMNROP

Incorrect, because O must be traversed before R.

So, option 4) is correct.

Grammar:

S → XY

X → aX | a

Y → aYb | ϵ

Explanation:

X generates at least one a. Generates a string of type {a, aa, aaa, aaaa……}

a^mbⁿ, if n = 0 and m = 0 ∴ string = ϵ which cannot be generated from the given grammar and hence option 2 is incorrect.

Y generates an equal number of a and b { ϵ, ab, aabb, ……} with a comes before b.

Since at least one a is generated by X and an equal number of a’s and b’s generated by Y ∴ m> n and hence option 1 is incorrect

The smallest length string generated by Y is ϵ. In a^mbⁿ, n ≥ 0 and hence option 4 is incorrect.

{ a, aab, aaabb,………….} which is equivalent to :

L = {a^mbⁿ | m > n, n ≥ 0}

Concept:

Total participation: It specifies that each entity in the entity set must compulsorily participate in at least one relationship instance in that relationship set.

Partial participation: It specifies that each entity in the entity set may or may not participate in the relationship instance in that relationship set.

Explanation:

In one to many or many to one relation, the relation between two entities is merged on the many side with total participation. As, it is given that relationship R doesn’t have its own attributes. So, it must be combined with entity A. So, the relation must be many to one and there should be total participation of A in R.

A connected UDP socket calls connect function again to specify a new IP address and port. Also to disconnect the socket.

I. A connected UDP socket can be used to communicate with multiple peers simultaneously.

Servers that use UDP are normally iterative in nature means that the server processes one request at a time. A server gets the request received in a datagram from UDP, processes the request and gives the response to UDP to send to the client. So, this statement is incorrect.

II. A process can successfully call connect function again for an already connected UDP socket.

As, it is already known that a connect function can be called again to setup new peers and to disconnect the already connected sockets. So, this statement is correct.

Concept:

During on delete cascade, when something is deleted that is primary key in table 1 than it is deleted from table 2 also if there is a same foreign key in table 2 referencing primary key in table 1. During on set NULL, when data is table of primary key than in foreign key it is set to NULL.

Diagram:

Explanation:

When record (3,8) is deleted from T1 as 3 is the primary key in T1 and foreign key in T2 with on delete set NULL. So in table T2, at entry (8, 3) that 3 becomes NULL, no entry will be deleted from T2. When no entry is deleted from T2 primary key R that’s why the number of additional records that need to be deleted from T1 is 0 because R references Q in table T1.

Concept:

Record route record the routers an IP packet takes as it propagates from source to destination device.

Format:

In IPv4, for options, 40 bytes are reserved. 3 bytes are already used 1 for code, 1 for length and 1 for the pointer. So only 37 bytes are remaining.

An IP address is of 4 bytes (32 bits)

Router addresses that can be listed in record route option field = \(floor\left( {\frac{{37}}{4}} \right) = 9\)

Concept:

A Hasse diagram becomes a lattice if for every pair of elements in the Hasse diagram there exist a LUB (Least upper bound) and GLB (Greatest lower bound).

Explanation:

Consider all the pairs one by one:

For each pair of Hasse diagram, there exists a LUB and GLB, so there is no need to add any ordered pairs. It is already a lattice.

Concept:

The rank of a matrix is defined as the maximum number of linearly independent column vectors in the matrix or the maximum number of linearly independent row vectors in the matrix.

In terms of determinant, rank of a matrix can be viewed as m where m is the size of the largest non- zero m × m submatrix with non-zero determinant.

Calculation:  

\(P = \left[ {\begin{array}{*{20}{c}} 1&1&{ - 1}\ 2&{ - 3}&4\ 3&{ - 2}&3 \end{array}} \right];and;Q = \left[ {\begin{array}{*{20}{c}} { - 1}&{ - 2}&{ - 1}\ 6&{12}&6\ 5&{10}&5 \end{array}} \right]\)

\(Let;X = P + Q = ;\left[ {\begin{array}{*{20}{c}} 0&{ - 1}&{ - 2}\ 8&9&{10}\ 8&8&8 \end{array}} \right]\)

\(\left| X \right| = \left| {\begin{array}{*{20}{c}} 0&{ - 1}&{ - 2}\ 8&9&{10}\ 8&8&8 \end{array}} \right|\)

|X| = 0 (72 – 80) – (–1) (64 – 80) – 2(64 – 72) 

∴ |X| = 0 + (–16) + 16 = 0

Determinant of 3 × 3 matrix is zero.

∴ Rank(X) ≠ 3

\(\left| {\begin{array}{*{20}{c}} 0&{ - 1}\ 8&9 \end{array}} \right| = 8 \ne 0\)

Determinant of 2 × 2 matrix is nonzero. So, rank of X is 2.

Data:

d_min = 3

edges = |E| = 25

Formula:

\({{\rm{d}}_{{\rm{min}}}}{\rm{;}} \le \frac{{2\left| {\rm{E}} \right|}}{{\left| {\rm{n}} \right|}} \le {\rm{;}}{{\rm{d}}_{{\rm{max}}}}\)

Calculation

\(3{\rm{;}} \le \frac{{2 \times 25}}{{\rm{n}}}\)

\({\rm{n;}} \le \frac{{2 \times 25}}{3} \le 16.66\)

∴ n_max = 16

So, maximum possible value of n is 16.

Formula:

In quadratic equation, ax² + bx + c = 0

Sum of root =

Product of roots =

Calculation:

Quadratic equation: x² – 13x + 36 = 0

Given base is b.

Roots of the equation with base b is 5 and 6

5_b + 6_b = (13)_b

11 = b + 3

b = 8

Also, by considering the product of roots,

5_b × 6_b = (36)_b

30 = 3b + 6,

24 = 3b, b = 8

In both cases, base b = 8

Given language is:  L = {w₁aw₂ | w₁, w₂ ϵ {a, b}*, |w₁| = 2, |w₂| ≥ 3}

Regular expression: (a+b) (a+b) a (a+b) (a+b) (a+b)(a+b)^*

Minimum length string that is possible = (a+b) (a+b) a (a+b) (a+b) (a+b)

This string has minimum length 6. For these 7 states are needed and one trap state. So, total 8 states are needed.

DFA for given language is

Data:  

\(p\left( P \right) = \frac{1}{4}\)

\(P\left( {\frac{P}{Q}} \right) = ;\frac{1}{2}\) , \(P\left( {\frac{Q}{P}} \right) = ;\frac{1}{3}\)

Formula

\(P\left( {\frac{A}{B}} \right) = ;\frac{{P\left( {A \cap B} \right)}}{{P\left( B \right)}}\)

Calculation:

\(P\left( {\frac{Q}{P}} \right) = ;\frac{{P;\left( {P \cap Q} \right)}}{{P\left( P \right)}},;;\) 

\(\frac{1}{3} = ;\frac{{P\left( {P \cap Q} \right)}}{{\frac{1}{4}}}\)  , 

\(P\left( {P \cap Q} \right) = ;\frac{1}{{12}}\)

Also, \(P\left( {\frac{P}{Q}} \right) = \frac{{P;\left( {P \cap Q} \right)}}{{P\left( Q \right)}},;;\)

\(\frac{1}{2} = \frac{{\frac{1}{{12}}}}{{P\left( Q \right)}}\) ,

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

Required probability, \(P\left( {\frac{{P'}}{{Q'}}} \right) = \frac{{P\left( {P' \cap Q'} \right)}}{{P\left( {Q'} \right)}}\)

\(= \frac{{P{{\left( {P \cup Q} \right)}'}}}{{1 - P\left( Q \right)}}; = \frac{{1 - P\left( {P \cup Q} \right)}}{{1 - P\left( Q \right)}}\)

\(= \frac{{1 - \left( {P\left( P \right) + P\left( Q \right) - P;\left( {P \cap Q} \right)} \right)}}{{1 - P\left( Q \right)}};\)

\(= \frac{{1 - \left( {\frac{1}{4} + \frac{1}{6} - \frac{1}{{12}}} \right)}}{{1 - \frac{1}{6}}}\)

\(= \frac{{\frac{8}{{12}}}}{{\frac{5}{6}}} = \frac{4}{5}\)

Formula:

A + A = A; A.A = A ; A + A.B = A; 

1 + A = 1; 1.A = A

Explanation:

Consider all the options

Option 1:

wx + w(x + y) + x(x + y) = x + wy

wx + wx + wy + xx + xy = x + wy

wx + wy + x + xy = x + wy

x + wy = x + wy

Option 2:

\(\overline {w\bar x\left( {y + \bar z} \right)} + \bar wx = \bar w + x + ;\bar yz\)

\(\bar w + \overline {\bar x} + \bar y;;\overline {\bar z} + ;\bar wx = ;\bar w + x + \bar yz\)

\(\bar w + x + \bar y;;z + ;\bar wx = ;\bar w + x + \bar yz\) 

\(\bar w + x + \bar y;;z; = ;\bar w + x + \bar yz\) 

Option 3:

(wx̅ (y + xz̅ ) + w̅ x̅)y = xy̅ 

\(\left( {w;\bar x;y + w\bar z + \bar w;\overline {x;} ;} \right)y = x\bar y;\)

\(\left( {w;\bar x;y + w\bar z;y + \bar w;\overline {x;} ;;y} \right) = x\bar y\)

\(\left( {;\bar x;y + w\bar z;y} \right) = \bar x;\bar y\)

\(\therefore \left( {;\bar x;y + w\bar z;y} \right) \ne \bar x;\bar y\)

Option 4:  

(w + y) (wxy + wyz) = wxy + wyz

wxy + wyz + wxy + wyz = wxy + wyz

wxy + wyz = wxy + wy

Concept:

In SOP (sum of product) form, a min term is represented by 1.

In POS (product of sum) form, a max term is represented by 0.

Sum of product: (SOP)

f(w, x, y, z) = ∑_m (0, 1, 2, 3, 7, 8, 10) + ∑_d (5, 6, 11, 15)

Product of sum: (P0S)

f(w, x, y, z) = Π (4, 9, 12, 13, 14)  + ∑_d (5, 6, 11, 15),

Diagram:

K-map from this expression is:

f(x, y, w, z) = (w’ + z’) (x’ + z)

Data:

Access time of L₁ = T₁ = 1 clock cycle

Access time of L₂ = T₂ = 8 clock cycle

L₂ miss penalty = T₃ = 18 clock cycle

L₁ miss rate = 2 × L₂ miss rate

Average memory access time = AMAT = 2 clock cycle

Let, L₂ miss rate = a

∴ L₁ miss rate = 2a

Formula:

 AMAT = (T₁ + 2a × T₂ + 2a × a × T₃)

Calculation:

2 = 1 + 2a × 8 + 2a × a × 18

2 = 1 + 16a + 36a²

36a² + 16a -1 = 0

36a² + 18a – 2a + 1 = 0

18a (2a + 1) – 1(2a + 1) = 0

\(a = \frac{{ - 1}}{2},\frac{1}{{18}}\)

So, miss rate of L₂ = 0.056 and Miss rate of L₁ = 0.111

\(T\left( n \right) = 2;T\left( {\sqrt n } \right) + 1\)

Put n= 2^m, m = log₂n

\(T\left( {{2^m}} \right) = 2T\left( {{2^{\frac{m}{2}}}} \right) + 1\)

\(Put;T\left( {{2^m}} \right) = S\left( m \right)\)

\(S\left( m \right) = 2;S;\left( {\frac{m}{2}} \right) + 1\)

Now, calculate \({n^{log_b^a}}\)

\({m^{log_b^a}} = m\)

S (m) = m + 1

S(m) = m

Put the value of m 

Therefore, T(n) in terms of Θ notation is Θ (logn).

Derivative of g_x (z) at z = 1 gives the expectation E (X).

When g_y(z) is expanded, it results in a binomial distribution form and mean of a binomial distribution is in the form of N *p.

\({g_x}\left( z \right) = ;\mathop \sum \limits_{j = 0}^N {p_j}{z^j}\)

\({g'_x}\left( z \right) = ;\mathop \sum \nolimits_{j = 1}^N j{p_j}{z^{j - 1}} = ;\mathop \sum \nolimits_{j = 1}^N j{p_j} = E\left( X \right)\) 

Similarly, take the derivate of g_y(z) at z= 1.

\(E\left( Y \right) = ;{\left. {{{g'}_y}\left( z \right)} \right|_{z = 1}} = ;{\left. {\left( {{{\left( {1 - ;\beta + \beta z} \right)}^N}} \right)'} \right|_{z = 1}} = N\beta {\left. {{{\left( {1 - \beta + \beta z} \right)}^{N - 1}}} \right|_{z = 1}} = N\beta {\left( {1 - \beta + \beta z} \right)^{N - 1}}\)

\(E\left( Y \right) = N\beta \)

Concept:

A production of grammar is said to have left recursion if its leftmost variable of its RHS is same as variable of LHS.

Consider grammar of type A → Aa | b

After removing left recursion, it becomes A → bA’, A’ → aA’| ϵ

Explanation:

Given grammar is:

E → E – T | T

T → T + F | F

F → (E) | id

After removing left recursion, it becomes:

E → TE’

E’ → -T E’ | ϵ

T → FT’

T’ → + FT’ | ϵ

F → (E) | id

Therefore option 3 is correct.

Resource allocation table:

Available = 9 – ∑ (current allocation to process) = 9 – 7 = 2

Now, 2 resource will satisfy the need of P3.

After this available = 2 + 3 = 5

5 resource can satisfy need of P2 or P1

CASE 1:

If P2 is executed before P1, 

Available = 5 + 1 =6

6 resource can satisfy the need of P1 easily.

CASE 2:

If P1 is executed before P2

Available = 5 + 3 = 8

8 resource can satisfy the need of P1 easily.

Safe sequence will be P3, P1, P2 and P3, P2, P1

System is safe and there is no deadlock in the system.

Concept:

Hamming distance is a metric for comparing two binary strings. While comparing two binary strings of equal length, hamming distance is the number of bit positions in which the two bits are different.

Explanation:

Given code words are:  00000, 01011, 10101, 11110

Code 1 = 00000

Code 2 = 01011

Code 3 = 10101

Code 4 = 11110

Hamming distance can also be calculated by taking XOR of two binary strings.

Here hamming distance between code1 and code2 is 3. Similarly, between code 1 and code 3, hamming distance is 3.

But between code 2 and code 3 hamming distance is 4. But we have to take minimum hamming distance which is 3.

So, p = 3

Now, maximum error bits that can be correct using hamming distance = \(floor\left( {\frac{{d - 1}}{2}} \right) = \frac{{3 - 1}}{2} = 1\) 

So, q = 1

Data:

Transmission rate = bandwidth = 10⁶ bits/sec

Distance = 10,000 km

Propagation speed = 2 × 10⁸ m/sec

Frame size = 50,000 bytes

Formula:

Transmission time = \(\rm \frac{{frame;length}}{{bandwidth}}\)

Propagation time = \(\rm \frac{{Distance}}{{propagation;speed}}\)

Calculation:

\(\rm Transmission;time = p = \frac{{50000\ \times\ 8}}{{{{10}^6}}} = \frac{{4\ \times ;{{10}^5}}}{{{{10}^6}}} = \frac{{4 ;\times; 100}}{{10 ;\times; 100}} = 400;msec\)

\(\rm Propagation;time = q = ;\frac{{10000; \times; 1000}}{{2; \times ;{{10}^8}}} = \frac{1}{{20}} = 50;msec\)

∴ p = 400 and q = 500

Concept:

Inorder traversal of a binary search tree is the ascending order of the given values.

In pre- order first node is the root.

Pre-order Traversal = root, left, right

In-order = left, root, right

Post-order = left, right, root

Explanation:

Pre-order traversal is 12, 8, 6, 2, 7, 9, 10, 16, 15, 19, 17, 20.

In-order traversal is 2, 6, 7, 8, 9, 10, 12, 15, 16, 17, 19, 20

Now, anything which is in the left of root in in-order traversal will come to the left of root and other comes to the right of root.

Binary search tree using pre-order and in-order traversal is:

Diagram:

So, post order traversal of this binary search tree is 2, 7, 6, 10, 9, 8, 15, 17, 20, 19, 16, 12

Given condition is x == (y*q + r)

Here, x= result, y= multiplicand, q= quotient, r= remainder

As, the number is divided using repeated subtraction, So quotient must be 0 in that case.

When in above condition q= 0

Then, x = r.

It matches with option 3.

We have to check how many times inner loop will be executed here.

For i=1,

j will run 1 + 2 + 3 + …………. (n times)

For i=2

j will run for 1,3,5, 7, 9, 11,………..(n/2 times)

For i=3

j will run for 1,4,7,10, 13…………… (n/3 times)

So, in this way,

\(T\left( n \right) = n + \frac{n}{2} + \frac{n}{3} + \frac{n}{4} + \frac{n}{5} + \frac{n}{6} \ldots + \frac{n}{n}\)

\(= n\left( {1 + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} \ldots + \frac{1}{n}} \right);\)

So, Time complexity of given program = Θ (n log n)

Concept:

Extended transition function means when we start from a state and follow a sequence of input.

In case of ϵ-NFA, epsilon moves are also considered.

Diagram: NFA for the given NFA table is:

Here, \(\hat \delta ;\left( {{q_2},;aba} \right)\) 

Explanation:

When input a is applied on q₂ it will move to q₀, q₁ as there is null transition so it will also get to q₂.

Similarly, states after input b => {q₀, q₂, q₃}

States after input a = {q₀, q₁, q₂}

So, final answer is {q₀, q₁, q₂}

Consider the options one by one:

Option 1:

L₁ = {a^p | p is a prime number}

Prime numbers do not have fixed pattern. So, it is not possible to solve it using pushdown

automaton. So, L₁ is not context free language.

Option 2:

L₂ = {aⁿb^mc^2m | n ≥ 0, m ≥ 0}

It can be solved easily using single stack.  Comparison is done between b and c. We can make a pushdown automaton for this. So, L₂ is context free language.

Option 3:

L₃ = {aⁿbⁿc²ⁿ | n ≥ 0}

First comparison is between a and b, then between b and c, therefore two stacks are required.

So, it is context sensitive language. L₃ is recursive language.

Option 4:

L₄ = { aⁿbⁿ | n ≥ 1}

First push a into a stack then pop a for each b from the stack. The given language is accepted by

Deterministic Pushdown Automaton. Therefore, L₄  is deterministic context-free.

Decidable properties of Languages:

For decidable: D

For un-decidable: U

For grammar: G

From the above table:

Membership property of regular grammar is decidable.

Emptiness problem of context free grammar is decidable.

Universality property for context free grammar is undecidable.

Membership problem of Turing machine is undecidable.

Concept:

Output of T flip flop will change when T = 1 and remain same when T = 0

Excitation table for T flip flop

From this table, 

T1 = Q̅1Q0

T0 = Q̅1 + Q̅0

Important Point:

T₀ → NAND Gate (function)

Tips:

If unable to write the function then construct the K- Map of two variable with Q1 and Q0 as input

int main () {

                int array [ ] = { 3, 5, 1, 4, 6, 2} ;

                int done = 0;

                int i;

                while (done == 0) {                           // first time condition becomes true

                                done = 1;                              // done becomes 1

                                for (i=0; i<=4; i++) {                                         //first for loop

                                                if (array[i] < array [i+1]) {

                                                                swap (&array[i], &array[i+1]);

                                                                done = 0;

                                                }

                                }

                                for (i=5; i>=1; i--) {                                       //second for loop

                                                If (array[i] > array[i-1]) {

                                                                Swap (&array[i], &array[i-1]);

                                                }

                                }

                }

                printf(‘’%d’’, array[3]);

}

Initially array is:

Here, when while condition becomes true, first for loop will be executed, the content of the array after this:

After second for loop, content of array will become:

After this, again it goes to while loop, done is 0, condition is true, now after execution of first for loop content of array will be:

No change in the contents after second for loop.

After this, when while condition becomes true again, done = 1, after this there will be no change in the done variable because content of array remains same.

Then, while condition becomes false, array[3] is the output, which is 3.

Concept:

Conflict serializable schedule which can be transformed in a serial schedule by swapping non conflicting operations. Two operations are conflicting: if they belong to different transactions and operate on same data. A conflict serializable schedule must be free from read-write, write-write, write-read conflicts.

Explanation:

In both transaction T₁ and T₂, common data item is Y. There can be conflict between T₁ and T₂ on data item Y.

FIRST SEQUENCE OF EXECUTION:

T₁ executes first and then T₂.  There is conflict between r₁(Y) and w₂(Y).  SO, either both the read and write of T₁ on Y should be performed before read write pair of T₂ or after read write pair of T₂. Because in all other cases, it causes violation.

According to the, one serial arrangement is r₁ (X)w₁ (X)r₁ (Y)w₁ (Y), r₂ (Y)w₂ (Y)r₂ (Z)w₂ (Z)

As, there are total 8 operations, so total sequence possible = \(\frac{{8!}}{{4!4!}} = 70\)

Now find the schedules which have a cycle in the precedence graph or which violate the conflict serializability.

These operations are: r₁(Y) w₁(Y), r₂(Y) w₂(Y).

Sequences of operation possible from this are:

Consider the possible sequences as core sequence and then find the other sequences.

Out of the total, 16 schedules are not possible in this way.

Total conflict serializable schedule that are possible = 70 – 16 = 54

Data:

Instruction Fetch:

T₁ = 2 ns, T₂ = 8 ns and T₃ = 90 ns

H₁ = 0.8 and H₂ = 0.9

Data Fetch:

T₁ = 2 ns, T₂ = 8 ns and T₃ = 90 ns

H₁ = 0.9 and H₂ = 0.9

Formula:

T_avg = T₁ + (1 - H₁) T₂ + (1 – H₁) (1 – H₂) T₃

Calculation:

Instruction Fetch:

T_avg = 2 + 0.2 × 8 + 0.2 × 0.1 × 90

∴ T_avg = 5.4 ns

For 60 % instruction fetch

T_avg = 0.6 × 5.4 = 3.24 ns

Data Fetch:

T_avg = 2 + 0.1 × 8 + 0.1 × 0.1 × 90

∴ T_avg = 2 + 0.8 + 0.9 = 3.7 ns

For 40% Data fetch

T_avg = 0.4 × 3.7 = 1.48 ns

Total_avg = 3.24 ns + 1.48 ns = 4.72 ns

Important Points:

In two level in serial manner,

T_avg = H₁T₁ + (1- H₁)(T₁ + T₂)

T_avg = T₁ + (1- H₁)(T₂)

Similarly, three level in serial manner

T_avg = H₁T₁ + (1 - H₁)H₂(T₁ + T₂) +(1- H₁)(1 - H₂)(T₁ + T₂ + T₃)

T_avg = T₁ + (1- H₁)T₂ + (1 - H₁)(1 -H₂)T₃

Here first condition results in the players where goals greater than all the player of spain. But there are no players of spain. So, this will result in all the players. Result of first query is:

Second condition results in player who have goals greater than goals of any player of Germany.

At the last result, it results in 7 tuples.

Formula:

\({\left( {1 - x} \right)^{ - n}} = 1 + \frac{n}{{1!}}x + \frac{{n\left( {n + 1} \right){x^2}}}{{2!}} + \frac{{n\left( {n + 1} \right)\left( {n + 2} \right){x^3}}}{{3!}} + \ldots \) 

Calculation:

\(\frac{{1 + z}}{{{{\left( {1 - z} \right)}^3}}} = \left( {1 + z} \right){\left( {1 - z} \right)^{ - 3}}\) 

\(= \left( {1 + z} \right)\left[ {1 + \frac{{3z}}{{1!}} + \frac{{12{z^2}}}{{2!}} + \frac{{60{z^3}}}{{3!}} + \ldots } \right]\)

\(= \left( {1 + z} \right)\left[ {1 + 3z + 6{z^2} + 10{z^3} + \ldots } \right]\)

\(= 1 + 3z + 6{z^2} + 10{z^3} + \ldots .. + z + 3{z^2} + 6{z^3} + \ldots \)

\(= 1 + 4z + 9{z^2} + 16{z^3} + \ldots\)

Here a_n is the coefficient of zⁿ

a₀ = 1

a₁ = 4

a₂ = 9, a₃ = 16

so, a₃ – a₀ = 16 – 1 = 15

Concept:

In case of Poisson distribution, mean and variance are same.

Calculation:

Given, mean = 5

E[(X + 2)²] = E [X² + 4X + 4] = E[X²] + E[4X] + E[4]

Variance = E[X²] – (E[X])²

As, mean = variance = 5

Mean = E[X]

5 = E[X²] -  (5)²

5 = E[X²] – 25

E[X²] = 30

So, E[(X+2)²] = 30 + 4 × 5 + 4 = 54

Data for B+ Tree:

Disk Block size = D= 512 byte

Block pointer = B = 2 byte

Key field = K = 8 byte.

Order = p

Formula:

p × 2 + (p – 1) (8) ≤ 512

Calculation:

p × 2 + (p – 1) (8) ≤ 512

2p + 8p ≤ 520

p ≤ 52

∴ p = 52

In Huffman coding, character with minimum probability are combined first and then other in similar way.

First take T and R,

Now, combine P and S

Another two minimum probabilities are 0.25 and 0.34, combine them.

Now, combine all remaining in same way.

Here, for left arm we are considering a 0 and for right arm we are considering 1.

Code for P = 01 (length 2)

Code for Q = 11 (length 2)

Code for R = 101 (length 3)

Code for S = 00 (length 2)

Code for T = 100 (length 3)

Expected length of encoded message =

 \(\sum \left( {length;of;code; \times probabilty} \right)\) × number of characters

= [(0.22 × 2) + (0.34 ×2) + (0.17×3) + (0.19×2) + (0.08 × 3)] ×100

= (0.44 + 0.68 + 0.51 + 0.38 + 0.24) × 100

= 225 bits

Gantt chart:

0             2              5             33            40            49            51            67

Process Table:

Average waiting time = \(\frac{{\sum waiting;time;of;all;the;processes}}{{number;of;processes}}\)

\(= \frac{{38 + 0 + 37 + 28 + 42}}{5} = 29\rm ;milliseconds;\)

Concept:

Characteristic equation: If A is any square matrix of order n, we can form the matrix [A – λI], where I is the nth order unit matrix. The determinant of this matrix equated to zero i.e. |A – λI| = 0 is called the characteristic equation of A.

Eigenvalues: The roots of the characteristic equation are called Eigenvalues or latent roots or characteristic roots of matrix A.

Calculation:

Here, polynomial is: λ³ – 4λ² + aλ + 30, a ∈ R

One eigen value is 2. So, it must satisfy this equation.

⇒ 2³ – 4 × 2² + a × 2 + 30 = 0,

⇒ 8 – 16 + 2a + 30 = 0

⇒ - 8 + 2a = -30

⇒ a = -11

Now, the polynomial will be 

λ³ – 4λ² + (-11)λ + 30 = 0

λ³ – 4λ² – 11λ + 30 = 0

Factorising we get,

(λ - 2) (λ - 5) (λ + 3) = 0

⇒ λ = 2, 5, -3

The largest among the absolute value of the eigenvalues of M is 5.

Data:

Memory size = 2³² bytes

Total address space = 32 bit

Block size = 32 bytes = 2⁵ byte

Cache lines = 512 = 2⁹

Formula:

In bits:

Total address space = tag + no. of lines + block offset

For direct mapped cache:

Calculation:

32 = x + 9 + 5

∴ x = 18

The size of tag field in bits = 18

Concept:

• C provides two unusual operators for incrementing and decrementing the variables
• The increment operator ++ adds 1 to its operand, while the decrement operator - subtracts 1
• The unusual aspect is the ++ and – can be used either as prefix operator or postfix operator.

Code Explanation:

#include<stdio.h>

int main ( ) {

int m = 10;

int n, n1;

n = ++m;                           // Here n= 11, m = 11

n1 = m++;                         // n1 = 11

n--;                                    // post decrement; here remains n = 11, but from next line n= 11

--n1;                                  // n1 = 10      (pre-decrement)

n -= n1;                             // n= n – n1; n = 10 – 10 = 0

printf(‘’%d’’, n) ;              // print 0

return 0;

}

So, the final answer is 0.

The output of the program is 0.

string c is:

100 101 102 103 104 105 106 107 108 109 110 111 112

\(\begin{matrix}p & \boxed{100} \\ {} & 200 \end{matrix}\)

Character is of one byte and hence each character it placed at one byte of space .

char* p = c; // p is pointing to base address of c

2[p] = p[2]

ASCII value of T and I in decimal are is 84 and 73 respectively.

c+2[p] – 6[p]-1 = 100 + p[2] - p[6] – 1

= 100 + T – I – 1 = 100 + (84 - 73) – 1

= 100 + 11 – 1 = 110

Which means string starting from address 110 onwards till 111

So, (int)strlen (c+2[p] – 6[p]-1)

= (int)strlen(“17”)

The output of the program is 2.