## Gate 2014 Set -03

Question 1 |

I | |

II | |

III | |

IV |

Question 1 Explanation:

Losing consiousness represents that it is a continuous process of losing the consiousness. It is not appropriate, he just lost the consiousness.

Question 2 |

If she _____________ how to calibrate the instrument, she ______________ done the experiment.

knows, will have | |

knew, had | |

had known, could have | |

should have known, would have |

Question 2 Explanation:

Rule: If + past perfect then result to be perfect conditional (or) perfect continuous condition.

Then answer is Option C.

Question 3 |

Choose the word that is opposite in meaning to the word “coherent”.

sticky | |

well-connected | |

rambling | |

friendly |

Question 3 Explanation:

Coherent = logical and consistent

Rambling = lengthy and confused (or) inconsequential

Rambling = lengthy and confused (or) inconsequential

Question 4 |

17 | |

37 | |

64 | |

26 |

Question 4 Explanation:

2,5, 10, 17, 26, 37, 50, 64

2 = 1

5 = 2

10 = 3

17 = 4

26 = 5

37 = 6

50 = 7

64 = 8

64 does not belong to the series.

2 = 1

^{2}+15 = 2

^{2}+110 = 3

^{2}+117 = 4

^{2}+126 = 5

^{2}+137 = 6

^{2}+150 = 7

^{2}+164 = 8

^{2}+064 does not belong to the series.

Question 5 |

1.34 | |

1.74 | |

3.02 | |

3.91 |

Question 5 Explanation:

Number of students = 21+17+6 (or) 15+27+2 (or) 23+18+3 = 44

Total marks obtained = (21×2)+(15×3)+(23×2) = 133

Average marks = 133/44 = 3.02

Total marks obtained = (21×2)+(15×3)+(23×2) = 133

Average marks = 133/44 = 3.02

Question 6 |

A dance programme is scheduled for 10.00 a.m. Some students are participating in the programme and they need to come an hour earlier than the start of the event. These students should be accompanied by a parent. Other students and parents should come in time for the programme. The instruction you think that is appropriate for this is

Students should come at 9.00 a.m. and parents should come at 10.00 a.m. | |

Participating students should come at 9.00 a.m. accompanied by a parent, and other parents and students should come by 10.00 a.m. | |

Students who are not participating should come by 10.00 a.m. and they should not bring their parents. Participating students should come at 9.00 a.m. | |

Participating students should come before 9.00 a.m. Parents who accompany them should come at 9.00 a.m. All others should come at 10.00 a.m. |

Question 6 Explanation:

Students who are particularly in the program and they need to come an hour earlier i.e., 09.00 am because the program is start of 10.00 am.

→ All other students and parents should come in time for the programme i.e. 10.00 am.

→ Option B is correct answer.

→ In option D, they gave, all other should come at 10.00 am that includes student's parents, staff and all ohers. So this is not correct option.

→ All other students and parents should come in time for the programme i.e. 10.00 am.

→ Option B is correct answer.

→ In option D, they gave, all other should come at 10.00 am that includes student's parents, staff and all ohers. So this is not correct option.

Question 8 |

The Gross Domestic Product (GDP) in Rupees grew at 7% during 2012-2013. For international comparison, the GDP is compared in US Dollars (USD) after conversion based on the market exchange rate. During the period 2012-2013 the exchange rate for the USD increased from Rs. 50/ USD to Rs. 60/ USD. India’s GDP in USD during the period 2012-2013

increased by 5% | |

decreased by 13% | |

decreased by 20% | |

decreased by 11% |

Question 8 Explanation:

Let,

GDP in rupees = x

GDP in dollars = x/50

Increase in GDP in rupees = 7%

∴ New GDP in rupees = 1.07x

New GDP in dollars = 1.07x/60

Change = ((1.07x/60) - (x/50))/(x/50) = -6.5/60 = -10.83%

As it is negative, the value has decreased.

GDP in VSD has decreased by 11%.

GDP in rupees = x

GDP in dollars = x/50

Increase in GDP in rupees = 7%

∴ New GDP in rupees = 1.07x

New GDP in dollars = 1.07x/60

Change = ((1.07x/60) - (x/50))/(x/50) = -6.5/60 = -10.83%

As it is negative, the value has decreased.

GDP in VSD has decreased by 11%.

Question 9 |

1:1 | |

2:1 | |

1.5:1 | |

2.5:1 |

Question 9 Explanation:

Given,

Male to female students ratio in 2011 = 1 : 1

Male to female students ratio in 2012 = 1.5 : 1 = 3 : 2

⇒ M

M

⇒ M

2M

Given,

F

M

But from (3)

M

We need to find

M

Male to female students ratio in 2011 = 1 : 1

Male to female students ratio in 2012 = 1.5 : 1 = 3 : 2

⇒ M

_{1}/F_{1}= 1:1M

_{1}= F_{1}------- (1)⇒ M

_{2}/F_{2}= 1:12M

_{2}= 3F_{2}------- (2)Given,

F

_{1}= F_{2}------- (3) From (1) & (2)M

_{1}/M_{2}= F_{1}/(3F_{2}/2) = 2F_{1}/3F_{2}But from (3)

M

_{1}/M_{2}= 2/3We need to find

M

_{2}: M_{1}= 3 : 2 = 1.5 : 1Question 10 |

Consider the equation: (7526)

_{8}- (Y)_{8 }= (4364)_{8}, where (X)_{N}stands for X to the base N. Find Y.1634 | |

1737 | |

3142 | |

3162 |

Question 10 Explanation:

(7526)

⇒ 1/8 = (7526)

Base 8 ⇒ 0 to 7 digits

When you are borrowing you will add the value of the base, hence 2 becomes (2+8) = 10

Y = 3142

