## Gate 2012

Question 1 |

Both I _{1} and I_{2} are correct inferences | |

I _{1} is correct but I_{2} is not a correct inference | |

I _{1} is not correct but I_{2} is a correct inference | |

Both I _{1} and I_{2} are not correct inferences |

Question 1 Explanation:

I

The cricket match was played.

Let p = it rains

q = playing cricket/ match played

If (it rains) then (the match will not be played)

p ⇒ (∼q)

Inference: There was no rain. (i.e., p = F)

So for any F ⇒ (∼q) is true.

So this inference is valid.

I

It did not rain.

p ⇒ (∼q)

Inference: The cricket match was played.

q = T

p ⇒ (∼q)

p ⇒ (∼T)

p ⇒ F

This is false for p = T, so this is not true.

_{1}: If it rains then the cricket match will not be played.The cricket match was played.

Let p = it rains

q = playing cricket/ match played

If (it rains) then (the match will not be played)

p ⇒ (∼q)

Inference: There was no rain. (i.e., p = F)

So for any F ⇒ (∼q) is true.

So this inference is valid.

I

_{2}: If it rains then the cricket match will not be played.It did not rain.

p ⇒ (∼q)

Inference: The cricket match was played.

q = T

p ⇒ (∼q)

p ⇒ (∼T)

p ⇒ F

This is false for p = T, so this is not true.

Question 2 |

Which of the following is

**TRUE**?Every relation in 3NF is also in BCNF | |

A relation R is in 3NF if every non-prime attribute of R is fully functionally dependent on every key of R | |

Every relation in BCNF is also in 3NF | |

No relation can be in both BCNF and 3NF |

Question 2 Explanation:

BCNF is a stronger version 3NF. So straight from definition of BCNF every relation in BCNF will also be in 3NF.

Question 3 |

No Choice | |

Choice A | |

Program gives no output as it is erroneous |

Question 3 Explanation:

Everything in the switch will be executed, because there is no break; statement after case ‘A’. So it executes all the subsequent statements until it find a break;

So,

→ Choice A

→ Choice B. No choice. Is the output.

So,

→ Choice A

→ Choice B. No choice. Is the output.

Question 4 |

Assuming P ≠ NP, which of the following is

**TRUE**?NP-complete = NP | |

NP-complete ∩ P = ∅ | |

NP-hard = NP | |

P = NP-complete |

Question 4 Explanation:

Note: Out of syllabus.

The definition of NP-complete is,

A decision problem p is NP-complete if:

1. p is in NP, and

2. Every problem in NP is reducible to p in polynomial time.

It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .

This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.

Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.

The definition of NP-complete is,

A decision problem p is NP-complete if:

1. p is in NP, and

2. Every problem in NP is reducible to p in polynomial time.

It is given that assume P ≠ NP , hence NP-complete ∩ P = ∅ .

This is due to the fact that, if NP-complete ∩ P ≠ ∅ i.e. there are some problem (lets say problem P1) which is in P and in NP-complete also, then it means that P1 (NP-complete problem) can be solved in polynomial time also (as it is also in P class) and this implies that every NP problem can be solve in polynomial time, as we can convert every NP problem into NP-complete problem in polynomial time.

Which means that we can convert every NP problem to P1 and solve in polynomial time and hence P = NP, which is contradiction to the given assumption that P ≠ NP.

Question 5 |

The worst case running time to search for an element in a balanced binary search tree with n2

^{n}elements isΘ (n log n) | |

Θ (n2 ^{n}) | |

Θ (n) | |

Θ (log n) |

Question 5 Explanation:

→ Worst case running time to search for an element in a balanced binary search tree of ‘n’ elements is (log n).

→ No of elements = n.2

