## GATE 2014(Set-01)

Question 1 |

adopt to | |

adapt to | |

adept in | |

accept with |

Question 1 Explanation:

Cope: Deal effectively with something difficult.

(1) Adopt ⇒ Legally take and bring it up as one's own.

(2) Adapt ⇒ Make suitable for a new use or purpose.

(3) Adept ⇒ Very skilled (or) proficienct at something.

(4) Accept ⇒ Believe (or) come to recognize as valid (or) correct.

Option B is correct.

(1) Adopt ⇒ Legally take and bring it up as one's own.

(2) Adapt ⇒ Make suitable for a new use or purpose.

(3) Adept ⇒ Very skilled (or) proficienct at something.

(4) Accept ⇒ Believe (or) come to recognize as valid (or) correct.

Option B is correct.

Question 2 |

superb | |

medium | |

mediocre | |

exhilarating |

Question 2 Explanation:

Mediocre ⇒ Average quality (or) Not very good.

Question 3 |

In a press meet on the recent scam, the minister said, "The buck stops here". What did the minister convey by the statement?

He wants all the money | |

He will return the money | |

He will assume final responsibility | |

He will resist all enquiries |

Question 3 Explanation:

"The buck stops here" means "The responsibility for something cannot (or) should not passed to someone else.

⇒ It represents that this is the final stage of responsibility.

⇒ It represents that this is the final stage of responsibility.

Question 4 |

If (z + 1/z)

^{2 }= 98, compute (z^{2}+ 1/z^{2}).96 | |

97 | |

98 | |

99 |

Question 4 Explanation:

z

^{2}+1/z^{2}+2∙z∙ 1/z=98⇒z^{2}+ 1/z^{2}=96Question 5 |

The roots of ax

^{2}+ bx + c = 0 are real and positive. a, b and c are real. Then ax^{2 }+ b|x|+ c = 0 hasno roots | |

2 real roots | |

3 real roots | |

4 real roots |

Question 5 Explanation:

ax

For roots to be real & positive b

This will have 2 real positive roots.

ax

Discriminant =b

ax

(-b)

⇒b

Is also > 0. This will have real roots.

⇒ This will have 4 real roots.

^{2}+bx+c=0For roots to be real & positive b

^{2}-4ac>0This will have 2 real positive roots.

ax

^{2}+b|x|+c=0Discriminant =b

^{2}-4ac>0ax

^{2}+bx+c(-b)

^{2}-4ac⇒b

^{2}-4acIs also > 0. This will have real roots.

⇒ This will have 4 real roots.

Question 6 |

The Palghat gap is caused by high rainfall and high temperatures in southern Tamil Nadu and Kerala | |

The regions in Tamil Nadu and Kerala that are near the Palghat Gap are low-lying | |

The low terrain of the Palghat Gap has a significant impact on weather patterns in neighbouring parts of Tamil Nadu and Kerala | |

Higher summer temperatures result in higher rainfall near the Palghat Gap area |

Question 6 Explanation:

The given passage says that "it results neighbouring regions of Tamilnadu getting more rainfall from the south west monsoon and neighbouring regions of Kerela having higher summer temperatures".

⇒ Option C is suitable option.

⇒ Option C is suitable option.

Question 7 |

Strategies are now available for eliminating psychiatric illnesses | |

Certain psychiatric illnesses have a genetic basis | |

All human diseases can be traced back to genes and how they are expressed | |

In the future, genetics will become the only relevant field for identifying psychiatric illnesses |

Question 7 Explanation:

The first sentence can represents the two specific illness depression and schizophernia.
⇒ Option B is the only option that contain illness.

Question 8 |

Round-trip tickets to a tourist destination are eligible for a discount of 10% on the total fare. In addition, groups of 4 or more get a discount of 5% on the total fare. If the one way single person fare is Rs 100, a group of 5 tourists purchasing round-trip tickets will be charged Rs _________.

850 | |

851 | |

852 | |

853 |

Question 10 |

When a point inside of a tetrahedron (a solid with four triangular surfaces) is connected by straight lines to its corners, how many (new) internal planes are created with these lines? _____________

6 | |

7 | |

8 | |

9 |

Question 11 |

∀x:glitters(x) ⇒¬gold(x) | |

∀x:gold(x) ⇒glitters() | |

∃x: gold(x)∧¬glitters(x) | |

∃x:glitters(x)∧¬gold(x) |

Question 11 Explanation:

Method 1:

Not all that glitters is gold.

Option A:

∀x:glitters(x) ⇒¬gold(x)

which means that every item (x), which glitters is not gold.

Option B:

∀x:gold(x) ⇒glitters()

Every item (x) which is gold is a glitter.

(or)

Every golden item glitters.

Option C:

∃x: gold(x)∧¬glitters(x)

There are some gold items which does not glitters.

Option D:

∃x:glitters(x)∧¬gold(x)

There exists some glitters which are not gold.

(or)

Not all glitters are gold.

The answer is Option (D).

Method 2:

⇒ (∼∀x) (∼ (glitters(x) ⇒ gold(x))

⇒ ∃x (∼ (∼glitters(x) ∨ gold(x))

⇒ ∃x (glitters ∧ gold(x))

Not all that glitters is gold.

Option A:

∀x:glitters(x) ⇒¬gold(x)

which means that every item (x), which glitters is not gold.

Option B:

∀x:gold(x) ⇒glitters()

Every item (x) which is gold is a glitter.

(or)

Every golden item glitters.

Option C:

∃x: gold(x)∧¬glitters(x)

There are some gold items which does not glitters.

Option D:

∃x:glitters(x)∧¬gold(x)

There exists some glitters which are not gold.

(or)

Not all glitters are gold.

The answer is Option (D).

Method 2:

⇒ (∼∀x) (∼ (glitters(x) ⇒ gold(x))

⇒ ∃x (∼ (∼glitters(x) ∨ gold(x))

⇒ ∃x (glitters ∧ gold(x))

Question 12 |

Suppose you break a stick of unit length at a point chosen uniformly at random. Then the expected length of the shorter stick is ________ .

0.25 | |

0.26 | |

0.27 | |

0.28 |

Question 12 Explanation:

We break a unit length rod into two pieces at a uniformly chosen point.

If we break at point x, length of the one piece x and the other piece is 1 – x.

Length of the shorter stick is between 0 to 0.5. If it is more than 0.5 then it will be longer stick.

The random variable (l) follows a uniform distribution. The probability function of l is

1/(b-a)=1/(0.5-0)=2 (length is between 0 to 0.5)

Expected value of length

(where P(l) is the probability density function)

If we break at point x, length of the one piece x and the other piece is 1 – x.

Length of the shorter stick is between 0 to 0.5. If it is more than 0.5 then it will be longer stick.

The random variable (l) follows a uniform distribution. The probability function of l is

1/(b-a)=1/(0.5-0)=2 (length is between 0 to 0.5)

Expected value of length

(where P(l) is the probability density function)

Question 13 |

Let G = (V,E) be a directed graph where V is the set of vertices and E the set of edges. Then which one of the following graphs has the same strongly connected components as G?

G _{1}=(V,E_{1}) where E_{1}={(u,v)|(u,v)∉E} | |

G _{2}=(V,E_{2} )where E_{2}={(u,v)│(u,v)∈E} | |

G _{3}=(V,E_{3}) where E_{3}={(u,v)|there is a path of length≤2 from u to v in E} | |

G _{4}=(V_{4},E) where V_{4} is the set of vertices in G which are not isolated |

Question 13 Explanation:

G(V, E) is a directed graph.

→ It strongly connected.

(A) G

If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.

(B) G

Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.

Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.

(C) G

This can also be true.

eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.

(D) G

If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component

then no. of SCC = x + 1

G

→ It strongly connected.

(A) G

_{1}=(V,E_{1}) where E_{1}={(u,v)|(u,v)∉E}If (u, v) does not belong to the edge set ‘E’, then it indicates there are no edges. So, it is not connected.

(B) G

_{2}=(V,E_{2})where E_{2}={(u,v)│(u,v)∈E}Given that ‘G’ is directed graph, i.e., it has path from each vertex to every other vertex.

Though direction is changed from (u, v) to (v, u), it is still connected component same as ‘G’.

(C) G

_{3}=(V,E_{3}) where E_{3}={(u,v)|there is a path of length≤2 from u to v in E}This can also be true.

eg:

Both from each vertex to other vertex is also exists. So it is also strongly connected graph.

(D) G

_{4}=(V_{4},E) where V_{4}is the set of vertices in G which are not isolated.If ‘G’ has same ‘x’ no. of isolated vertices, one strongly connected component

then no. of SCC = x + 1

G

_{4}contain only ‘1’ component, which is not same as G.Question 14 |

1 | |

2 | |

3 | |

4 |

Question 14 Explanation:

Given:

3x + 2y = 1

4x + 7z = 1

x + y + z = 3

x – 2y + 7z = 0

This is a non-homogeneous equation system.

The Augmented matrix for above set of equations is

For matrix (A):

R

R

Rank = 3

For matrix (AB):

R

Rank = 3

Rank of (A) = Rank (AB), so Unique solution

rank = 3 = no. of variables

Working Rule for Non-homogeneous equation:

(1) rank (A) < rank (AB), Inconsistent solution

(2) is rank (A) = rank (AB) = r then

if r = n, Unique solution

r < n, Infinite solution

3x + 2y = 1

4x + 7z = 1

x + y + z = 3

x – 2y + 7z = 0

This is a non-homogeneous equation system.

The Augmented matrix for above set of equations is

For matrix (A):

R

_{4}→ R_{4}+R_{1}R

_{4}→ R_{4}-R_{2}Rank = 3

For matrix (AB):

R

_{4}→(R_{4}+R_{1})-R_{2}Rank = 3

Rank of (A) = Rank (AB), so Unique solution

rank = 3 = no. of variables

Working Rule for Non-homogeneous equation:

(1) rank (A) < rank (AB), Inconsistent solution

(2) is rank (A) = rank (AB) = r then

if r = n, Unique solution

r < n, Infinite solution

Question 15 |

The value of the dot product of the eigenvectors corresponding to any pair of different eigenvalues of a 4-by-4 symmetric positive definite matrix is _____________________.

0 | |

1 | |

2 | |

3 |

Question 15 Explanation:

For real symmetric matrix, the eigen values are orthogonal to each other. So their dot product will be zero.

The finite dimensional spectral theorem says that any symmetric matrix whose entries are real can be diagonalized by an orthogonal matrix.

The finite dimensional spectral theorem says that any symmetric matrix whose entries are real can be diagonalized by an orthogonal matrix.

Question 16 |

I only | |

II only | |

Both I and II | |

Neither I nor II |

Question 16 Explanation:

Rolle’s theorem:

Rolle’s theorem states that for any continuous, differentiable function that has two equal values at two distinct points, the function must have a point on the function where the first derivative is zero. The technical way to state this is: if f is continuous and differentiable on a closed interval [a,b] and if f(a) = f(b), then f has a minimum of one value c in the open interval [a, b] so that f'(c) = 0.

We can observe that, sin, cos are continuous, but, Tan is not continuous at π/2. As the mentioned interval does not contain π/2, we can conclude that it is continuous.

As per Rolls theorem both statement 1 and statement 2 are true.

Rolle’s theorem states that for any continuous, differentiable function that has two equal values at two distinct points, the function must have a point on the function where the first derivative is zero. The technical way to state this is: if f is continuous and differentiable on a closed interval [a,b] and if f(a) = f(b), then f has a minimum of one value c in the open interval [a, b] so that f'(c) = 0.

We can observe that, sin, cos are continuous, but, Tan is not continuous at π/2. As the mentioned interval does not contain π/2, we can conclude that it is continuous.

As per Rolls theorem both statement 1 and statement 2 are true.

Question 17 |

Question 17 Explanation:

PQ + P’QR + P’QR’S

= Q(P+P’R) + P’QR’S

= Q(P+R) + P’QR’S

=QP + QR + P’QR’S

= QP + Q(R + P’R’S)

= QP + Q( R + P’S)

= QP + QR + QP’S

= Q(P+P’S) + QR

= Q(P+S)+ QR

= QP + QS + QR

= Q(P+P’R) + P’QR’S

= Q(P+R) + P’QR’S

=QP + QR + P’QR’S

= QP + Q(R + P’R’S)

= QP + Q( R + P’S)

= QP + QR + QP’S

= Q(P+P’S) + QR

= Q(P+S)+ QR

= QP + QS + QR

Question 18 |

5 | |

6 | |

7 | |

8 |

Question 18 Explanation:

Let base of the number system is r.

(3r

(3r

(3r

r

Therefor r = 5

(3r

^{2}+ r + 2) / 2r= (r+3+1/r)(3r

^{2}+ r + 2) / 2r= (r^{2}+3r+1) / r(3r

^{2}+ r + 2) = (2r^{2}+6r+2)r

^{2}-5r = 0Therefor r = 5

Question 19 |

A machine has a 32-bit architecture, with 1-word long instructions. It has 64 registers, each of which is 32 bits long. It needs to support 45 instructions, which have an immediate operand in addition to two register operands. Assuming that the immediate operand is an unsigned integer, the maximum value of the immediate operand is ____________.

16383 | |

16384 | |

16385 | |

16386 |

Question 19 Explanation:

1 Word = 32 bits

Each instruction has 32 bits.

To support 45 instructions, opcode must contain 6-bits.

Register operand1 requires 6 bits, since the total registers are 64.

Register operand 2 also requires 6 bits

14-bits are left over for immediate Operand Using 14-bits, we can give maximum 16383, Since 2

Each instruction has 32 bits.

To support 45 instructions, opcode must contain 6-bits.

Register operand1 requires 6 bits, since the total registers are 64.

Register operand 2 also requires 6 bits

14-bits are left over for immediate Operand Using 14-bits, we can give maximum 16383, Since 2

^{14}= 16384 (from 0 to 16383)Question 20 |

Compilation fails. | |

Execution results in a run-time error. | |

On execution, the value printed is 5 more than the address of variable i. | |

On execution, the value printed is 5 more than the integer value entered. |

Question 20 Explanation:

int i; // Initially i takes the Garbage value

int *pi = &i; // pi is a pointer which stores the address of i.

scanf (pi); // pi = &i (we rewrite the garbage value with our values) say x = 2

printf (i+5); // i+5 = x+5 = 2+5 = 7

Hence on execution, the value printed is 5 more than the integer value entered.

int *pi = &i; // pi is a pointer which stores the address of i.

scanf (pi); // pi = &i (we rewrite the garbage value with our values) say x = 2

printf (i+5); // i+5 = x+5 = 2+5 = 7

Hence on execution, the value printed is 5 more than the integer value entered.

Question 21 |

Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?

θ(n) | |

θ(n+m) | |

θ(n ^{2} ) | |

θ(m ^{2} ) |

Question 21 Explanation:

DFS visits each vertex once and as it visits each vertex, we need to find all of its neighbours to figure out where to search next. Finding all its neighbours in an adjacency matrix requires O(V ) time, so overall the running time will be O(V

^{2}).Question 22 |

Consider a rooted n node binary tree represented using pointers. The best upper bound on the time required to determine the number of subtrees having exactly 4 nodes is O(n

^{a}log^{b}n). Then the value of a+10b is ________.1 | |

2 | |

3 | |

4 |

Question 22 Explanation:

Binary tree traversal takes O(n) time for reaching 4th level from the leaf node. Every node has to check their subtree having exactly 4 nodes. Checking time can be done in maximum constant time for each node. Nodes in the level is always less than n and it's complexity is O(n). Finally a value becomes 1 and b value becomes 0.

Substitute into a and b values in equation.

⇒ a+10b

⇒ a*1 + 10*0

⇒ 1+0

⇒ 1

Substitute into a and b values in equation.

⇒ a+10b

⇒ a*1 + 10*0

⇒ 1+0

⇒ 1

Question 23 |

The graph does not have any topological ordering. | |

Both PQRS and SRQP are topological. | |

Both PSRQ and SPRQ are topological orderings. | |

PSRQ is the only topological ordering. |

Question 23 Explanation:

There are no cycles in the graph, so topological orderings do exist.

We can consider P & S as starting vertex, followed by R & Q.

Hence, PSRQ & SPRQ are the topological orderings.

Question 24 |

Let P be a quicksort program to sort numbers in ascending order using the first elements as the pivot. Let t

_{1}and t_{2}be the number of comparisons made by P for the inputs [1 2 3 4 5] and [4 1 5 3 2] respectively. Which one of the following holds?t _{1}=5 | |

t _{1} | |

t _{1}>t_{2} | |

t _{1}=t_{2} |

Question 24 Explanation:

[

Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2

Hence t

**1**, 2, 3, 4, 5] [**4**, 1, 5, 3, 2]Simple one: First element is a pivot element. And if we observe first array pivot is small and requires lot of comparisons and whereas it is not the case with 2

^{nd}array through not in sorted manner.Hence t

_{1}> t_{2}.Question 25 |

Which one of the following is TRUE?

The language L={a ^{n} b^{n}│n≥0} is regular. | |

The language L={a ^{n}│n is prime} is regular. | |

The language L={w│w has 3k+1b's for some k∈N with Σ={a,b} } is regular. | |

The language L={ww│w∈Σ* with Σ={0,1} } is regular. |

Question 25 Explanation:

The Language L= {a

L = {a

L = {ww | w ∈ ∑*} is CSL.

But L = { w | w has 3k+1 b’s for some k ∈ natural number} is regular.

Lets take values of k={1,2,3,….}

So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.

The DFA will be

^{n}b^{n}| n>=0} is CFL but not regular, as it requires comparison between a’s and b’s.L = {a

^{n}| n is prime} is CSL, as calculation of “n is prime” can be done by LBA (Turing machine)L = {ww | w ∈ ∑*} is CSL.

But L = { w | w has 3k+1 b’s for some k ∈ natural number} is regular.

Lets take values of k={1,2,3,….}

So number of b’s will be {4, 7, 10,……….} and number of a’s can be anything.

The DFA will be

Question 26 |

{q _{0},q_{1},q_{2} } | |

{q _{0},q_{1} } | |

{q _{0},q_{1},q_{2},q_{3} } | |

{q _{3} } |

Question 26 Explanation:

{q

{q

{q

Hence δ (q

_{0}, 0 → q_{0}} , { q_{0}, 0 → q_{0}}, {q_{0}, 1 → q_{0}}, {q_{0}, 1 → q_{0}} . Hence δ (q_{0}, 0011) = q_{0}{q

_{0}, 0 → q_{0}} , { q_{0}, 0 → q_{0}}, {q_{0}, 1 → q_{0}}, {q_{0}, 1 → q_{1}} . Hence δ (q_{0}, 0011) = q_{1}{q

_{0}, 0 → q_{0}} , { q_{0}, 0 → q_{0}}, {q_{0}, 1 → q_{1}}, {q_{1}, 1 → q_{2}} . Hence δ (q_{0}, 0011) = q_{2}Hence δ (q

_{0}, 0011) = {q_{0}, q_{1}, q_{2}}Question 27 |

Which one of the following is FALSE?

A basic block is a sequence of instructions where control enters the sequence at the beginning and exits at the end. | |

Available expression analysis can be used for common subexpression elimination. | |

Live variable analysis can be used for dead code elimination. | |

x=4*5⇒x=20 is an example of common subexpression elimination. |

Question 27 Explanation:

x=4* 5 ⇒ x=20 is an example of common subexpression elimination is a false statement.

Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.

For ex: Consider the following code:

m=y+z * p

n= y+z *k

The common subexpression is “y+z” we can be calculate it one time and replace in both expression

temp = y+z

m = temp*p

n = temp*k

Common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyzes whether it is worthwhile replacing them with a single variable holding the computed value.

For ex: Consider the following code:

m=y+z * p

n= y+z *k

The common subexpression is “y+z” we can be calculate it one time and replace in both expression

temp = y+z

m = temp*p

n = temp*k

Question 29 |

Suppose a disk has 201 cylinders, numbered from 0 to 200. At some time the disk arm is at cylinder 100, and there is a queue of disk access requests for cylinders 30, 85, 90, 100, 105, 110, 135 and 145. If Shortest-Seek Time First (SSTF) is being used for scheduling the disk access, the request for cylinder 90 is serviced after servicing ____________ number of requests.

3 | |

4 | |

5 | |

6 |

Question 29 Explanation:

100 → 105 → 110 → 90

90 is serviced after servicing the 3 requests.

90 is serviced after servicing the 3 requests.

Question 30 |

Which one of the following is

**FALSE**?User level threads are not scheduled by the kernel. | |

When a user level thread is blocked, all other threads of its process are blocked. | |

Context switching between user level threads is faster than context switching between kernel level threads. | |

Kernel level threads cannot share the code segment. |

Question 30 Explanation:

Kernel level threads shares the code segment.

Question 31 |

Consider the relation scheme R = (E, F, G, H, I, J, K, L, M, N) and the set of functional dependencies {{E,F} → {G}, {F} → {I,J}, {E,H} → {K,L}, {K} → {M}, {L} → {N}} on R. What is the key for R?

{E,F} | |

{E,F,H} | |

{E,F,H,K,L} | |

{E} |

Question 31 Explanation:

A) (EF)

B) (EFH)

C) If EFH is a key, then EFHKL will become the super key.

D) (E)

^{+}= EFGIJ. So, EF is not a key.B) (EFH)

^{+}= EFHGIJKLMN, EFH is deriving all the attributes of R. So, EFH is a key.C) If EFH is a key, then EFHKL will become the super key.

D) (E)

^{+}= EQuestion 32 |

S1 is TRUE and S2 is FALSE. | |

Both S1 and S2 are TRUE. | |

S1 is FALSE and S2 is TRUE. | |

Both S1 and S2 are FALSE. |

Question 32 Explanation:

S1: False

Using a check constraint, we can have the same effect as foreign key while adding elements to the child table. But while deleting elements from the parent table the referential integrity constraint is no longer valid. So, a check constraint cannot replace a foreign key.

S2: False:

Foreign key in one table should be defined as a primary key in other table. In above table definition, table S has a foreign key that refers to field ‘a’ of R. The field ‘a’ in table S is part of the primary key and part of the key cannot be declared as a foreign key.

Using a check constraint, we can have the same effect as foreign key while adding elements to the child table. But while deleting elements from the parent table the referential integrity constraint is no longer valid. So, a check constraint cannot replace a foreign key.

S2: False:

Foreign key in one table should be defined as a primary key in other table. In above table definition, table S has a foreign key that refers to field ‘a’ of R. The field ‘a’ in table S is part of the primary key and part of the key cannot be declared as a foreign key.

Question 33 |

S1, S2, and S3 are all true. | |

S1, S2, and S3 are all false. | |

S1 and S2 are true, but S3 is false. | |

S1 and S3 are true, but S2 is false. |

Question 33 Explanation:

S1: The computational overhead in link state protocols is higher than in distance vector protocols. Because LSR is based upon global knowledge whereas DVR is based upon Local info.(True)

S2: A distance vector protocol with split horizon avoid persistent routing loops is true, but not a link state protocol is false because link state protocols do not have count to infinity problem.

S3: As Distance vector protocol has count to infinity problem and converges slower. (True)

S2: A distance vector protocol with split horizon avoid persistent routing loops is true, but not a link state protocol is false because link state protocols do not have count to infinity problem.

S3: As Distance vector protocol has count to infinity problem and converges slower. (True)

Question 34 |

P and R only | |

Q and R only | |

Q and S only | |

R and S only |

Question 34 Explanation:

RSA and DES are for Encryption where MD5 and SHA – 1 are used to generate Message Digest.

Question 35 |

4,2,1,3 | |

1,2,3,4 | |

4,1,2,3 | |

2,4,1,3 |

Question 35 Explanation:

First of all the browser must now know what IP to connect to. For this purpose browser takes help of Domain name system (DNS) servers which are used for resolving hostnames to IP addresses. As browser is an HTTP client and as HTTP is based on the TCP/IP protocols, first it establishes a TCP connection with the web server and requests a web page using HTTP, and then the web server sends the requested web page using HTTP. Hence the order is 4,2,1,3.

Question 36 |

Consider a token ring network with a length of 2 km having 10 stations including a monitoring station. The propagation speed of the signal is 2×10

^{8}m/s and the token transmission time is ignored. If each station is allowed to hold the token for 2 µsec, the minimum time for which the monitoring station should wait (in µsec) before assuming that the token is lost is _______.28μs to 30 μs | |

29μs to 31 μs | |

30μs to 32 μs | |

31μs to 33 μs |

Question 36 Explanation:

Given length (d) = 2 Km

No. of Stations (m) = 10

Propagation speed (v) = 2⨯10

THT = 2μs

So, Max, TRT = T

= 10 ⨯ 10

= 30 μs

No. of Stations (m) = 10

Propagation speed (v) = 2⨯10

^{8}m/sTHT = 2μs

So, Max, TRT = T

_{p}in the ring + No. of Active Stations * THT= 10 ⨯ 10

^{-6}⨯ 10 ⨯ 2 ⨯ 10^{-6}= 30 μs

Question 37 |

Let the size of congestion window of a TCP connection be 32 KB when a timeout occurs. The round trip time of the connection is 100 msec and the maximum segment size used is 2 KB. The time taken (in msec) by the TCP connection to get back to 32 KB congestion window is _________.

1100 to 1300 | |

1101 to 1301 | |

1102 to 1302 | |

1103 to 1303 |

Question 37 Explanation:

Given that at the time of Time Out, Congestion Window Size is 32KB and RTT = 100ms

When Time Out occurs, for the next round of Slow Start, Threshold = (size of Cwnd) / 2

It means Threshold = 16KB

Slow Start

2KB

1RTT

4KB

2RTT

8KB

3RTT

16KB ----------- Threshold reaches. So Additive Increase Starts

4RTT

18KB

5RTT

20KB

6RTT

22KB

7RTT

24KB

8RTT

26KB

9RTT

28KB

10RTT

30KB

11RTT

32KB

So, Total no. of RTTs = 11 → 11 * 100 = 1100

When Time Out occurs, for the next round of Slow Start, Threshold = (size of Cwnd) / 2

It means Threshold = 16KB

Slow Start

2KB

1RTT

4KB

2RTT

8KB

3RTT

16KB ----------- Threshold reaches. So Additive Increase Starts

4RTT

18KB

5RTT

20KB

6RTT

22KB

7RTT

24KB

8RTT

26KB

9RTT

28KB

10RTT

30KB

11RTT

32KB

So, Total no. of RTTs = 11 → 11 * 100 = 1100

Question 38 |

Consider a selective repeat sliding window protocol that uses a frame size of 1 KB to send data on a 1.5 Mbps link with a one-way latency of 50 msec. To achieve a link utilization of 60%, the minimum number of bits required to represent the sequence number field is ________.

5 | |

6 | |

7 | |

8 |

Question 38 Explanation:

Given L=1 KB

B=1.5 Mbps

T

η=60%

Efficiency formula for SR protocol is

η=W/(1+2a)⇒60/100=W/(1+2a) (∵a=T

T

a=T

⇒ 60/100=W/19.86⇒W=11.9≈12

⇒ W=2

B=1.5 Mbps

T

_{p}=50 msη=60%

Efficiency formula for SR protocol is

η=W/(1+2a)⇒60/100=W/(1+2a) (∵a=T

_{p}/T_{x})T

_{x}=L/B=8×10^{3}/1.5×10^{6}=5.3msa=T

_{p}/T_{x}=50/5.3=500/53=9.43⇒ 60/100=W/19.86⇒W=11.9≈12

⇒ W=2

^{n-1}=12⇒2^{n}=24⇒2^{n}=24≈2^{5}⇒n=5Question 39 |

Consider the following four schedules due to three transactions (indicated by the subscript) using read and write on a data item x, denoted by r(x) and w(x) respectively. Which one of them is conflict serializable?

r _{1} (x); r_{2} (x); w_{1} (x); r_{3} (x); w_{2} (x) | |

r _{2} (x);r_{1} (x);w_{2} (x);r_{3} (x);w_{1} (x) | |

r _{3} (x);r_{2} (x);r_{1} (x);w_{2} (x);w_{1} (x) | |

r _{2} (x);w_{2} (x);r_{3} (x);r_{1} (x);w_{1} (x) |

Question 39 Explanation:

Option: A

- Polygraph contains cycle. So, not a conflict serializable.

Option: B

-Cyclic

Option: C

- Cyclic

Option: D

- Acyclic, so conflict serializable.

- Polygraph contains cycle. So, not a conflict serializable.

Option: B

-Cyclic

Option: C

- Cyclic

Option: D

- Acyclic, so conflict serializable.

Question 40 |

S1 is TRUE and S2 is FALSE. | |

Both S1 and S2 are TRUE. | |

S1 is FALSE and S2 is TRUE. | |

Both S1 and S2 are FALSE. |

Question 40 Explanation:

S1: True

If we can prove the relation is in BCNF then by default it would be in 1NF, 2NF, 3NF also.

Let R(AB) be a two attribute relation, then

If {A→B} exists then BCNF since {A}

If {B→A} exists then BCNF since {B}

If {A→B, B→A} exists then BCNF since A and B both are Super Key now.

If {No non-trivial Functional Dependency} then default BCNF.

Hence it’s proved that a Relation with two single-valued attributes is in BCNF hence it’s also in 1NF, 2NF, 3NF.

S2: False

The canonical cover for the given FD set is {AB→C, D→E, AB→E, E→C}. As we can see AB→E is not covered in minimal cover since {AB}

If we can prove the relation is in BCNF then by default it would be in 1NF, 2NF, 3NF also.

Let R(AB) be a two attribute relation, then

If {A→B} exists then BCNF since {A}

^{+}= AB = RIf {B→A} exists then BCNF since {B}

^{+}= AB = RIf {A→B, B→A} exists then BCNF since A and B both are Super Key now.

If {No non-trivial Functional Dependency} then default BCNF.

Hence it’s proved that a Relation with two single-valued attributes is in BCNF hence it’s also in 1NF, 2NF, 3NF.

S2: False

The canonical cover for the given FD set is {AB→C, D→E, AB→E, E→C}. As we can see AB→E is not covered in minimal cover since {AB}

^{+}= ABC in the given cover {AB→C, D→E, E→C}Question 41 |

Only REQ1 can be permitted. | |

Only REQ2 can be permitted. | |

Both REQ1 and REQ2 can be permitted. | |

Neither REQ1 nor REQ2 can be permitted. |

Question 41 Explanation:

Lets take 1st case,

After allowing Req 1,

Available: X=3, Y=2, Z=0

With this we can satisfy P1's requirement. So available becomes: X=6, Y=4, Z=0.

Since Z is not available, neither P0's nor P2's requirement can be satisfied. So, it is an unsafe state.

Lets take 2nd case,

After allowing Req 2,

Available: X=1, Y=2, Z=2

With this we can satisfy any one of P1's or P2's requirement. Lets first satisfy P1's requirement. So Available now becomes:

X=6, Y=4, Z=2

Now with the availability we can satisfy P2's requirement. So Available now becomes,

X=8, Y=5, Z=3

With this availability P0 can also be satisfied. So, hence it is in safe state.

So from above two cases Req 1 cannot be permitted but Req 2 can be permitted.

After allowing Req 1,

Available: X=3, Y=2, Z=0

With this we can satisfy P1's requirement. So available becomes: X=6, Y=4, Z=0.

Since Z is not available, neither P0's nor P2's requirement can be satisfied. So, it is an unsafe state.

Lets take 2nd case,

After allowing Req 2,

Available: X=1, Y=2, Z=2

With this we can satisfy any one of P1's or P2's requirement. Lets first satisfy P1's requirement. So Available now becomes:

X=6, Y=4, Z=2

Now with the availability we can satisfy P2's requirement. So Available now becomes,

X=8, Y=5, Z=3

With this availability P0 can also be satisfied. So, hence it is in safe state.

So from above two cases Req 1 cannot be permitted but Req 2 can be permitted.

Question 42 |

7.2 | |

7.3 | |

7.4 | |

7.5 |

Question 42 Explanation:

Using SRTF:

TAT(A) = 8-0 = 8, TAT(B)= 5-3=2, TAT(C)= 12-5=7, TAT(D)= 21-7= 14, TAT(E)=15-10=5

Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms

TAT(A) = 8-0 = 8, TAT(B)= 5-3=2, TAT(C)= 12-5=7, TAT(D)= 21-7= 14, TAT(E)=15-10=5

Average turnaround time = 8+2+7+14+5/ 5 = 7.2ms

Question 43 |

Assume that there are 3 page frames which are initially empty. If the page reference string is 1, 2, 3, 4, 2, 1, 5, 3, 2, 4, 6, the number of page faults using the optimal replacement policy is__________.

7 | |

8 | |

9 | |

10 |

Question 43 Explanation:

Total 7 faults are there.

Question 44 |

a shift-reduce conflict and a reduce-reduce conflict. | |

a shift-reduce conflict but not a reduce-reduce conflict. | |

a reduce-reduce conflict but not a shift-reduce conflict. | |

neither a shift-reduce nor a reduce-reduce conflict. |

Question 44 Explanation:

The input symbol is “<” which is not in canonical set of item, so it is neither a shift-reduce nor a reduce-reduce conflict with reference to “<” symbol.

But if it would have asked about “>” then it will be a SR conflict.

But if it would have asked about “>” then it will be a SR conflict.

Question 45 |

Neither L nor is recursively enumerable (r.e.). | |

One of L and is r.e. but not recursive; the other is not r.e. | |

Both L and are r.e. but not recursive. | |

Both L and are recursive. |

Question 45 Explanation:

If both L and L’ are recursively enumerable, then L must be recursive. Hence, both L and L´ are recursively enumerable, but not recursive is not a viable possibility.

Question 46 |

I and II only | |

I and III only | |

II and III only | |

I, II, and III |

Question 46 Explanation:

The DFA accepts the language “all strings ending with 1”.

So the regular expression corresponding to DFA is (0+1)*1.

Now, by using state elimination method,

So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.

But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.

So the regular expression corresponding to DFA is (0+1)*1.

Now, by using state elimination method,

So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.

But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.

Question 47 |

There are 5 bags labeled 1 to 5. All the coins in a given bag have the same weight. Some bags have coins of weight 10 gm, others have coins of weight 11 gm. I pick 1, 2, 4, 8, 16 coins respectively from bags 1 to 5. Their total weight comes out to 323 gm. Then the product of the labels of the bags having 11 gm coins is _______.

12 | |

13 | |

14 | |

15 |

Question 47 Explanation:

Bags: 1 2 3 4 5

No. of coins picked: 1 2 4 8 16

There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.

Let there be x number of 10gm coins and y number of 11gm coins.

So, 10x + 11y = 323 ------ (1)

And we also know that total number of coins picked is

1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,

= 31 ------ (2)

Solving equation (1) and (2), we get

y = 13

Means total there are 13 coins of 11gm.

Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.

So product of labelled bag number = 1×3×4 = 12

No. of coins picked: 1 2 4 8 16

There are two types of weights of coin, i.e., 10gm and 11gm. And total weight of picked coins are 323gm.

Let there be x number of 10gm coins and y number of 11gm coins.

So, 10x + 11y = 323 ------ (1)

And we also know that total number of coins picked is

1 + 2 + 4 + 8 + 16 = 31 which is equal to x + y, so,

= 31 ------ (2)

Solving equation (1) and (2), we get

y = 13

Means total there are 13 coins of 11gm.

Now we can chose bag number 1, 3 and 4, we will get a total sum of 13 coins picked from them.

So product of labelled bag number = 1×3×4 = 12

Question 48 |

Suppose a polynomial time algorithm is discovered that correctly computes the largest clique in a given graph. In this scenario, which one of the following represents the correct Venn diagram of the complexity classes P, NP and NP Complete (NPC)?

Question 48 Explanation:

The most important open question in complexity theory is whether the P = NP, which asks whether polynomial time algorithms actually exist for NP-complete and all NP problems (since a problem “C” is in NP-complete, iff C is in NP and every problem in NP is reducible to C in polynomial time). In the given question it is given that some polynomial time algorithm exists which computes the largest clique problem in the given graph which is known NP-complete problem. Hence P=NP=NP-Complete.

Question 49 |

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is _________________.

148 | |

149 | |

150 | |

151 |

Question 49 Explanation:

The minimum number of comparisons required to find the minimum and the maximum of 100 numbers is 3n/2 – 2 = 148. (∵ T(n) = T(floor(n/2))+T(ceil(n/2))+2)

Question 50 |

Consider a hash table with 9 slots. The hash function is h(k) = k mod 9. The collisions are resolved by chaining. The following 9 keys are inserted in the order: 5, 28, 19, 15, 20, 33, 12, 17, 10. The maximum, minimum, and average chain lengths in the hash table, respectively, are

3, 0, and 1 | |

3, 3, and 3 | |

4, 0, and 1 | |

3, 0, and 2 |

Question 50 Explanation:

Hash table has 9 slots.

h(k) = k mod 9

Collisions are resolved using chaining.

Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5

28%9 – 1

19%9 – 1

15%9 – 6

20%9 – 2

33%9 – 6

12%9 – 3

17%9 – 8

10%9 – 1

Maximum chain length is 3

Minimum chain length is 0

Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1

h(k) = k mod 9

Collisions are resolved using chaining.

Keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.

5%9 – 5

28%9 – 1

19%9 – 1

15%9 – 6

20%9 – 2

33%9 – 6

12%9 – 3

17%9 – 8

10%9 – 1

Maximum chain length is 3

Minimum chain length is 0

Average chain length = 0+3+1+1+0+1+2+0+1/ 9 = 1

Question 51 |

maximum possible sum of elements in any sub-array of array E. | |

maximum element in any sub-array of array E. | |

sum of the maximum elements in all possible sub-arrays of array E. | |

the sum of all the elements in the array E. |

Question 51 Explanation:

Y=0

for (i=0; i
Y=Y+E[i] // E is an array, this statement calculates the sum of elements of the array E and stores it in Y.

for (i=0; i
for(j=i; j
{

Z=0;

for(k=i; k<=j; k++)

Z=Z+E[k];

// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].

Store the current sum in Z.

If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

for (i=0; i

for (i=0; i

Z=0;

for(k=i; k<=j; k++)

Z=Z+E[k];

// It calculates the sum of all possible subarrays starting from 0 i.e., the loop will iterate for all the elements of array E and for every element, calculate sum of all sub arrays starting with E[i].

Store the current sum in Z.

If Z is greater than Y then update Y and return Y. So it returns the maximum possible sum of elements in any sub array of given array E.

Question 52 |

Half of the product of the 3 consecutive integers. | |

One-third of the product of the 3 consecutive integers. | |

One-sixth of the product of the 3 consecutive integers. | |

None of the above. |

Question 52 Explanation:

D = 2

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3;

Also you can try for smaller ‘n’.

for i = 1 to n do

for j = i to n do

for k = j + 1 to n do

D = D * 3;

Also you can try for smaller ‘n’.

Question 53 |

Consider a 6-stage instruction pipeline, where all stages are perfectly balanced. Assume that there is no cycle-time overhead of pipelining. When an application is executing on this 6-stage pipeline, the speedup achieved with respect to non-pipelined execution if 25% of the instructions incur 2 pipeline stall cycles is ______________________.

4 | |

5 | |

6 | |

7 |

Question 53 Explanation:

For 6 stages, non- pipelining takes 6 cycles.

There were 2 stall cycles for pipelining for 25% of the instructions.

So pipeline time =(1+(25/100)*2)=3/2=1.5

Speed up =Non-pipeline time / Pipeline time=6/1.5=4

There were 2 stall cycles for pipelining for 25% of the instructions.

So pipeline time =(1+(25/100)*2)=3/2=1.5

Speed up =Non-pipeline time / Pipeline time=6/1.5=4

Question 54 |

An access sequence of cache block addresses is of length N and contains n unique block addresses. The number of unique block addresses between two consecutive accesses to the same block address is bounded above by k. What is the miss ratio if the access sequence is passed through a cache of associativity A≥k exercising least-recently-used replacement policy?

n⁄N | |

1⁄N | |

1⁄A | |

k⁄n |

Question 54 Explanation:

Consider the scenario, you have k-way set associative cache, let us say a block b0 comes to set-0 and then there are k-1 unique blocks to the same set. Now the set-0 is full then one more block came to set-0 and the block b0 is replaced using LRU, if b0 comes again then it will cause a miss. But it is given that the set associativity A>=k, means the no. of blocks in a set is k or more so assume we have (k+1)-way set associativity, applying the above logic b0 comes first and then k-1 other unique accesses come to the same set-0 then there is still place for one more block in set-0 and if b0 comes again now then it will not cause a miss. As the associativity increases further there will not be any more misses other than the unique blocks we have a best case scenario. So out of N accesses only the unique blocks n can be missed and the miss ratio is n/N.

As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.

As the set associativity size keeps increasing then we don't have to replace any block, so LRU is not of any significance here.

Question 55 |

Question 55 Explanation:

F(P,Q,R)= P’Q’ (0) + P’Q (1) + PQ’ (R) + PQ(R’)

= P’Q + PQ’R + PQR’

= Q(P’ + P R’) + PQ’R

= Q(P’ + R’) + PQ’R

= P’Q + QR’ + PQ’R

= P’Q + PQ’R + PQR’

= Q(P’ + P R’) + PQ’R

= Q(P’ + R’) + PQ’R

= P’Q + QR’ + PQ’R

Question 56 |

The function f(x) = x sinx satisfies the following equation: f ''(x) + f(x)+ tcosx = 0. The value of t is __________.

-2 | |

-3 | |

-4 | |

-5 |

Question 56 Explanation:

f(x) = x Sinx

f ’(x) = x(Sinx)’ + Sin(x)(x’)

= xCosx + Sinx ---------①

f ’’(x) = x (Cosx)’ + Cos (x)’+ Cos x

= -x Sinx + 2Cosx -----------②

Given: f ’’(x) + f(x) + t Cosx = 0

Replace ① & ②,

-xSinx + 2Cosx + xSinx + tCosx = 0

2Cosx + tCosx = 0

t = -2

f ’(x) = x(Sinx)’ + Sin(x)(x’)

= xCosx + Sinx ---------①

f ’’(x) = x (Cosx)’ + Cos (x)’+ Cos x

= -x Sinx + 2Cosx -----------②

Given: f ’’(x) + f(x) + t Cosx = 0

Replace ① & ②,

-xSinx + 2Cosx + xSinx + tCosx = 0

2Cosx + tCosx = 0

t = -2

Question 57 |

A function f(x) is continuous in the interval [0,2]. It is known that f(0) = f(2) = -1 and f(1) = 1. Which one of the following statements must be true?

There exists a y in the interval (0,1) such that f(y)=f(y+1) | |

For every y in the interval (0,1),f(y)=f(2-y) | |

The maximum value of the function in the interval (0,2) is 1 | |

There exists a y in the interval (0, 1) such that f(y)=-f(2-y) |

Question 57 Explanation:

Consider this function as sum of two functions as,
g(y) = f(y) -f(y+1)

Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1]

g(0) = -2, g(1) = 2

Since g is continuous and goes from negative to positive value in [0,1]. Therefore at some point g would be 0 in (0,1).

g=0 ⇒ f(y) = f(y+1) for some y in (0,1).

Apply similar logic to option D, Let g(y) = f(y) + f(2 - y)

Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1] (sum of two continuous functions is continuous)

g(0) = -2, g(1) = 2

Since g is continuous and goes from negative to positive value in [0, 1]. Therefore at some point g would be 0 in (0, 1).

There exists y in the interval (0, 1) such that:

g=0 ⇒ f(y) = -f(2 – y)

Both A, D are answers.

Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1]

g(0) = -2, g(1) = 2

Since g is continuous and goes from negative to positive value in [0,1]. Therefore at some point g would be 0 in (0,1).

g=0 ⇒ f(y) = f(y+1) for some y in (0,1).

Apply similar logic to option D, Let g(y) = f(y) + f(2 - y)

Since function f is continuous in [0, 2], therefore g would be continuous in [0, 1] (sum of two continuous functions is continuous)

g(0) = -2, g(1) = 2

Since g is continuous and goes from negative to positive value in [0, 1]. Therefore at some point g would be 0 in (0, 1).

There exists y in the interval (0, 1) such that:

g=0 ⇒ f(y) = -f(2 – y)

Both A, D are answers.

Question 58 |

Four fair six-sided dice are rolled. The probability that the sum of the results being 22 is X⁄1296. The value of X is ___________.

10 | |

11 | |

12 | |

13 |

Question 58 Explanation:

Each dice can result from {1, 2, 3, 4, 5, 6}

To get ‘22’ as Sum of four outcomes

x

The maximum Sum = 6+6+6+6 = 24 which is near to 22

So, keeping three 6’s, 6+6+6+x = 22

x = 4 combination① = 6 6 6 4

Keeping two 6’s, 6+6+x

x

combination② = 6 6 5 5

No. of permutation with 6664 = 4!/ 3! = 4

“ “ “ 6655 = 4!/ 2!2! = 6

Total = 4+6 = 10 ways out of 6×6×6×6 = 1296

Pnb (22) = 10/1296 ⇒ x = 10

To get ‘22’ as Sum of four outcomes

x

_{1}+ x_{2}+ x_{3}+ x_{4}= 22The maximum Sum = 6+6+6+6 = 24 which is near to 22

So, keeping three 6’s, 6+6+6+x = 22

x = 4 combination① = 6 6 6 4

Keeping two 6’s, 6+6+x

_{1}+x_{2}= 22x

_{1}+x_{2}= 10 possible x’s (5, 5) onlycombination② = 6 6 5 5

No. of permutation with 6664 = 4!/ 3! = 4

“ “ “ 6655 = 4!/ 2!2! = 6

Total = 4+6 = 10 ways out of 6×6×6×6 = 1296

Pnb (22) = 10/1296 ⇒ x = 10

Question 59 |

A pennant is a sequence of numbers, each number being 1 or 2. An n-pennant is a sequence of numbers with sum equal to n. For example, (1,1,2) is a 4-pennant. The set of all possible 1-pennants is {(1)}, the set of all possible 2-pennants is {(2), (1,1)}and the set of all 3-pennants is {(2,1), (1,1,1), (1,2)}. Note that the pennant (1,2) is not the same as the pennant (2,1). The number of 10-pennants is ______________.

89 | |

90 | |

91 | |

92 |

Question 59 Explanation:

No twos: 1111111111⇒ 1 pennant

Single two: 211111111 ⇒ 9!/8!1! = 9 pennants

Two twos: 22111111 ⇒ 8!/6!2! = 28

Three twos: 2221111 ⇒ 7!/3!4! = 35

Four twos: 222211 ⇒ 6!/4!2! = 15

Five twos: 22222 ⇒ 1

Total = 89 pennants.

Single two: 211111111 ⇒ 9!/8!1! = 9 pennants

Two twos: 22111111 ⇒ 8!/6!2! = 28

Three twos: 2221111 ⇒ 7!/3!4! = 35

Four twos: 222211 ⇒ 6!/4!2! = 15

Five twos: 22222 ⇒ 1

Total = 89 pennants.

Question 60 |

Let S denote the set of all functions f:{0,1}

^{4 }→ {0,1}. Denote by N the number of functions from S to the set {0,1}. The value of log_{2 }log_{2}N is ______.16 | |

17 | |

18 | |

19 |

Question 60 Explanation:

The number of functions from A to B where size of A=|A| and size of B=|B| is |B|

{0,1}

|S|=2

N=2

loglogN=loglog2

^{|A|}{0,1}

^{4}={0,1}×{0,1}×{0,1}×{0,1}=16|S|=2

^{16}N=2

^{|S|}loglogN=loglog2

^{|S|}=log |S| =log2^{16}=16Question 61 |

Consider an undirected graph where self-loops are not allowed. The vertex set of G is {(i,j): 1 ≤ i ≤ 12, 1 ≤ j ≤ 12}. There is an edge between (a,b) and (c,d) if |a - c| ≤ 1 and |b - d| ≤ 1. The number of edges in this graph is __________.

506 | |

507 | |

508 | |

509 |

Question 61 Explanation:

The total number of vertices in the graph is 12*12=144. The vertices are allowed to connect in both horizontal and vertical directions which are separated by at most 1 distance.

If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.

From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.

⇒ (4*3) + (40*5) + (100*8) = 2*E

⇒ 1012=2*E

⇒ E=506

If we observe the graph, it looks like a 12 by 12 grid. Each corner vertex has a degree of 3 and we have 4 corner vertices. 40 external vertices of degree 5 and remaining 100 vertices of degree 8.

From Handshaking theorem, sum of the degrees of the vertices is equal to the 2*number of edges in the graph.

⇒ (4*3) + (40*5) + (100*8) = 2*E

⇒ 1012=2*E

⇒ E=506

Question 62 |

An ordered -tuple (d

_{1}, d_{2}, ..., d_{n}) with d_{1}≥ d_{2}≥ ... d_{n}is called graphic if there exists a simple undirected graph with n vertices having degrees d_{1}, d_{2}, ..., d_{n}respectively. Which of the following 6-tuples is NOT graphic?(1, 1, 1, 1, 1, 1) | |

(2, 2, 2, 2, 2, 2) | |

(3, 3, 3, 1, 0, 0) | |

(3, 2, 1, 1, 1, 0) |

Question 62 Explanation:

This can be checked by Havel-hakimi theorem:

A) (1, 1, 1, 1, 1, 1)

Yes, it is a graph.

We will see that option (C) is not graphic.

A) (1, 1, 1, 1, 1, 1)

Yes, it is a graph.

We will see that option (C) is not graphic.

Question 63 |

Which one of the following propositional logic formulas is TRUE when exactly two of p, q, and r are TRUE?

((p↔q)∧r)∨(p∧q∧∼r) | |

(∼(p↔q )∧r)∨(p∧q∧∼r) | |

((p→q)∧r)∨(p∧q∧∼r) | |

(∼(p↔q)∧r)∧(p∧q∧∼r) |

Question 63 Explanation:

Method 1: construct the tables for all options and check with T, T, F combinations.

Method2: directly check with one of {TTF, TFT, FTT} options.

As there are two T’s in each option, replace them and check with the third value.

Eg: Place p=q= T

(∼(p↔q)∧r)∨(p∧q∧∼r)

=(∼(T↔T)∧r)∨(T∧T∧∼r)

=(∼(T)∧r)∨(T∧∼r)

=(F∧r)∨(T∧∼r)

=(F)∨(∼r)

=∼r

This is true for r=F.

Similarly with p=r=T and q=F.

q=r=T and p=F

Option B is the answer.

Method2: directly check with one of {TTF, TFT, FTT} options.

As there are two T’s in each option, replace them and check with the third value.

Eg: Place p=q= T

(∼(p↔q)∧r)∨(p∧q∧∼r)

=(∼(T↔T)∧r)∨(T∧T∧∼r)

=(∼(T)∧r)∨(T∧∼r)

=(F∧r)∨(T∧∼r)

=(F)∨(∼r)

=∼r

This is true for r=F.

Similarly with p=r=T and q=F.

q=r=T and p=F

Option B is the answer.

Question 64 |

It executes but does not give the correct result. | |

It executes and gives the correct result. | |

It generates an error because of pairwise comparison. | |

It generates an error because the GROUP BY clause cannot be used with table joins in a subquery. |

Question 64 Explanation:

The given SQL query will display the last names and hire-dates of all latest hires in their respective departments in the location ID 1700. So, correct option is (B).

Question 65 |

Consider two processors P

_{1}and P_{2}executing the same instruction set. Assume that under identical conditions, for the same input, a program running on P_{2}takes 25% less time but incurs 20% more CPI (clock cycles per instruction) as compared to the program running on P_{1}. If the clock frequency of P_{1}is 1GHz, then the clock frequency of P_{2}(in GHz) is _________.1.6 | |

1.7 | |

1.8 | |

1.9 |

Question 65 Explanation:

1 cycle time for P

Assume P

P

Assume P

P

_{1}=10^{9}/ 1GH=1 nsAssume P

_{1}takes 5 cycles for a program then P_{2}takes 20%more, means, 6 cycles.P

_{2}takes 25% less time, means, if P_{1}takes 5 ns, then P_{2}takes 3.75 ns.Assume P

_{2}clock frequency is x GHz.P

_{2}taken 6 cycles, so 6×10^{9}/x GH=3.75, x=1.6
There are 65 questions to complete.