_{8}- (Y)_{8}= (4364)_{8}⇒ 1/8 = (7526)

_{8}- (4364)_{8}Base 8 ⇒ 0 to 7 digits

When you are borrowing you will add the value of the base, hence 2 becomes (2+8) = 10

Y = 3142

Question 11 |

Only L is TRUE. | |

Only M is TRUE. | |

Only N is TRUE. | |

L, M and N are TRUE. |

Question 11 Explanation:

In the given statements observe that "not cheap" & cheap, "good & not good" are used.

So, given statement can be sub divided such that we can utilize the negation of this atomic statements.

Suppose, X is Good mobile and Y is cheap then

P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))

Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))

All these are contra positive.

All L, M, N are true.

So, given statement can be sub divided such that we can utilize the negation of this atomic statements.

Suppose, X is Good mobile and Y is cheap then

P: (Good(x) → ~cheap(x)) → (~good(x) ∨ ~cheap(x))

Q: cheap(x) → ¬good(x) ⟺ ((¬cheap(x) ∨ good(x)) ⟺ ¬good(x) ∨ ¬cheap(x))

All these are contra positive.

All L, M, N are true.

Question 12 |

Let X and Y be finite sets and f: X→Y be a function. Which one of the following statements is TRUE?

For any subsets A and B of X, |f(A ∪ B)| = |f(A)| + |f(B)| | |

For any subsets A and B of X, f(A ∩ B) = f(A) ∩ f(B) | |

For any subsets A and B of X, |f(A ∩ B)| = min{ |f(A)|, f|(B)|} |

Question 12 Explanation:

The function f: x→y.

We need to consider subsets of 'x', which are A & B (A, B can have common elements are exclusive).

Similarly S, T are subsets of 'y'.

To be a function, each element should be mapped with only one element.

(a) |f(A∪B)|=|f(A)|+|f(B)|

|{a,b,c}|∪|{c,d,e}| = |{a,b,c}| + |{c,d,e}|

|{a,b,c,d,e}| = 3+3

5 = 6 FALSE

(d) To get inverse, the function should be one-one & onto.

The above diagram fulfills it. So we can proceed with inverse.

f

f

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

2=2 TRUE

We need to consider subsets of 'x', which are A & B (A, B can have common elements are exclusive).

Similarly S, T are subsets of 'y'.

To be a function, each element should be mapped with only one element.

(a) |f(A∪B)|=|f(A)|+|f(B)|

|{a,b,c}|∪|{c,d,e}| = |{a,b,c}| + |{c,d,e}|

|{a,b,c,d,e}| = 3+3

5 = 6 FALSE

(d) To get inverse, the function should be one-one & onto.

The above diagram fulfills it. So we can proceed with inverse.

f

^{-1}(S∩T )=f^{-1}(S)∩f^{-1}(T)f

^{-1}(c)=f^{-1}({a,b,c})∩f^{-1}({c,d,e})2={1,2,3}∩{2,4,5}

2=2 TRUE

Question 13 |

Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L ≠ G and that the size of L is at least 4. The size of L is __________.

5 | |

6 | |

7 | |

8 |

Question 13 Explanation:

Lagrange's theorem, in the mathematics of group theory, states that for any finite group G, the
order (number of elements) of every subgroup H of G divides the order of G.

So, 15 is divided by {1, 3, 5, 15}.

As minimum is 4 and total is 15, we eliminate 1,3,15.

Answer is 5.

So, 15 is divided by {1, 3, 5, 15}.

As minimum is 4 and total is 15, we eliminate 1,3,15.

Answer is 5.

Question 14 |

Which one of the following statements is TRUE about every n × n matrix with only real eigenvalues?

If the trace of the matrix is positive and the determinant of the matrix is negative, at least one of its eigenvalues is negative. | |

If the trace of the matrix is positive, all its eigenvalues are positive. | |

If the determinant of the matrix is positive, all its eigenvalues are positive. | |

If the product of the trace and determinant of the matrix is positive, all its eigenvalues are positive. |

Question 14 Explanation:

The sum of the n eigenvalues of A is the same as the trace of A (that is, the sum of the diagonal
elements of A).

• The product of the n eigenvalues of A is the same as the determinant of A. •

A: Yes, for sum to be negative there should be atleast one negative number.

B: There can be one small negative number and remaining positive, where sum is positive.

C: Product of two negative numbers is positive. So, there no need of all positive eigen values.

D: There is no need for all eigen values to be positive, as product of two negative numbers is positive.

• The product of the n eigenvalues of A is the same as the determinant of A. •

A: Yes, for sum to be negative there should be atleast one negative number.

B: There can be one small negative number and remaining positive, where sum is positive.

C: Product of two negative numbers is positive. So, there no need of all positive eigen values.

D: There is no need for all eigen values to be positive, as product of two negative numbers is positive.

Question 15 |

If V

_{1}and V_{2}are 4-dimensional subspaces of a 6-dimensional vector space V, then the smallest possible dimension of V_{1}∩V_{2}is ______.2 | |

3 | |

4 | |

5 |

Question 15 Explanation:

In a 6 dimensional vector space, sub space of 4 dimensional subspaces V

For eg: a two dimensional vector space have x, y axis. For dimensional vector space, it have x, y, z axis.

In the same manner, 6 dimensional vector space has x, y, z, p, q, r (assume).

Any subspace of it, with 4 dimensional subspace consists any 4 of the above. Then their intersection will be atmost 2.

[{x,y,z,p} ∩ {r,q,p,z}] = #2

V

_{1}, V_{2}are provided. Then the V_{1}∩V_{2}?For eg: a two dimensional vector space have x, y axis. For dimensional vector space, it have x, y, z axis.

In the same manner, 6 dimensional vector space has x, y, z, p, q, r (assume).

