## GATE 2010

Question 1 |

Let G = (V,E) be a graph. Define ξ(G) = Σd id x d, where id is the number of vertices of degree d in G. If S and T are two different trees with ξ(S) = ξ(T),then

|S| = 2|T| | |

|S| = |T| - 1 | |

|S| = |T| | |

|S| = |T| + 1 |

i

_{d}= no. of vertices of degree ‘d’ in ‘G’

Eg:

No. of vertices with degree ‘2’ = 3

ξ(G') = 3 × 2 = '6' i.e., sum of degrees

By Handshaking Theorem,

The sum of degrees would be equal to twice the no. of edges

|V| = 2|E|

It is given that ξ(G) = ξ(S) then

Sum of degrees of vertices in G is equal to sum of degrees of vertices in S

i.e., 2*(no. of edges in G) = 2*no. of edges in S no. of edges in G = no. of edges in S

Eg:

ξ(G) = (2 × 2) + (2 × 3) = 4 + 6 = 10

ξ(S) = 2 × 5 = 10

You can observe that, though no. of vertices are different, but still no. of edges are same.

Question 2 |

Newton-Raphson method is used to compute a root of the equation x^{2} - 13 = 0 with 3.5 as the initial value. The approximation after one iteration is

3.575 | |

3.676 | |

3.667 | |

3.607 |

Question 3 |

What is the possible number of reflexive relations on a set of 5 elements?

2 ^{10} | |

2 ^{15} | |

2 ^{20} | |

2 ^{25} |

Definition of Reflexive relation:

A relation ‘R’ is reflexive if it contains xRx ∀ x∈A

A relation with all diagonal elements, it can contain any combination of non-diagonal elements.

Eg:

A={1, 2, 3}

So for a relation to be reflexive, it should contain all diagonal elements. In addition to them, we can have possible combination of (n

^{2}-n)non-diagonal elements (i.e., 2

^{n2-n})

Ex:

{(1,1)(2,2)(3,3)} ----- ‘0’ non-diagonal element

{(1,1)(2,2)(3,3)(1,2)} ----- ‘1’ non-diagonal element

{(1,1)(2,2)(3,3)(1,2)(1,3)} “

___________ “

___________ “

{(1,1)(2,2)(3,3)(1,2)(1,3)(2,1)(2,3)(3,1)(3,2)} (n

^{2}-n) diagonal elements

____________________

Total: 2

^{n2-n}

For the given question n = 5.

The number of reflexive relations = 2

^{(25-5)}= 2

^{20}

Question 4 |

Consider the set S = {1, ω, ω^{2}}, where ω and ω^{2} are cube roots of unity. If * denotes the multiplication operation, the structure (S,*) forms

A group | |

A ring | |

An integral domain | |

A field |

1) Closure

2) Associativity

3) Have Identity element

4) Invertible

Over ‘*’ operation the S = {1, ω, ω

^{2}} satisfies the above properties.

The identity element is ‘1’ and inverse of 1 is 1, inverse of ‘w’ is 'w

^{2}' and inverse of 'w

^{2}' is 'w'.

Question 5 |

What is the value of

0 | |

e ^{-2} | |

e ^{-1/2} | |

1 |

Question 6 |

The minterm expansion of is

m _{2}+m_{4}+m_{6}+m_{7} | |

m _{0}+m_{1}+m_{3}+m_{5} | |

m _{0}+m_{1}+m_{6}+m_{7} | |

m _{2}+m_{3}+m_{4}+m_{5} |

= PQR + PQR' + PQR' + P'QR' + PQR' + PQ'R'

= PQR + PQR' + P'QR' + PQ'R'

= m

_{7}+ m

_{6}+ m

_{2}+ m

_{4}

Question 7 |

A main memory unit with a capacity of 4 megabytes is built using 1M 1-bit DRAM chips. Each DRAM chip has 1K rows of cells with 1K cells in each row. The time taken for a single refresh operation is 100 nanoseconds. The time required to perform one refresh operation on all the cells in the memory unit is

100 nanoseconds | |

100*2 ^{10} nanoseconds | |

100*2 ^{20} nanoseconds | |