= (log n + log 2

= (log n + n log 2)

= O(n)

→ No of elements = n.2

^{n}then search time = (log n.2^{n})= (log n + log 2

^{n})= (log n + n log 2)

= O(n)

Question 6 |

X | |

X + Y | |

X ⊕ Y | |

Y |

Question 6 Explanation:

f(X,Y)=XY’ + XY = X(Y’ + Y) = X

Question 7 |

The decimal value 0.5 in IEEE single precision floating point representation has

fraction bits of 000…000 and exponent value of 0 | |

fraction bits of 000…000 and exponent value of −1 | |

fraction bits of 100…000 and exponent value of 0 | |

no exact representation |

Question 7 Explanation:

(0.5)

So, value of the exponent = -1

and

fraction is 000…000 (Implicit representation)

_{10}= (1.0)_{2}× 2^{–1}So, value of the exponent = -1

and

fraction is 000…000 (Implicit representation)

Question 8 |

3 | |

4 | |

7 | |

8 |

Question 8 Explanation:

The no. of child process created = 2

7 are child processes.

^{n}-1 = 2^{3}-1 = 7 (where n is number of fork() statements)7 are child processes.

Question 9 |

Consider the function f(x) = sin(x) in the interval x ∈ [π/4, 7π/4]. The number and location(s) of the local minima of this function are

One, at π/2 | |

One, at 3π/2 | |

Two, at π/2 and 3π/2 | |

Two, at π/4 and 3π/2 |

Question 9 Explanation:

f(x) = sin x

f’(x) = cos x

[just consider the given interval (π/4, 7π/4)]

f'(x) = 0 at π/2, 3π/2

To get local minima f ’’(x) > 0, f ’’(x) = - sin x

f ’’(x) at π/2, 3π/2

f ’’(x) = -1< 0 local maxima

f ’’ (3π/2) = 1 > 0 this is local minima

In the interval [π/4, π/2] the f(x) is increasing, so f(x) at π/4 is also a local minima.

So there are two local minima for f(x) at π/4, 3π/2.

f’(x) = cos x

[just consider the given interval (π/4, 7π/4)]

f'(x) = 0 at π/2, 3π/2

To get local minima f ’’(x) > 0, f ’’(x) = - sin x

f ’’(x) at π/2, 3π/2

f ’’(x) = -1< 0 local maxima

f ’’ (3π/2) = 1 > 0 this is local minima

In the interval [π/4, π/2] the f(x) is increasing, so f(x) at π/4 is also a local minima.

So there are two local minima for f(x) at π/4, 3π/2.

Question 10 |

The protocol data unit (PDU) for the application layer in the Internet stack is

Segment | |

Datagram | |

Message | |

Frame |

Question 10 Explanation:

The PDU for Data Link layer, Network layer, Transport layer and Application layer are frame, datagram, segment and message respectively.

Question 11 |

Let be the 2×2 matrix with elements a

_{11}= a_{12}= a_{21}= +1 and a_{22}= -1. Then the eigenvalues of the matrix A^{19}are1024 and -1024 | |

1024√2 and -1024√2 | |

4√2 and -4√2 | |

512√2 and -512√2 |

Question 11 Explanation:

a

The 2×2 matrix =

Cayley Hamilton theorem:

If matrix A has ‘λ’ as eigen value, A

Eigen value of

|A-λI| = 0

-(1-λ)(1+λ)-1=0

-(1-λ

-1=1-λ

λ

λ=±√2

A

=512√2

_{11}=a_{12}=a_{21}=1, a_{22}=-1The 2×2 matrix =

Cayley Hamilton theorem:

If matrix A has ‘λ’ as eigen value, A

^{n}has eigen value as λ^{n}.Eigen value of

|A-λI| = 0

-(1-λ)(1+λ)-1=0

-(1-λ

^{2})-1=0-1=1-λ

^{2}λ

^{2}=2λ=±√2

A

^{19}has (√2)^{19}=2^{9}×√2 (or) (-√2)^{19}=-512√2=512√2

Question 12 |

∅ | |

{ε} | |

a* | |

{a ,ε} |

Question 12 Explanation:

The Σ= {a} and the given NFA accepts the strings {a, aa, aaa, aaaa, ……….} i.e. the language accepted by the NFA can be represented by the regular expression: {a

Hence the complement of language is: {a* − a

^{+}}Hence the complement of language is: {a* − a

^{+}} = {ϵ}Question 13 |

∃x (real(x) ∨ rational(x)) | |

∀x (real(x) → rational(x)) | |

∃x (real(x) ∧ rational(x)) | |

∃x (rational(x) → real(x)) |

Question 13 Explanation:

∃x (real(x) ∧ rational(x))

(A) ∃x(real(x) ∨ rational(x))

means There exists some number, which are either real or rational.

(B) ∀x (real(x)→rational(x))

If a number is real then it is rational.

(D) ∃x (rational(x)→real(x))

There exists a number such that if it is rational then it is real.

Question 14 |

Given the basic ER and relational models, which of the following is

**INCORRECT**?An attribute of an entity can have more than one value | |

An attribute of an entity can be composite | |

In a row of a relational table, an attribute can have more than one value | |

In a row of a relational table, an attribute can have exactly one value or a NULL value |

Question 14 Explanation:

Option (A): In ER-model, multivalued attribute of an entity can have more than one value.

Option (B): In ER model, the attribute which can be further broken down into some other attributes is called composite attribute.

Option (C): In Relational model, the intersection of one row and column should contain only one value. So, option (C) is INCORRECT.

Option (D): In Relational model, the intersection of one row and column should contain either exactly one value or NULL.

Option (B): In ER model, the attribute which can be further broken down into some other attributes is called composite attribute.

Option (C): In Relational model, the intersection of one row and column should contain only one value. So, option (C) is INCORRECT.

Option (D): In Relational model, the intersection of one row and column should contain either exactly one value or NULL.

Question 15 |

P and R | |

P and S | |

Q and R | |

Q and S |

Question 15 Explanation:

The SQL GROUP BY clause is used in collaboration with the SELECT statement to arrange identical data into groups. This GROUP BY clause follows the WHERE clause in a SELECT statement and precedes the ORDER BY clause. The attributes used in GROUP BY clause must present in SELECT statement.

The HAVING Clause enables you to specify conditions that filter which group results appear in the results. The WHERE clause places conditions on the selected columns, whereas the HAVING clause places conditions on groups created by the GROUP BY clause. So, we cannot use HAVING clause without GROUP BY clause.

The HAVING Clause enables you to specify conditions that filter which group results appear in the results. The WHERE clause places conditions on the selected columns, whereas the HAVING clause places conditions on groups created by the GROUP BY clause. So, we cannot use HAVING clause without GROUP BY clause.

Question 16 |

The recurrence relation capturing the optimal execution time of the Towers of Hanoi problem with n discs is

T(n) = 2T(n - 2) + 2 | |

T(n) = 2T(n - 1) + n | |

T(n) = 2T(n/2) + 1 | |

T(n) = 2T(n - 1) + 1 |

Question 16 Explanation:

The recurrence equation for given recurrence function is

T(n) = 2T(n – 1) + 1

= 2 [2T(n – 2) + 1] + 1

= 2

⋮

= 2

n – k = 1

= 2

= 2

= 2

≌ O(2

T(n) = 2T(n – 1) + 1

= 2 [2T(n – 2) + 1] + 1

= 2

^{2}T(n – 2) + 3⋮

= 2

^{k}T( n – k) + (2^{k}– 1)n – k = 1

= 2

^{n-1}T(1) + (2^{n-1}– 1)= 2

^{n-1}+ 2^{n-1}– 1= 2

^{n}– 1≌ O(2

^{n})Question 17 |

Let G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

3 | |

4 | |

5 | |

6 |

Question 17 Explanation:

If the graph is planar, then we have to consider Euler’s formula

v-e+f=2

Given 10 vertices & 15 edges

10-15+f=2

f=2+15-10

f=7

There will be an unbounded face always. So, number of faces = 6.

v-e+f=2

Given 10 vertices & 15 edges

10-15+f=2

f=2+15-10

f=7

There will be an unbounded face always. So, number of faces = 6.

Question 18 |

Let W(n) and A(n) denote respectively, the worst case and average case running time of an algorithm executed on an input of size n. Which of the following is

**ALWAYS TRUE**?A(n) = Ω (W(n)) | |

A(n) = Θ (W(n)) | |

A(n) = O (W(n)) | |

A(n) = o (W(n)) |

Question 18 Explanation:

The average case time can be lesser than or even equal to the worst case.

So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).

A(n)=O(W(n))

Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .

So, A(n) would be upper bounded by W(n) and it will not be strict upper bound as it can even be same (e.g. Bubble Sort and merge sort).

A(n)=O(W(n))

Note: Option A is wrong because A(n) is not equal to Ω(w(n)) .

Question 19 |

The amount of ROM needed to implement a 4 bit multiplier is

64 bits | |

128 bits | |

1 Kbits | |

2 Kbits |

Question 19 Explanation:

To implement a 4-bit multiplier we need to store all the possible combinations of 2

Hence option D is the answer.

^{4}x 2^{4}inputs and their corresponding 8 output bits. The total ROM size needed = 2^{8}x 8 bits = 2^{11}bits = 2 Kbits.Hence option D is the answer.

Question 20 |

Register renaming is done in pipelined processors

as an alternative to register allocation at compile time | |

for efficient access to function parameters and local variables | |

to handle certain kinds of hazards | |

as part of address translation |

Question 20 Explanation:

Register renaming is used to eliminate hazards that arise due to WAR (Write After Read) and WAW(Write After Write) dependencies. Hence option C is the answer.

Question 21 |

Consider a random variable X that takes values +1 and −1 with probability 0.5 each. The values of the cumulative distribution function F(x) at x = −1 and +1 are

0 and 0.5 | |

0 and 1 | |

0.5 and 1 | |

0.25 and 0.75 |

Question 21 Explanation:

Cumulative probability is sum of probabilities of all other points till the given value.

The sum of probabilities at x=1, x=-1 itself is 0.5+0.5 =1. It is evident that, there is no probability for any other values.

The F(x=-1) is 0.5 as per given probabilities and

F(x=1) = sum of F(x=-1) +F(x=0)=...f(X=1) = 0.5 +0.5 =1

The sum of probabilities at x=1, x=-1 itself is 0.5+0.5 =1. It is evident that, there is no probability for any other values.

The F(x=-1) is 0.5 as per given probabilities and

F(x=1) = sum of F(x=-1) +F(x=0)=...f(X=1) = 0.5 +0.5 =1

Question 22 |

Which of the following transport layer protocols is used to support electronic mail?

SMTP | |

IP | |

TCP | |

UDP |

Question 22 Explanation:

TCP is used in transport layer to carry out mail which is initiated by application layer protocol SMTP.

Question 23 |

In the IPv4 addressing format, the number of networks allowed under Class C addresses is

2 ^{14} | |

2 ^{7} | |

2 ^{21} | |

2 ^{24} |

Question 23 Explanation:

For class C address, size of network field is 24 bits. But first 3 bits are fixed as 110; hence total number of networks possible is 2

^{21}.Question 24 |

1, 2, 3, 4 | |

1, 2 | |

2, 3, 4 | |

3, 4 |

Question 24 Explanation:

The statement “Does a given program ever produce an output?” is same as the statement “Does a Turing Machine will halt for any arbitrary string?”, which is nothing but the “halting problem of Turing Machine”, hence statement 1 is undecidable.

Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.

Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.

Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.

Context free languages are not closed under complement operation, so compliment of CFL may or may not be CFL. Hence statement 2 is also undecidable.

Complement of Regular languages is also regular. Since a DFA that accepts the complement of L, i.e. ∑* – L, can be obtained by swapping its final states with its non-final states and vice-versa. Hence it is decidable and if L is a regular language, then, L must also be regular.

Recursive languages are closed under complement, so if L is a recursive language then L must also be recursive, hence it is decidable.

Question 25 |

1, 2 and 3 | |

2, 3 and 4 | |

1, 2 and 4 | |

1, 3 and 4 |

Question 25 Explanation:

L* will contain all those strings which can be obtained by any combination (and repetition) of the strings in language i,e, from L= {ab, aa, baa}

String 1: abaabaaabaa : ab aa baa ab aa

String 2: aaaabaaaa : aa aa baa aa

String 3: baaaaabaaaab: baa aa ab aa aa b, because of the last “b” the string cannot belong to L*.

String 4: baaaaabaa : baa aa ab aa

String 1: abaabaaabaa : ab aa baa ab aa

String 2: aaaabaaaa : aa aa baa aa

String 3: baaaaabaaaab: baa aa ab aa aa b, because of the last “b” the string cannot belong to L*.

String 4: baaaaabaa : baa aa ab aa

Question 26 |

Question 26 Explanation:

Original graph:

(A) 3 cycle graph not in original one.

(B) Correct 5 cycles & max degree is 4.

(C) Original graph doesn’t have a degree of 3.

(D) 4 cycles not in original one.

(A) 3 cycle graph not in original one.

(B) Correct 5 cycles & max degree is 4.

(C) Original graph doesn’t have a degree of 3.

(D) 4 cycles not in original one.

Question 27 |

a serializable schedule | |

a schedule that is not conflict serializable | |

a conflict serializable schedule | |

a schedule for which a precedence graph cannot be drawn |

Question 27 Explanation:

The above schedule is not conflict serializable.

Question 28 |

The bisection method is applied to compute a zero of the function f(x) = x

^{4}- x^{3}- x^{2}- 4 in the interval [1,9]. The method converges to a solution after ________ iterations.1 | |

3 | |

5 | |

7 |

Question 28 Explanation:

Note: Numerical methods are not present in the GATE CS syllabus anymore.

Question 29 |

Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is

**TRUE**?T' = T with total weight t' = t ^{2} | |

T' = T with total weight t' | |

T' ≠ T but total weight t' = t ^{2} | |

None of the above |

Question 29 Explanation:

Let graph G be

Then MST for G is,

Now let's square the weights,

Then MST for G' is,

So, from above we can see that T is not necessarily equal to T' and moreover (t

So option (D) is correct answer.

Then MST for G is,

Now let's square the weights,

Then MST for G' is,

So, from above we can see that T is not necessarily equal to T' and moreover (t

^{1}) < (t^{2}).So option (D) is correct answer.

Question 31 |

FCFS: P1, P2, P3 RR2: P1, P2, P3 | |

FCFS: P1, P3, P2 RR2: P1, P3, P2 | |

FCFS: P1, P2, P3 RR2: P1, P3, P2 | |

FCFS: P1, P3, P2 RR2: P1, P2, P3 |

Question 31 Explanation:

FCFS is - P1, P2, P3

FCFS is clear.

RR Queue: In RR queue time slot is of 2 units.

Processes are assigned in following order

P1, P2, P1, P3, P2, P1, P3, P2, P2

This question used ready queue concept. At t=2, P2 starts and P1 is sent to the ready queue and at t=3 P3 arrives so then the job P3 is queued in ready queue after P1. So at t=4, again P1 is executed then P3 is executed for first time at t=6.

RR2: P1, P3, P2 So option C.

FCFS is clear.

RR Queue: In RR queue time slot is of 2 units.

Processes are assigned in following order

P1, P2, P1, P3, P2, P1, P3, P2, P2

This question used ready queue concept. At t=2, P2 starts and P1 is sent to the ready queue and at t=3 P3 arrives so then the job P3 is queued in ready queue after P1. So at t=4, again P1 is executed then P3 is executed for first time at t=6.

RR2: P1, P3, P2 So option C.

Question 32 |

fails as L can overflow | |

fails as L can take on a non-zero value when the lock is actually available | |

works correctly but may starve some processes | |

works correctly without starvation |

Question 32 Explanation:

Check the loop first:

while (Fetch_And_Add (L,1))

L = 1; // A waiting process can be here just after

// the lock is released, and can make L = 1.

Assume P1 executes until while condition and preempts before executing L =1. Now P2 executes all statements, hence L = 0. Then P1 without checking L it makes L = 1 by executing the statement where it was preempted.

It takes a non-zero value (L=1) when the lock is actually available (L = 0). So option B.

while (Fetch_And_Add (L,1))

L = 1; // A waiting process can be here just after

// the lock is released, and can make L = 1.

Assume P1 executes until while condition and preempts before executing L =1. Now P2 executes all statements, hence L = 0. Then P1 without checking L it makes L = 1 by executing the statement where it was preempted.

It takes a non-zero value (L=1) when the lock is actually available (L = 0). So option B.

Question 33 |

Suppose a fair six-sided die is rolled once. If the value on the die is 1, 2, or 3, the die is rolled a second time. What is the probability that the sum total of values that turn up is at least 6?

10/21 | |

5/12 | |

2/3 | |

1/6 |

Question 33 Explanation:

The value on the die for first time rolling= {1, 2, 3}

The value on second time can be {1, 2, 3, 4, 5, 6}

So the Sum can be

We have Sample space = 36

The no. of events where (Sum = atleast 6) = {6, 7, 6, 7, 8, 6, 7, 8, 9}

So the probability atleast ‘6’ while getting {1, 2, 3} in first time = 9/36 → ①

If we get ‘6’ in the first time itself, then we do not go for rolling die again.

So, its probability = 1/6

Total probability = 1/6 + 9/36 = 1/6 + 1/4 = 10/24 = 5/12

The value on second time can be {1, 2, 3, 4, 5, 6}

So the Sum can be

We have Sample space = 36

The no. of events where (Sum = atleast 6) = {6, 7, 6, 7, 8, 6, 7, 8, 9}

So the probability atleast ‘6’ while getting {1, 2, 3} in first time = 9/36 → ①

If we get ‘6’ in the first time itself, then we do not go for rolling die again.

So, its probability = 1/6

Total probability = 1/6 + 9/36 = 1/6 + 1/4 = 10/24 = 5/12

Question 34 |

An Internet Service Provider (ISP) has the following chunk of CIDR-based IP addresses available with it: 245.248.128.0/20. The ISP wants to give half of this chunk of addresses to Organization A, and a quarter to Organization B, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to A and B?

245.248.136.0/21 and 245.248.128.0/22 | |

245.248.128.0/21 and 245.248.128.0/22 | |

245.248.132.0/22 and 245.248.132.0/21 | |

245.248.136.0/24 and 245.248.132.0/21 |

Question 34 Explanation:

Question 35 |

Suppose a circular queue of capacity (n - 1) elements is implemented with an array of n elements. Assume that the insertion and deletion operations are carried out using REAR and FRONT as array index variables, respectively. Initially, REAR = FRONT = 0. The conditions to detect

*queue full*and*queue empty*arefull: (REAR+1)mod n == FRONT empty: REAR == FRONT | |

full: (REAR+1)mod n == FRONT empty: (FRONT+1) mod n == REAR | |

full: REAR == FRONT empty: (REAR+1) mod n == FRONT | |

full: (FRONT+1)mod n == REAR empty: REAR == FRONT |

Question 35 Explanation:

To circulate within the queue we have to write mod n for (Rear + 1).

We insert elements using Rear & delete through Front.

Question 36 |

Question 36 Explanation:

Main → A1 → A2 → A21 → A1

Since, Activation records are created at procedure exit time.

A1 & A2 are defined under Main ( ). So A1 & A2 access links are pointed to main.

A21 is defined under A2, hence its access link will point to A2.

Question 37 |

How many onto (or surjective) functions are there from an n-element (n ≥ 2) set to a 2-element set?

2 ^{n} | |

2 ^{n}-1 | |

2 ^{n}-2 | |

2(2 ^{n}– 2) |

Question 37 Explanation:

Onto function is possible if m ≥ n. So, no. of onto functions possible is,

n

^{m}-

^{n}C

_{1}(n-1)

^{m}+

^{n}C

_{2}(n-2)

^{m}+ .......

Here in Question,

m = n, n = 2

So, the final answer will be,

= 2

^{n}-

^{2}C

_{1}(2-1)

^{n}+

^{2}C

_{2}(2-2)

^{n}

= 2

^{n}- 2 × 1 + 0

= 2

^{n}- 2

Question 38 |

Let G be a complete undirected graph on 6 vertices. If vertices of G are labeled, then the number of distinct cycles of length 4 in G is equal to

15 | |

30 | |

45 | |

360 |

Question 38 Explanation:

Complete graph means there exists an edge between every pair of vertices.

It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.

So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.

The number of such selection of 4 vertices from 6 vertices is

From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like

a-b-c-d

a-b-d-c

a-c-b-d

a-c-d-b

a-d-b-c

a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )

As they are labelled you can observe, a-b-c-d and a-d-c-b are same, in different directions.

So, we get only three combinations from the above 6.

So, total number of distinct cycles of length 4 will be 15*3 = 45.

If it is asked about just number of cycles then 15*6 = 90

It is asked to find the distinct cycle of length 4. As it is complete graph, if we chose any two vertices, there will be an edge.

So, to get a cycle of length 4 (means selecting the 4 edges which can form a cycle) we can select any four vertices.

The number of such selection of 4 vertices from 6 vertices is

^{6}C_{4}=> 15.From each set of 4 vertices, suppose a set {a, b, c, d} we can have cycles like

a-b-c-d

a-b-d-c

a-c-b-d

a-c-d-b

a-d-b-c

a-d-c-b (Total 6, which is equal to number of cyclic permutations (n-1)! )

As they are labelled you can observe, a-b-c-d and a-d-c-b are same, in different directions.

So, we get only three combinations from the above 6.

So, total number of distinct cycles of length 4 will be 15*3 = 45.

If it is asked about just number of cycles then 15*6 = 90

Question 39 |

A list of n strings, each of length n, is sorted into lexicographic order using the merge-sort algorithm. The worst case running time of this computation is

O (n log n) | |

O (n ^{2} log n) | |

O (n ^{2} + log n) | |

O (n ^{2}) |

Question 39 Explanation:

1.The comparison is strictly follow the Dictionary based order.

2.The length of the string is n, the time taken is to be O(n) for each comparison.

3. For level -1(bottom-up order): Every element has to be compared with other element the number of comparisons is O(n/2).

4. For level -1(bottom-up order): Total time taken by one level is O(n

5. For copying level to level the time taken by O(n

So, For level -1= O(n

6. Second level O(n

;

;

;

Final n level (logn)*O(n

2.The length of the string is n, the time taken is to be O(n) for each comparison.

3. For level -1(bottom-up order): Every element has to be compared with other element the number of comparisons is O(n/2).

4. For level -1(bottom-up order): Total time taken by one level is O(n

^{2}).5. For copying level to level the time taken by O(n

^{2}).So, For level -1= O(n

^{2})+ O(n^{2})6. Second level O(n

^{2})+ O(n^{2}).;

;

;

Final n level (logn)*O(n

^{2}) = O(n^{2}logn)Question 40 |

SDT | |

SBDT | |

SACDT | |

SACET |

Question 40 Explanation:

They did not ask about shortest paths from S to T but they had asked the shortest path obtained by applying Dijkstra algorithm. If we apply Dijkstra algorithm we got path from S to T 10 only after relaxing edges through E and E will get 6 only after relaxing edges through C and C will get 5 only after relaxing edges through A. So, the shortest path from S to T if we follow Dijkstra algorithm is S,A,C,E,T.

The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.

Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.

So, path is S, A, C, E, T.

Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.

The shortest path between S to T is SBDT also but if you follow Dijkstra shortest path algorithm then the shortest path you will getting from S to T is only SACET. We suggest you to apply Dijkstra algorithm on S and find the shortest path between S to all vertices. Then the path you will get from S to T is SACET.

Here we will draw edge from E to T not D to S because we updated the T value to 10 after selecting vertex E.

So, path is S, A, C, E, T.

Here D will get 7 only through S. So, SBDT is not possible and SDT is not possible because T will get 10 only after selecting E. So, path is SACET.

Question 41 |

A file system with 300 GByte disk uses a file descriptor with 8 direct block addresses, 1 indirect block address and 1 doubly indirect block address. The size of each disk block is 128 Bytes and the size of each disk block address is 8 Bytes. The maximum possible file size in this file system is

3 KBytes | |

35 KBytes | |

280 KBytes | |

dependent on the size of the disk |

Question 41 Explanation:

It’s given disk block is of size 128B.

So, one direct block addressing will point to 8 disk blocks = 8*128 B = 1 KB

Singly Indirect block addressing will point to 1 disk block which has 128/8 disc block addresses = (128/8)*128 B = 2 KB

Doubly indirect block addressing will point to 1 disk block which has 128/8 addresses to disk blocks which in turn has 128/8 addresses to disk blocks = 16*16*128 B = 32 KB

Maximum possible file size = 1 KB + 2 KB + 32 KB = 35 KB

So, one direct block addressing will point to 8 disk blocks = 8*128 B = 1 KB

Singly Indirect block addressing will point to 1 disk block which has 128/8 disc block addresses = (128/8)*128 B = 2 KB

Doubly indirect block addressing will point to 1 disk block which has 128/8 addresses to disk blocks which in turn has 128/8 addresses to disk blocks = 16*16*128 B = 32 KB

Maximum possible file size = 1 KB + 2 KB + 32 KB = 35 KB

Question 42 |

OPTIMAL < LRU < FIFO | |

OPTIMAL < FIFO < LRU | |

OPTIMAL = LRU | |

OPTIMAL = FIFO |

Question 42 Explanation:

FIFO:

No. of page faults with FIFO = 6

LRU:

No. of page faults with LRU = 9

Optimal:

No. of page faults with optimal = 5

∴ Optimal < FIFO < LRU

No. of page faults with FIFO = 6

LRU:

No. of page faults with LRU = 9

Optimal:

No. of page faults with optimal = 5

∴ Optimal < FIFO < LRU

Question 43 |

Suppose R

_{1}(__A__, B) and R_{2}(__C__, D) are two relation schemas. Let r_{1}and r_{2}be the corresponding relation instances. B is a foreign key that refers to C in R_{2}. If data in r_{1}and r_{2}satisfy referential integrity constraints, which of the following is ALWAYS TRUE?∏ _{B} (r_{1}) - ∏_{C} (r_{2}) = ∅ | |

∏ _{C} (r_{2}) - ∏_{B} (r_{1}) = ∅ | |

∏ _{B} (r_{1}) = ∏_{C} (r_{2}) | |

∏ _{B} (r_{1}) - ∏_{C} (r_{2}) ≠ ∅ |

Question 43 Explanation:

Referential integrity means, all the values in foreign key should be present in primary key.

So we can say that r

So (subset - superset) is always empty.

So we can say that r

_{2}(C) is the superset of r_{1}(B).So (subset - superset) is always empty.

Question 44 |

Consider a source computer (S) transmitting a file of size 10

^{6}bits to a destination computer (D) over a network of two routers (R_{1}and R_{2}) and three links (L_{1}, L_{2}and L_{3}). L_{1}connects S to R_{1}; L_{2}connects R_{1}to R_{2}; and L_{3}connects R_{2}to D. Let each link be of length 100 km. Assume signals travel over each link at a speed of 10^{8}meters per second. Assume that the link bandwidth on each link is 1Mbps. Let the file be broken down into 1000 packets each of size 1000 bits. Find the total sum of transmission and propagation delays in transmitting the file from S to D?1005 ms | |

1010 ms | |

3000 ms | |

3003 ms |

Question 44 Explanation:

Propagation delay = (Distance) / (Velocity) = 3*10

^{5}/10

^{8}= 3ms

Total transmission delay for 1 packet = 3 * L / B = 3*(1000/10

^{6}) = 3ms. Because at source and 2 routers, we need to transmit the bits.

The first packet will reach destination = T

_{t}+ T

_{p}= 6ms.

While the first packet was reaching to D, other packets must have been processing in parallel. So D will receive remaining packets 1 packet per 1 ms from R

_{2}. So remaining 999 packets will take 999 ms.

And total time will be 999 + 6 = 1005 ms

Question 45 |

Consider an instance of TCP’s Additive Increase Multiplicative Decrease (AIMD) algorithm where the window size at the start of the slow start phase is 2 MSS and the threshold at the start of the first transmission is 8 MSS. Assume that a timeout occurs during the fifth transmission. Find the congestion window size at the end of the tenth transmission.

8 MSS | |

14 MSS | |

7 MSS | |

12 MSS |

Question 45 Explanation:

Given initial threshold = 8

Time = 1 during 1st trans. , window size = 2 (Slow start),

Time = 2 congestion window size = 4 (double the no. of ack.)

Time = 3 congestion window = 8

Time = 4 congestion window size = 9, after threshold, increase by one additive increase.

Time = 5 transmit 10 MSS, but time out occur congestion window size = 10

Hence threshold = (congestion window size)/2 = 10/2 = 5

Time = 6 transmit 2(since in the question, they are saying ss is starting from 2)

Time = 7 transmit 4

Time = 8 transmit 5

Time =9 transmit 6

Time =10 transmit 7

Time = 1 during 1st trans. , window size = 2 (Slow start),

Time = 2 congestion window size = 4 (double the no. of ack.)

Time = 3 congestion window = 8

Time = 4 congestion window size = 9, after threshold, increase by one additive increase.

Time = 5 transmit 10 MSS, but time out occur congestion window size = 10

Hence threshold = (congestion window size)/2 = 10/2 = 5

Time = 6 transmit 2(since in the question, they are saying ss is starting from 2)

Time = 7 transmit 4

Time = 8 transmit 5

Time =9 transmit 6

Time =10 transmit 7

Question 46 |

Question 46 Explanation:

All states are final states except “q” which is trap state. The strings in language are such that every substring of 3 symbol has at most two zeros. It means that we cannot have 3 consecutive zeros anywhere in string. In the given DFA total four transition is missing, so we have to create the missing transition keeping the criteria in mind that “three consecutive zeros” will lead to trap state “q” as after 3 consecutive zeros whatever comes after that in the string, the string is going to be rejected by DFA.

From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.

Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.

From the state “00” it is clear that if another “0” comes then the string is going to be rejected, so from state “00” the transition with input “0” will lead to state “q”. So option A and B are eliminated.

Now option C has the self loop of “0” on state “10” which will accept any number of zeros (including greater than three zeros), hence the C option is also wrong. We left with only option D which is correct option.

Question 47 |

B1: (1+height(n→right)) B2: (1+max(h1,h2)) | |

B1: (height(n→right)) B2: (1+max(h1,h2)) | |

B1: height(n→right) B2: max(h1,h2) | |

B1: (1+ height(n→right)) B2: max(h1,h2) |

Question 47 Explanation:

Now, we analyze the code,

The box B1 gets executed when left sub tree of n is NULL & right subtree is not NULL.

In such case, height of n will be the height of the right subtree +1.

The box B2 gets executed when both left & right subtrees of n are not NULL.

In such case, height of n will be max of heights of left & right subtrees of n+1.

Question 49 |

Question 49 Explanation:

Line 1 replaced by auto int a=1;

Line 2 replaced by register int a=2;

In main there will be no change if it is static or auto because of a+=1 the auto variable a is updated to 2 from 1.

In prtfun ( ), register makes a difference.

For first print statement a is updated to 4 & prints 4, 2.

But now it is not a static variable to retain the value of a to 4. So it becomes 2, when second function call takes place & prints 4, 2 again. There is no change in b, it acts like a local variable.

Hence,

4 2

4 2

2 0.

Line 2 replaced by register int a=2;

In main there will be no change if it is static or auto because of a+=1 the auto variable a is updated to 2 from 1.

In prtfun ( ), register makes a difference.

For first print statement a is updated to 4 & prints 4, 2.

But now it is not a static variable to retain the value of a to 4. So it becomes 2, when second function call takes place & prints 4, 2 again. There is no change in b, it acts like a local variable.

Hence,

4 2

4 2

2 0.

Question 50 |

7 | |

4 | |

5 | |

9 |

Question 50 Explanation:

Performs the cross product and selects the tuples whose A∙Id is either greater than 40 or C∙Id is less than 15. It yields:

Question 51 |

4 | |

3 | |

0 | |

1 |

Question 51 Explanation:

First query (2) will be executed and 0 (no) rows will be selected because in relation B there is no Name ‘Arun’.

The outer query (1) results the follow and that will be the result of entire query now. (Because inner query returns 0 rows).

Question 52 |

FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b,$} | |

FIRST(A) = {a,b,$} FIRST(B) = {a,b,ε} FOLLOW(A) = {a,b} FOLLOW(B) = {$} | |

FIRST(A) = {a,b,ε} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = ∅ | |

FIRST(A) = {a,b} = FIRST(B) FOLLOW(A) = {a,b} FOLLOW(B) = {a,b} |

Question 52 Explanation:

FIRST (P): is the set of terminals that begin the strings derivable from non terminal P. If P derives epsilon then we include epsilon in FIRST(P).

FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.

FIRST(A) = FIRST (S)

FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)

FIRST(S) = {a, b, ϵ}

FIRST (B) = FIRST (S) = {a, b, ϵ}= FIRST (A)

FOLLOW(A) = {b} // because of production S→a A b B

FOLLOW(A) = {a} // because of production S→ b A a B

So FOLLOW (A) = {a, b}

FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B

FOLLOW (S) = FOLLOW (A) // because of production S → A

So FOLLOW (S) = {$, a, b}= FOLLOW(B)

FOLLOW(P): is the set of terminals that can appear immediately to the right of P in some sentential form.

FIRST(A) = FIRST (S)

FIRST (S) = FIRST (aAbB) and FIRST (bAaB) and FIRST (ϵ)

FIRST(S) = {a, b, ϵ}

FIRST (B) = FIRST (S) = {a, b, ϵ}= FIRST (A)

FOLLOW(A) = {b} // because of production S→a A b B

FOLLOW(A) = {a} // because of production S→ b A a B

So FOLLOW (A) = {a, b}

FOLLOW (B) = FOLLOW (S) // because of production S→ a A b B

FOLLOW (S) = FOLLOW (A) // because of production S → A

So FOLLOW (S) = {$, a, b}= FOLLOW(B)

Question 53 |

E1: S → aAbB,A → S E2: S → bAaB,B→S E3: B → S | |

E1: S → aAbB,S→ ε E2: S → bAaB,S → ε E3: S → ε | |

E1: S → aAbB,S → ε E2: S → bAaB,S→ε E3: B → S | |

E1: A → S,S →ε E2: B → S,S → ε E3: B →S |

Question 53 Explanation:

The entries in E1, E2 and E3 is related to S and B, so we have to take only those production which have S and B in LHS.

S→ aAbB | bAaB | ε

The production S→ aAbB will go under column FIRST (aAbB) = a, so S→ aAbB will be in E1.

S→ bAaB will go under column FIRST(bAaB) = b, so S→ bAaB will be in E2.

S→ ε will go under FOLLOW (S) = FOLLOW(B) = {a, b, $ } , So S→ ε will go in E1, E2 and under column of $.

So E1 will have: S→ aAbB and S→ ε.

E2 will have S→ bAaB and S→ ε.

Now, B→ S will go under FIRST (S) = {a, b, ε}

Since FIRST(S) = ε so B→ S will go under FOLLOW (B) = {a, b, $}

So E3 will contain B→ S.

S→ aAbB | bAaB | ε

The production S→ aAbB will go under column FIRST (aAbB) = a, so S→ aAbB will be in E1.

S→ bAaB will go under column FIRST(bAaB) = b, so S→ bAaB will be in E2.

S→ ε will go under FOLLOW (S) = FOLLOW(B) = {a, b, $ } , So S→ ε will go in E1, E2 and under column of $.

So E1 will have: S→ aAbB and S→ ε.

E2 will have S→ bAaB and S→ ε.

Now, B→ S will go under FIRST (S) = {a, b, ε}

Since FIRST(S) = ε so B→ S will go under FOLLOW (B) = {a, b, $}

So E3 will contain B→ S.

Question 54 |

11 | |

14 | |

16 | |

27 |

Question 54 Explanation:

It is given that cache size = 256 KB

Cache block size = 32 Bytes

So, number of blocks in the cache = 256K / 32 = 8 K

It is a 4-way set associative cache. Each set has 4 blocks.

So, number of sets in cache = 8 K / 4 = 2 K = 2

So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

Cache block size = 32 Bytes

So, number of blocks in the cache = 256K / 32 = 8 K

It is a 4-way set associative cache. Each set has 4 blocks.

So, number of sets in cache = 8 K / 4 = 2 K = 2

^{11}.So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

Question 55 |

160 Kbits | |

136 Kbits | |

40 Kbits | |

32 Kbits |

Question 55 Explanation:

It is given that cache size =256 KB

Cache block size = 32 Bytes

So, number of blocks in the cache = 256K / 32 = 8 K

It is a 4-way set associative cache. Each set has 4 blocks.

So, number of sets in cache = 8 K / 4 = 2 K = 2

So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

It is given that in addition to address tag there are 2 valid bits, 1 modified bit and 1 replacement bit.

So size of each tag entry = 16 tag bits + 2 valid bits + 1 modified bit + 1 replacement bit = 20 bits

Size of cache tag directory=Size of tag entry×Number of tag entries

= 20×8 K

=160 Kbits

Cache block size = 32 Bytes

So, number of blocks in the cache = 256K / 32 = 8 K

It is a 4-way set associative cache. Each set has 4 blocks.

So, number of sets in cache = 8 K / 4 = 2 K = 2

^{11}.So, 11 bits are needed for accessing a set. Inside a set we need to identify the cache block.

Since cache block size is 32 bytes, block offset needs 5 bits.

Out of 32 bit address, no. of TAG bits = 32 - 11 - 5 = 32-16 = 16

So, we need 16 tag bits.

It is given that in addition to address tag there are 2 valid bits, 1 modified bit and 1 replacement bit.

So size of each tag entry = 16 tag bits + 2 valid bits + 1 modified bit + 1 replacement bit = 20 bits

Size of cache tag directory=Size of tag entry×Number of tag entries

= 20×8 K

=160 Kbits

Question 56 |

The cost function for a product in a firm is given by 5q

^{2}, where q is the amount of production. The firm can sell the product at a market price of ₹50 per unit. The number of units to be produced by the firm such that the profit is maximized is5 | |

10 | |

15 | |

25 |

Question 56 Explanation:

Total selling price =50q

Profit = 50q - 5q

For Profit to be maximum,

d(Profit)/dq = 0

d(50q - 5q

50 - 10q = 0

50 = 10q

q = 5

Profit = 50q - 5q

^{2}For Profit to be maximum,

d(Profit)/dq = 0

d(50q - 5q

^{2}) /dq = 050 - 10q = 0

50 = 10q

q = 5

Question 57 |

attempts | |

setbacks | |

meetings | |

delegations |

Question 57 Explanation:

Setback = a reversal (or) setback in a progress (or) something that happens that delays

Despite several

Despite several

__setbacks__the mission succeeded in its attempt to resolve the conflict.Question 58 |

Diminish | |

Divulge | |

Dedicate | |

Denote |

Question 58 Explanation:

Mitigate = make (something bad) less severe, serious (or) painful

Synonyms = Diminish, alleviate, reduce etc.

Synonyms = Diminish, alleviate, reduce etc.

Question 59 |

Choose the grammatically

**INCORRECT**sentence:They gave us the money back less the service charges of Three Hundred rupees. | |

This country’s expenditure is not less than that of Bangladesh. | |

The committee initially asked for a funding of Fifty Lakh rupees, but later settled for a lesser sum. | |

This country’s expenditure on educational reforms is very less. |

Question 59 Explanation:

The country's expenditure on educational reforms is very less.

In the sentence "

In the sentence "

__very less__" is incorrect instead of this we use "much less" or else "very little".Question 60 |

that | |

which | |

who | |

whom |

Question 60 Explanation:

Suresh's dog is the one

__that__was hurt in the stampede.__that__can refer groups of things.__who__can refer to people.__which__can introduces a non-essential clause.__whom__can refer to object of a verb (or) preposition.Question 61 |

Gender-discriminatory | |

Xenophobic | |

Not designed to make the post attractive | |

Not gender-discriminatory |

Question 61 Explanation:

Xenephobic which refers to having (or) showing a dislike of or prejudice against people from other countries.

Question 62 |

A political party orders an arch for the entrance to the ground in which the annual convention is being held. The profile of the arch follows the equation y = 2x - 0.1x

^{2}where y is the height of the arch in meters. The maximum possible height of the arch is8 meters | |

10 meters | |

12 meters | |

14 meters |

Question 62 Explanation:

Given,

y = 2x - 0.1x

Differentiating both sides,

dy/dx = 2 - 0.2x

For maximum, dy/dx = 0

2 - 0.2x = 0

0.2x = 2

x = 10

y = 2x - 0.1x

^{2}Differentiating both sides,

dy/dx = 2 - 0.2x

For maximum, dy/dx = 0

2 - 0.2x = 0

0.2x = 2

x = 10

Question 63 |

0.288 | |

0.334 | |

0.667 | |

0.720 |

Question 63 Explanation:

Probability that a shock absorber from X is reliable = 0.6×0.96 = 0.576

Probability that a shock absorber from Y is reliable = 0.4×0.72 = 0.288

Probability that a randomly selected reliable absorber is from Y is = 0.288/(0.576+0.288) = 0.334

Probability that a shock absorber from Y is reliable = 0.4×0.72 = 0.288

Probability that a randomly selected reliable absorber is from Y is = 0.288/(0.576+0.288) = 0.334

There are 65 questions to complete.