Any subspace of it, with 4 dimensional subspace consists any 4 of the above. Then their intersection will be atmost 2.

[{x,y,z,p} ∩ {r,q,p,z}] = #2

V

_{1}∩ V_{2}= V_{1}+ V_{2}- V_{1}∪ V_{2}= 4+4+(-6) = 2Question 16 |

4 | |

5 | |

6 | |

7 |

Question 16 Explanation:

The graph x.Sinx from 0 to 2π is

We have |xSinx|,

We can observe that it is positive from 0 to π and negative in π to 2π.

To get positive value from π to 2π we put ‘-‘ sign in the (π, 2π)

We have |xSinx|,

We can observe that it is positive from 0 to π and negative in π to 2π.

To get positive value from π to 2π we put ‘-‘ sign in the (π, 2π)

Question 18 |

Full adder | |

Priority encoder | |

Multiplexor | |

Flip-flop |

Question 18 Explanation:

A 2x1 Multiplexer is most suitable for implementing the function.

x is the select line, I0 is b and I1 is a. The output line y = x a + x’ b

x is the select line, I0 is b and I1 is a. The output line y = x a + x’ b

Question 19 |

P1 | |

P2 | |

P3 | |

P4 |

Question 19 Explanation:

Clock period (CP) = max stage delay + overhead

So CP

CP

CP

CP

As frequency ∝ 1/C.P, so least clock period will give the highest peak clock frequency.

So, f

So CP

_{P1}=Max(1,2,2,1)=2nsCP

_{P2}=Max(1,1.5,1.5,1.5)=1.5nsCP

_{P3}=Max(0.5,1,1,0.6,1)=1nsCP

_{P4}=Max(0.5,0.5,1,1,1.1)=1.1nsAs frequency ∝ 1/C.P, so least clock period will give the highest peak clock frequency.

So, f

_{P3}=1/1ns=1GHzQuestion 20 |

The matrix A itself | |

Transpose of the matrix A | |

Adding 100 to the upper diagonal elements and subtracting 100 from lower diagonal elements of A | |

None of the above |

Question 20 Explanation:

Let be a small matrix.

For first row iteration, it get swapped and becomes

For second row iteration, it comes to the original position

=A

So, it is the same matrix A.

For first row iteration, it get swapped and becomes

For second row iteration, it comes to the original position

=A

So, it is the same matrix A.

Question 21 |

The minimum number of arithmetic operations required to evaluate the polynomial P(X) = X

^{5 }+ 4X^{3 }+ 6X + 5 for a given value of X, using only one temporary variable is ________.7 | |

8 | |

9 | |

10 |

Question 21 Explanation:

The minimum number of arithmetic operations required to evaluate

P(X)=x