3200*2 ^{20} nanoseconds |

Required capacity = 4MB

Number of chips needed = 4M*8 bits / 1M x 1-bit = 32 (1M x 1-bit)/(1M x 1-bit) = 32

Irrespective of the number of chips, all chips can be refreshed in parallel.

And all the cells in a row are refreshed in parallel too. So, the total time for refresh will be number of rows times the refresh time of one row.

Here we have 1K rows in a chip and refresh time of single row is 100ns.

So total time required = 1K × 100

= 100 × 2

^{10}nanoseconds

Question 8 |

P is a 16-bit signed integer. The 2's complement representation of P is (F87B)_{16}. The 2's complement representation of 8*P is

(C3D8) _{16} | |

(187B) _{16} | |

(F878) _{16} | |

(987B) _{16} |

_{16}is 2's complement representation of P.

(F87B)

_{16}=(1111 1000 0111 1011)

_{2}. (It is a negative number which is in 2's complement form)

P = 1111 1000 0111 1011 (2's complement form)

8 * P = 2

^{3}* P = 1100 0011 1101 1000. ( NOTE: Left shift k times is equivalent to Multiplication by 2

^{k})

Hence, 1100 0011 1101 1000 is 2's complement representation of 8P.

1100 0011 1101 1000 = (C3D8)

_{16}.

Question 9 |

The Boolean expression for the output 'f' of the multiplexer shown below is

P⊕Q⊕R | |

P+Q+R | |

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

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

= (P⊕Q⊕R)

Question 10 |

In a binary tree with n nodes, every node has an odd number of descendants. Every node is considered to be its own descendant. What is the number of nodes in the tree that have exactly one child?

0 | |

1 | |

(n-1)/2 | |

n-1 |

Every node has an odd number of descendants.

Also given every node is considered to be its own descendant.

― This is even number of descendants (2), because A is also considered as a descendant.

― This is odd number of descendants (3), A, B, C are descendants here.

Condition satisfied – odd number, but number of nodes in a tree that has exactly one child is 0.

Question 11 |

What does the following program print?

#include void f(int *p, int *q) { p = q; *p = 2; } int i = 0, j = 1; int main() { f(&i, &j); printf("%d %d n", i, j); getchar(); return 0; }

2 2 | |

2 1 | |

0 1 | |

0 2 |

Both pointers points to j = 1

now *p = 2

where j is updated with value 2.

printf (i, j) i = 0, j = 2

Question 12 |

Two alternative packages A and B are available for processing a database having 10^{k} records. Package A requires 0.0001n^{2} time units and package B requires 10nlog_{10}n time units to process n records.What is the smallest value of k for which package B will be preferred over A?

12 | |

10 | |

6 | |

5 |

_{10}n is lesser than or equals to Package A 0.0001n

^{2}0 because n

^{2}is asymptotically larger than nlogn. Finally, 10nlog

_{10}n ≤ 0.0001n

^{2}

Let n = 10

^{k}records. Substitute into 10nlog

_{10}n ≤ 0.0001n

^{2}

10(10

^{k})log

_{10}10

^{k}≤ 0.0001(10

^{k})

^{2}

10

^{k+1}k ≤ 0.0001 × 10

^{2k}

k ≤ 10

^{2k−k−1−4}

k ≤ 10

^{k−5}

According to the problem value 6 is suitable for K.

Question 13 |

Which data structure in a compiler is used for managing information about variables and their attributes?

Abstract syntax tree | |

Symbol table | |

Semantic stack | |

Parse Table |

Question 14 |

Which languages necessarily need heap allocation in the runtime environment?

Those that support recursion | |

Those that use dynamic scoping | |

Those that allow dynamic data structures | |

Those that use global variables |

Question 15 |

One of the header fields in an IP datagram is the Time to Live (TTL) field. Which of the following statements best explains the need for this field?

It can be used to prioritize packets
| |

It can be used to reduce delays
| |

It can be used to optimize throughput | |

It can be used to prevent packet looping |

Question 16 |

Which one of the following is not a client server application?

Internet chat | |

Web browsing | |

E-mail | |

ping |