GATE CSE 2018 Paper 1 — page 14

Questions 40–42 of 65. Imported answers require review unless explicitly marked reviewed.

Let G be a simple undirected graph. Let T_D be a depth first search tree of G. Let T_B be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to T_D. (A cross edge in G is between two nodes neither of which is an ancestor of the other in T_D.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in T_B, then

. Which of the statements above must necessarily be true?

Your answerChoose one option.

I only

II only

Both I and II

Neither I nor II

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Assume that multiplying a matrix G_i of dimension p × q with another matrix G_j of dimension q × r requires pqr scalar multiplications. Computing the product of n matrices G_1G_2G_3...G_n can be done by parenthesizing in different ways. Define G_iG_ as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain G_1G_2G_3G_4G_5G_6 using parenthesization (G_1(G_2G_3))(G_4(G_5G_6)), G_2G_3 and G_5G_6 are the only explicitly computed pairs. Consider a matrix multiplication chain F_1F_2F_3F_4F_5, where matrices F_1, F_2, F_3, F_4 and F_5 are of dimensions 2×25, 25×3, 3×16, 16×1 and 1×1000, respectively. In the parenthesization of F_1F_2F_3F_4F_5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

Your answerChoose one option.

F_1F_2 and F_3F_4 only

F_2F_3 only

F_3F_4 only

F_1F_2 and F_4F_5 only

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

Consider the following C code. Assume that unsigned long int type length is 64 bits.

unsigned long int fun(unsigned long int n){

unsigned long int i, j = 0, sum = 0;

for (i = n; i > 1; i = i/2) j++;

for (; j > 1; j = j/2) sum++;

return(sum);

}

The value returned when we call fun with the input

Your answerChoose one option.

You can attempt this question now. Sign in to view the answer key, explanations and discussion.Log in to check answer

2018 · Paper 1

Question 30

Question 31

Question 32