=x(x

=x(x(x

=x(x(x(x

=x(x(x(x(x)+4))+6)+5

4 multiplications & 3 additions.

4 + 3 = 7

P(X)=x

^{5}+4x^{3}+6x+5=x(x

^{4}+4x^{2}+6)+5=x(x(x

^{3}+4x)+6)+5=x(x(x(x

^{2}+4))+6)+5=x(x(x(x(x)+4))+6)+5

4 multiplications & 3 additions.

4 + 3 = 7

Question 22 |

SQPTRWUV | |

SQPTUWRV | |

SQPTWUVR | |

SQPTRUWV |

Question 22 Explanation:

Inorder Traversal: Left, Root, Middle, Right.

Question 23 |

19 | |

20 | |

21 | |

22 |

Question 23 Explanation:

Note: We should not consider backtrack edges, it reduces recursion depth in stack.

So the maximum possible recursive depth will be 19.

Question 24 |

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

O(n ^{2}) | |

O(n log n) | |

Θ(n logn) | |

O(n ^{3}) |

Question 24 Explanation:

The Worst case time complexity of quick sort is O (n

^{2}). This will happen when the elements of the input array are already in order (ascending or descending), irrespective of position of pivot element in array.Question 25 |

3 | |

4 | |

5 | |

6 |

Question 25 Explanation:

The regular expression generate all the strings of length 0 , 1 and 2

{ϵ, a, b, aa, ab, ba, bb}

Let’s check all the string of length 3.

The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}

But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).

{ϵ, a, b, aa, ab, ba, bb}

Let’s check all the string of length 3.

The given regular expression generates {aaa, aab, aba, abb, baa, bba, bbb}

But it doesn’t generate the string “bab”, hence the shortest string not generated by regular expression has length 3 (string “bab”).

Question 26 |

Let Σ be a finite non-empty alphabet and let 2

^{Σ*}be the power set of Σ*. Which one of the following is**TRUE**?Both 2 ^{Σ*} and Σ* are countable | |

2 ^{Σ*} is countable and Σ* is uncountable | |

2 ^{Σ*} is uncountable and Σ* is countable | |

Both 2 ^{Σ*} and Σ* are uncountable |

Question 26 Explanation:

If = {0,1} then Σ* ={ϵ, 0, 1, 00, 01, 10, 11, 000,...............}

Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).

While 2

Since we can enumerate all the strings of Σ*, hence Σ* is countable (countable infinite).

While 2

^{Σ*}is uncountable, it has been already proved by using Diagonalization method.Question 27 |

One of the purposes of using intermediate code in compilers is to

make parsing and semantic analysis simpler. | |

improve error recovery and error reporting. | |

increase the chances of reusing the machine-independent code optimizer in other compilers. | |

improve the register allocation. |

Question 27 Explanation:

Intermediate code is generated after semantic analysis. The intermediate code is independent of machine. By converting source code to intermediate code a machine independent code optimizer may be written. Thus increase the chances of reusing the machine-independent code optimizer in other compilers.

Question 28 |

1 and 2 only | |

2 and 3 only | |

3 and 4 only | |

1 and 3 only |

Question 28 Explanation:

The statement, static allocation of all data areas by a compiler makes it impossible to implement recursion is true, as recursion requires memory allocation at run time, so it requires dynamic allocation of memory. Hence, Dynamic allocation of activation records is essential to implement recursion is also a true statement.

Question 29 |

In the context of modular software design, which one of the following combinations is desirable?

High cohesion and high coupling | |

High cohesion and low coupling | |

Low cohesion and high coupling | |

Low cohesion and low coupling |

Question 29 Explanation:

Note: Out of syllabus

Cohesion is a measure of internal strength within a module, whereas coupling is a measure of inter dependency among the modules. So in the context of modular software design there should be high cohesion and low coupling.

Cohesion is a measure of internal strength within a module, whereas coupling is a measure of inter dependency among the modules. So in the context of modular software design there should be high cohesion and low coupling.

Question 31 |

What is the optimized version of the relation algebra expression π

_{A1}(π_{A2}(σ_{F1}(σ_{F2}(r)))), where A1, A2 are sets of attributes in with A1 ⊂ A2 and F1, F2 are Boolean expressions based on the attributes in r?π _{A1} (σ_{(F1∧F2)} (r)) | |

π _{A1} (σ_{(F1∨F2)} (r)) | |

π _{A2} (σ_{(F1∧F2)} (r)) | |

π _{A2} (σ_{(F1∨F2)} (r)) |

Question 31 Explanation:

Since A1 ⊂ A2 will get only attribute A1 as it is in the outside. So we can remove project A2.

Two Selects with Boolean expression can be combined into one select with AND of two Boolean expressions.

Two Selects with Boolean expression can be combined into one select with AND of two Boolean expressions.

Question 32 |

A prime attribute of a relation scheme is an attribute that appears

in all candidate keys of R. | |

in some candidate key of R. | |

in a foreign key of R. | |

only in the primary key of R . |

Question 32 Explanation:

A prime attribute of a relation scheme R is an attribute that appears in some candidate keys of R. Need not to appear in all the candidate keys.

Ex: AB, BC, CD are candidate keys of R(ABCD). In the FDs set one attribute may not be part of all the FDs.

Ex: AB, BC, CD are candidate keys of R(ABCD). In the FDs set one attribute may not be part of all the FDs.

Question 33 |

In the following pairs of OSI protocol layer/sub-layer and its functionality, the

**INCORRECT**pair isNetwork layer and Routing | |

Data Link Layer and Bit synchronization | |

Transport layer and End-to-end process communication | |

Medium Access Control sub-layer and Channel sharing |

Question 33 Explanation:

(a) One of the main functionality of Network Layer is Routing. So Option (a) is CORRECT.

(b) Bit Synchronization is always handled by Physical Layer of OSI model but not Data Link Layer. So Option (b) is INCORRECT.

(c) End – to – End Process Communication is handled by Transport Layer. So Option (c) is CORRECT.

(d) MAC sub layer have 3 types of protocols (Random, Controlled and Channelized Access).

(b) Bit Synchronization is always handled by Physical Layer of OSI model but not Data Link Layer. So Option (b) is INCORRECT.

(c) End – to – End Process Communication is handled by Transport Layer. So Option (c) is CORRECT.

(d) MAC sub layer have 3 types of protocols (Random, Controlled and Channelized Access).

Question 34 |

A bit-stuffing based framing protocol uses an 8-bit delimiter pattern of 01111110. If the output bit-string after stuffing is 01111100101, then the input bit-string is

0111110100 | |

0111110101 | |

0111111101 | |

0111111111 |

Question 34 Explanation:

Given 8-bit delimiter pattern of 01111110.

Output Bit string after stuffing is 01111100101.

Output Bit string after stuffing is 01111100101.

Question 35 |

(i) only | |

(i) and (ii) only | |

(i) and (ii) only | |

(i), (ii) and (iii) |

Question 35 Explanation:

While an IP Datagram is transferring from one host to another host, TTL, Checksum and Fragmentation Offset will be changed.

Question 36 |

1 | |

2 | |

3 | |

4 |

Question 36 Explanation:

Lets take, 131.22.0.0/15 Its Net Mask is 255.254.0.0.

If we do AND operation between 255.254.0.0 and given IP 131.23.151.76, gives 131.22.0.0 which is matching with interface 1.

If we do AND operation between 255.254.0.0 and given IP 131.23.151.76, gives 131.22.0.0 which is matching with interface 1.

Question 37 |

Every host in an IPv4 network has a 1-second resolution real-time clock with battery backup. Each host needs to generate up to 1000 unique identifiers per second. Assume that each host has a globally unique IPv4 address. Design a 50-bit globally unique ID for this purpose. After what period (in seconds) will the identifiers generated by a host wrap around?

256 | |

257 | |

258 | |

259 |

Question 37 Explanation:

Given that each host has a globally unique IPv4 Address and we have to design 50 bit unique Id. So, 50 bit in the sense (32 + 18). So, It is clearly showing that IP Address (32 bit) followed by 18 bits.

1000 unique Ids ⇒ 1Sec

218 unique Ids ⇒ 218/1000=28=256

1000 unique Ids ⇒ 1Sec

218 unique Ids ⇒ 218/1000=28=256

Question 38 |

An IP router with a Maximum Transmission Unit (MTU) of 1500 bytes has received an IP packet of size 4404 bytes with an IP header of length 20 bytes. The values of the relevant fields in the header of the third IP fragment generated by the router for this packet are

MF bit: 0, Datagram Length: 1444; Offset: 370 | |

MF bit: 1, Datagram Length: 1424; Offset: 185 | |

MF bit: 1, Datagram Length: 1500; Offset: 370 | |

MF bit: 0, Datagram Length: 1424; Offset: 2960 |

Question 38 Explanation:

Number of packet fragments = ⌈ (total size of packet)/(MTU) ⌉

So Datagram with data 4404 byte fragmented into 3 fragments.

So Datagram with data 4404 byte fragmented into 3 fragments.

Question 39 |

Only S1 is conflict-serializable. | |

Only S2 is conflict-serializable. | |

Both S1 and S2 are conflict-serializable. | |

Neither S1 nor S2 is conflict-serializable. |

Question 39 Explanation:

S1:

No cycle, so schedule S1 is conflict serializable.

S2:

There is a cycle, so S2 is not conflict serializable.

No cycle, so schedule S1 is conflict serializable.

S2:

There is a cycle, so S2 is not conflict serializable.

Question 40 |

some dependent. | |

all dependents. | |

some of his/her dependents. | |

all of his/her dependents. |

Question 40 Explanation:

The inner query selects the employees whose age is less than or equal to at least one of his dependents. So, subtracting from the set of employees, gives employees whose age is greater than all of his dependents.

Question 41 |

A system contains three programs and each requires three tape units for its operation. The minimum number of tape units which the system must have such that deadlocks never arise is _________.

7 | |

8 | |

9 | |

10 |

Question 41 Explanation:

(3*2 tape units) + 1 tape unit = 7

Question 42 |

5.5 | |

5.6 | |

5.7 | |

5.8 |

Question 42 Explanation:

SRTF:

WT(Waiting Time) of P1 = 17-2 =15, WT of P2 = 2-2 = 0, WT of P3 = 6-3 = 3, WT of P4 = 12-8 = 4

Avg. waiting time = 15+0+3+4 /4 = 5.5

WT(Waiting Time) of P1 = 17-2 =15, WT of P2 = 2-2 = 0, WT of P3 = 6-3 = 3, WT of P4 = 12-8 = 4

Avg. waiting time = 15+0+3+4 /4 = 5.5

Question 43 |

Consider a paging hardware with a TLB. Assume that the entire page table and all the pages are in the physical memory. It takes 10 milliseconds to search the TLB and 80 milliseconds to access the physical memory. If the TLB hit ratio is 0.6, the effective memory access time (in milliseconds) is _________.

122 | |

123 | |

124 | |

125 |

Question 43 Explanation:

T

T

T

H

T

T

T

_{ave}=H_{1}×(T_{TLB}+T_{M})+(1-H_{1})×(T_{TLB}+2×T_{M})T

_{TLB}=time to search in TLB=10msT

_{M}=time to access physical memory=30msH

_{1}=TLB hit ratio=0.6T

_{ave}=0.6×(10+80)+(1-0.6)(10+2×80)T

_{ave}=0.6×90ms+0.4(170)msT

_{ave}=54ms+68ms=122msQuestion 44 |

6 and 6 | |

8 and 10 | |

9 and 12 | |

4 and 4 |

Question 44 Explanation:

Given the basic block as:

The normal DAG representation is:

But we can reduce

d = b+c & e = d-b

as e = b+c-b

e=c

and

e = d-b & a = e+b

a = d-b+b

a=d

So reconstruct the DAG as

So number of nodes = 6 & number of edges = 6.

The normal DAG representation is:

But we can reduce

d = b+c & e = d-b

as e = b+c-b

e=c

and

e = d-b & a = e+b

a = d-b+b

a=d

So reconstruct the DAG as

So number of nodes = 6 & number of edges = 6.

Question 45 |

Which one of the following problems is undecidable?

Deciding if a given context-free grammar is ambiguous. | |

Deciding if a given string is generated by a given context-free grammar. | |

Deciding if the language generated by a given context-free grammar is empty. | |

Deciding if the language generated by a given context-free grammar is finite. |

Question 45 Explanation:

The problem, whether a given CFG is ambiguous is undecidable, as we don’t have any algorithm which decides it.

We have a membership algorithm which decides that whether a given string is generated by a given context-free grammar. Similarly, the problems, whether the language generated by a given context-free grammar is empty and the language generated by a given context-free grammar is finite are decidable.

We have a membership algorithm which decides that whether a given string is generated by a given context-free grammar. Similarly, the problems, whether the language generated by a given context-free grammar is empty and the language generated by a given context-free grammar is finite are decidable.

Question 46 |

None of the languages | |

Only L _{1} | |

Only L _{1} and L_{2} | |

All the three languages |

Question 46 Explanation:

L

But in L

_{1}and L_{2}are DCFL, as we can design DPDA for them. For L_{1}, DPDA will first push all zero’s in stack and when one appears in string, it will pop zero for every one and at the end if input string as well as stack is empty then accept the string else reject the string. Similarly for L_{2}, DPDA will push all the string till it encounter the terminal “c” and once “c” appears in string, DPDA will ignore this “c” and then for every terminal in string (after “c”) it will pop one symbol from stack and match, if matched then pop next and continue. If didn’t match at any stage then reject the string. Since push and pop is clearly defined (i.e., every transition is deterministic), so both L_{1}and L_{2}is DCFL.But in L

_{3}, we cannot make DPDA for it, as we cannot locate the middle of string, so DPDA for L_{3}is not possible. It can be accepted by NPDA only, so L_{3}is CFL but not DCFL.Question 47 |

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers i, j with i < j. Given a shortcut i, j if you are at position i on the number line, you may directly move to j. Suppose T(k) denotes the smallest number of steps needed to move from k to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let y and z be such that T(9) = 1 + min(T(y),T(z)). Then the value of the product yz is _____.

150 | |

151 | |

152 | |

153 |

Question 47 Explanation:

T(k) is the smallest no. of steps needed to move from k to 100.

Now, it is given that

T(9) = 1 + min(T(y),T(z))

where,

T(y) = steps from y to 100

T(z) = steps from z to 100

where y and z are two possible values that can be reached from 9.

One number that can be reached from 9 is 10. Another no. is 15, the shortcut path from 9, as given in the question.

∴ The value of 'y' and 'z' are 10 and 15.

So, y × z = 10 × 15 = 150

Now, it is given that

T(9) = 1 + min(T(y),T(z))

where,

T(y) = steps from y to 100

T(z) = steps from z to 100

where y and z are two possible values that can be reached from 9.

One number that can be reached from 9 is 10. Another no. is 15, the shortcut path from 9, as given in the question.

∴ The value of 'y' and 'z' are 10 and 15.

So, y × z = 10 × 15 = 150

Question 48 |

NP-Complete. | |

solvable in polynomial time by reduction to directed graph reachability. | |

solvable in constant time since any input instance is satisfiable. | |

NP-hard, but not NP-complete. |

Question 48 Explanation:

Note: Out of Syllabus.

→ 2-satisfiability problem are typically expressed as Boolean formulas of a special type, called conjunctive normal form (2-CNF) or Krom formulas.

→ Alternatively, they may be expressed as a special type of directed graph, the implication graph, which expresses the variables of an instance and their negations as vertices in a graph, and constraints on pairs of variables as directed edges.

→ Both of these kinds of inputs may be solved in linear time, either by a method based on backtracking or by using the strongly connected components of the implication graph.

→ Resolution, a method for combining pairs of constraints to make additional valid constraints, also leads to a polynomial time solution.

→ The 2-satisfiability problems provide one of two major subclasses of the conjunctive normal form formulas that can be solved in polynomial time; the other of the two subclasses is Horn-satisfiability.

→ 2-satisfiability problem are typically expressed as Boolean formulas of a special type, called conjunctive normal form (2-CNF) or Krom formulas.

→ Alternatively, they may be expressed as a special type of directed graph, the implication graph, which expresses the variables of an instance and their negations as vertices in a graph, and constraints on pairs of variables as directed edges.

→ Both of these kinds of inputs may be solved in linear time, either by a method based on backtracking or by using the strongly connected components of the implication graph.

→ Resolution, a method for combining pairs of constraints to make additional valid constraints, also leads to a polynomial time solution.

→ The 2-satisfiability problems provide one of two major subclasses of the conjunctive normal form formulas that can be solved in polynomial time; the other of the two subclasses is Horn-satisfiability.

Question 49 |

Suppose we have a balanced binary search tree T holding n numbers. We are given two numbers L and H and wish to sum up all the numbers in T that lie between L and H. Suppose there are m such numbers in T. If the tightest upper bound on the time to compute the sum is O(n

^{a}log^{b}n + m^{c}log^{d}n), the value of a + 10b + 100c + 1000d is ____.110 | |

111 | |

112 | |

113 |

Question 49 Explanation:

It takes (log n) time to determine numbers n

1. n

2. n

Since there are m elements between n

So time complexity is O(log n+m)

So the given expression becomes O(n

And a+10b+100c+1000d=0+10*1+100*1+1000*1=10+100=110

Because a=0, b=1, c=1 and d=0

_{1}and n_{2}in balanced binary search tree T such that1. n

_{1}is the smallest number greater than or equal to L and there is no predecessor n_{1}' of >n_{1}such that n_{1}' is equal to n_{1}.2. n

_{2}2' of n_{2}such that is equal to n_{2}.Since there are m elements between n

_{1}and n_{2}, it takes ‘m’ time to add all elements between n_{1}and n_{2}.So time complexity is O(log n+m)

So the given expression becomes O(n

^{0}log'n+m'log^{0}n)And a+10b+100c+1000d=0+10*1+100*1+1000*1=10+100=110

Because a=0, b=1, c=1 and d=0

Question 50 |

Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?

(97×97×97)/100 ^{3} | |

(99×98×97)/100 ^{3} | |

(97×96×95)/100 ^{3} | |

(97×96×95)/(3!×100 ^{3}) |

Question 50 Explanation:

Given Hash table consists of 100 slots.

They are picked with equal probability of Hash function since it is uniform hashing.

So to avoid the first 3 slots to be unfilled

=97/100*97/100*97/100=((97*97*97))⁄100

They are picked with equal probability of Hash function since it is uniform hashing.

So to avoid the first 3 slots to be unfilled

=97/100*97/100*97/100=((97*97*97))⁄100

^{3}Question 51 |

number of internal nodes in the tree. | |

height of the tree. | |

number of nodes without a right sibling in the tree. | |

number of leaf nodes in the tree. |

Question 51 Explanation:

The key to solving such questions is to understand or detect where/by what condition the value (or the counter) is getting incremented each time.

Here, that condition is if (tree → leftMostchild = = Null)

⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)

⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).

⇒ Which means the node under consideration is a leaf node.

⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.

Here, that condition is if (tree → leftMostchild = = Null)

⇒ Which means if there is no left most child of the tree (or the sub-tree or the current node as called in recursion)

⇒ Which means there is no child to that particular node (since if there is no left most child, there is no child at all).

⇒ Which means the node under consideration is a leaf node.

⇒ The function recursively counts, and adds to value, whenever a leaf node is encountered. ⇒ The function returns the number of leaf nodes in the tree.

Question 52 |

It will run into an infinite loop when x is not in listA. | |

It is an implementation of binary search. | |

It will always find the maximum element in listA. | |

It will return −1 even when x is present in listA. |

Question 52 Explanation:

From the above code, we can identify

k = (i+j)/2;

where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.

So it is an implementation of Binary search.

k = (i+j)/2;

where k keeps track of current middle element & i, j keeps track of left & right children of current subarray.

So it is an implementation of Binary search.

Question 53 |

An instruction pipeline has five stages, namely, instruction fetch (IF), instruction decode and register fetch (ID/RF), instruction execution (EX), memory access (MEM), and register writeback (WB) with stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns, respectively (ns stands for nanoseconds). To gain in terms of frequency, the designers have decided to split the ID/RF stage into three stages (ID, RF1, RF2) each of latency 2.2/3 ns. Also, the EX stage is split into two stages (EX1, EX2) each of latency 1 ns. The new design has a total of eight pipeline stages. A program has 20% branch instructions which execute in the EX stage and produce the next instruction pointer at the end of the EX stage in the old design and at the end of the EX2 stage in the new design. The IF stage stalls after fetching a branch instruction until the next instruction pointer is computed. All instructions other than the branch instruction have an average CPI of one in both the designs. The execution times of this program on the old and the new design are P and Q nanoseconds, respectively. The value of P/Q is __________.

1.54 | |

1.55 | |

1.56 | |

1.57 |

Question 53 Explanation:

There are five stages:

Instruction Fetch (IF),

instruction decode and register fetch (ID/RF),

Instruction execution (EX),

Memory access (MEM),

and register writeback (WB)

P old design:

With stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns

Cycle time = MAX(1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2nsec

Branch penalty = 3-1 = 2 because the next instruction pointer at the end of the EX stage(which is 3rd stage) in the old design

AVG instruction execution time is

P=T

=(1+0.20*2)2.2

P =3.08 nsec

Q new design:

ID/RF stage is split into three stages (ID, RF1, RF2) each of latency (2.2)/3 ns = 0.73ns.

The EX stage is split into two stages (EX1, EX2) each of latency 1 ns.

The new design has a total of eight pipeline stages.

Time of stages in new design ={1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns}

Cycle time = MAX( 1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns) =1nsec

Branch penalty = 6-1 = 5 because the next instruction pointer at the end of the EX2 stage(which is 6th stage) in the new design.

AVG instruction execution time is

Q = T

= (1+0.20*5)1

Q = 2 nsec

Therefore, P/Q=3.08/2 =1.54

Instruction Fetch (IF),

instruction decode and register fetch (ID/RF),

Instruction execution (EX),

Memory access (MEM),

and register writeback (WB)

P old design:

With stage latencies 1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns

Cycle time = MAX(1 ns, 2.2 ns, 2 ns, 1 ns, and 0.75 ns) = 2.2nsec

Branch penalty = 3-1 = 2 because the next instruction pointer at the end of the EX stage(which is 3rd stage) in the old design

AVG instruction execution time is

P=T

_{avg}=(1+no. of stalls*branch penalty)*cycle time=(1+0.20*2)2.2

P =3.08 nsec

Q new design:

ID/RF stage is split into three stages (ID, RF1, RF2) each of latency (2.2)/3 ns = 0.73ns.

The EX stage is split into two stages (EX1, EX2) each of latency 1 ns.

The new design has a total of eight pipeline stages.

Time of stages in new design ={1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns}

Cycle time = MAX( 1ns, 0.73ns, 0.73ns, 0.73ns , 1ns, 1ns, 1ns, and 0.75ns) =1nsec

Branch penalty = 6-1 = 5 because the next instruction pointer at the end of the EX2 stage(which is 6th stage) in the new design.

AVG instruction execution time is

Q = T

_{avg}=(1+no. of stalls*branch penality)*cycle time= (1+0.20*5)1

Q = 2 nsec

Therefore, P/Q=3.08/2 =1.54

Question 54 |

The memory access time is 1 nanosecond for a read operation with a hit in cache, 5 nanoseconds for a read operation with a miss in cache, 2 nanoseconds for a write operation with a hit in cache and 10 nanoseconds for a write operation with a miss in cache. Execution of a sequence of instructions involves 100 instruction fetch operations, 60 memory operand read operations and 40 memory operand write operations. The cache hit-ratio is 0.9. The average memory access time (in nanoseconds) in executing the sequence of instructions is __________.

1.68 | |

1.69 | |

1.70 | |

1.71 |

Question 54 Explanation:

Total instruction=100 instruction fetch operation +60 memory operand read operation +40 memory operand write op

=200 instructions (operations)

Time taken for fetching 100 instructions (equivalent to read) = 90*1ns + 10*5ns = 140ns

Memory operand Read operations = 90% (60)*1ns + 10% (60) × 5ns = 54ns + 30 ns = 84ns

Memory operands Write operations time = 90% (40)*2ns + 10% (40)*10ns

= 72ns + 40ns = 112ns

Total time taken for executing 200 instructions = 140 + 84 + 112 = 336ns

∴ Average memory access time =336 ns/200=1.68ns

=200 instructions (operations)

Time taken for fetching 100 instructions (equivalent to read) = 90*1ns + 10*5ns = 140ns

Memory operand Read operations = 90% (60)*1ns + 10% (60) × 5ns = 54ns + 30 ns = 84ns

Memory operands Write operations time = 90% (40)*2ns + 10% (40)*10ns

= 72ns + 40ns = 112ns

Total time taken for executing 200 instructions = 140 + 84 + 112 = 336ns

∴ Average memory access time =336 ns/200=1.68ns

Question 56 |

I only | |

II only | |

Both I and II | |

Neither I nor II |

Question 56 Explanation:

Note: Numerical methods are out of syllabus for the GATE -CS.

Question 58 |

Let S be a sample space and two mutually exclusive events A and B be such that A∪B = S. If P(∙) denotes the probability of the event, the maximum value of P(A)P(B) is __________.

0.25 | |

0.26 | |

0.27 | |

0.28 |

Question 58 Explanation:

We know that

P(A∪B) = P(A) + P(B) + P(A∩B) = 1 →①

But, as A and B are mutually exclusive events

P(A∩B) = 0

∴ P(A∪B) = P(A) + P(B) = 1 →②

Arithmetic mean of two numbers ≥ Geometric mean of those two numbers

(P(A)+P(B))/2≥√(P(A)∙P(B))

1/2≥√(P(A)∙P(B)) (∵from ②)

Squaring on both sides

1/4≥P(A)∙P(B)

P(A)∙P(B)≤1/4

∴ Maximum value of P(A)P(B) = 1/4 = 0.25

P(A∪B) = P(A) + P(B) + P(A∩B) = 1 →①

But, as A and B are mutually exclusive events

P(A∩B) = 0

∴ P(A∪B) = P(A) + P(B) = 1 →②

Arithmetic mean of two numbers ≥ Geometric mean of those two numbers

(P(A)+P(B))/2≥√(P(A)∙P(B))

1/2≥√(P(A)∙P(B)) (∵from ②)

Squaring on both sides

1/4≥P(A)∙P(B)

P(A)∙P(B)≤1/4

∴ Maximum value of P(A)P(B) = 1/4 = 0.25

Question 59 |

P, Q and R are true | |

Only Q and R are true | |

Only P and Q are true | |

Only R is true |

Question 59 Explanation:

f:{0,1,…,2014}→{0,1,…,2014} and f(f(i))=i

So f(i)should be resulting only {0, 1, …2014}

So, every element in range has a result value to domain. This is onto. (Option R is correct)

We have ‘2015’ elements in domain.

So atleast one element can have f(i) = i,

so option ‘Q’ is also True.

∴ Q, R are correct.

So f(i)should be resulting only {0, 1, …2014}

So, every element in range has a result value to domain. This is onto. (Option R is correct)

We have ‘2015’ elements in domain.

So atleast one element can have f(i) = i,

so option ‘Q’ is also True.

∴ Q, R are correct.

Question 60 |

4 | |

5 | |

6 | |

7 |

Question 60 Explanation:

We know

a*a

1. x*x=e So x

2. y*y=e So y

4. (y*x)*(y*x)=x*y*y*x=x*x*e=e So (y*x)

In ③, ④

x*y,y*x has same inverse, there should be unique inverse for each element.

x*y=y*x (even with cumulative law, we can conclude)

So {x, y, e, x*y} are element of Group.

a*a

^{-1}= e1. x*x=e So x

^{-1}is x ⇒ x is element of Group2. y*y=e So y

^{-1}= y ⇒ y is element of Group4. (y*x)*(y*x)=x*y*y*x=x*x*e=e So (y*x)

^{-1}=(y*x)In ③, ④

x*y,y*x has same inverse, there should be unique inverse for each element.

x*y=y*x (even with cumulative law, we can conclude)

So {x, y, e, x*y} are element of Group.

Question 61 |

If G is a forest with n vertices and k connected components, how many edges does G have?

⌊n/k⌋ | |

⌈n/k⌉ | |

n–k | |

n-k+1 |

Question 61 Explanation:

Suppose, if each vertex is a component, then k=n, then there will not be any edges among them Replace the same in options

Option 1, 2 will give answer 1. (i.e. one edge among them),

Option 3: n-k = 0 edges.

Option 4: n-k+1 : 1edge, which is false.

Option 1, 2 will give answer 1. (i.e. one edge among them),

Option 3: n-k = 0 edges.

Option 4: n-k+1 : 1edge, which is false.

Question 62 |

Let δ denote the minimum degree of a vertex in a graph. For all planar graphs on n vertices with δ ≥ 3, which one of the following is

**TRUE**?In any planar embedding, the number of faces is at least n/2+ 2 | |

In any planar embedding, the number of faces is less than n/2+ 2 | |

There is a planar embedding in which the number of faces is less than n/2+ 2 | |

There is a planar embedding in which the number of faces is at most n/(δ+1) |

Question 62 Explanation:

Euler’s formula:

v – e + f = 2 →①

Point ① degree of each vertex is minimum ‘3’.

3×n≥2e

e≤3n/2

From ①

n-3n/2+f=2⇒

v – e + f = 2 →①

Point ① degree of each vertex is minimum ‘3’.

3×n≥2e

e≤3n/2

From ①

n-3n/2+f=2⇒

Question 63 |

The CORRECT formula for the sentence, “not all rainy days are cold” is

∀d (Rainy(d) ∧∼Cold(d)) | |

∀d (∼Rainy(d) → Cold(d)) | |

∃d (∼Rainy(d) → Cold(d)) | |

∃d (Rainy(d) ∧∼Cold(d)) |

Question 63 Explanation:

Not all rainy days are cold

= ∼[∀rainy days are cold]

= ∼[∀ days (rainy days ⇒ cold days]

= ∃ days[∼(cold days ∨ ∼rainy days)]

= ∃ days[rainy days ∧ ∼cold days]

= ∼[∀rainy days are cold]

= ∼[∀ days (rainy days ⇒ cold days]

= ∃ days[∼(cold days ∨ ∼rainy days)]

= ∃ days[rainy days ∧ ∼cold days]

Question 64 |

Names of all the employees with at least one of their customers having a ‘GOOD’ rating. | |

Names of all the employees with at most one of their customers having a ‘GOOD’ rating. | |

Names of all the employees with none of their customers having a ‘GOOD’ rating. | |

Names of all the employees with all their customers having a ‘GOOD’ rating. |

Question 64 Explanation:

The inner query i.e., ② represents all customers having other than ‘GOOD’ while the entire query represents name of all employees with all their customers having a ‘good rating’.

There are 65 questions to complete.