GATE CSE 2018
Q11.
Consider the minterm list form of a Boolean function F given below. F(P,Q,R,S)=\sum m(0,2,5,7,9,11)+d(3,8,10,12,14) Here, m denotes a minterm and d denotes a don't care term. The number of essential prime implicants of the function F is ______.Q12.
Let \bigoplus and \bigodot denote the Exclusive OR and Exclusive NOR operations, respectively. Which one of the following is NOT CORRECT?Q13.
Assume that multiplying a matrix G1 of dimension pxq with another matrix G2 of dimension pxq requires pqr scalar multiplications. Computing the product of n matrices G1G2G3...Gn can be done by parenthesizing in different ways. Define Gi Gi+1 as an explicitly computed pair for a given paranthesization if they are directly multiplied. For example, in the matrix multiplication chain G1G2G3G4G5G6 using parenthesization (G1(G2G3))(G4(G5G6)), G2G3 and G5G6 are the only explicitly computed pairs. Consider a matrix multiplication chain F1F2F3F4F5, where matrices F1, F2, F3, F4 and F5 are of dimensions 2x25, 25x3, 3x16, 16x1 and 1x1000, respectively. In the parenthesization of F1F2F3F4F5 that minimizes the total number of scalar multiplications, the explicitly computed pairs is/areQ14.
In an Entity-Relationship (ER) model, suppose R is a many-to-one relationship from entity set E1 to entity set E2. Assume that E1 and E2 participate totally in R and that the cardinality of E1 is greater than the cardinality of E2. Which one of the following is true about R?Q15.
Let G be a graph with 100! vertices, with each vertex labelled by a distinct permutation of the numbers 1,2,...,100. There is an edge between vertices u and v if and only if the label of u can be obtained by swapping two adjacent numbers in the label of v. Let y denote the degree of a vertex in G, and z denote the number of connected components in G. Then, y+ 10z = _____.Q16.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1. Which of the statements above must necessarily be true?Q18.
Let G be a simple undirected graph. Let TD be a depth first search tree of G. Let TB be a breadth first search tree of G. Consider the following statements. (I) No edge of G is a cross edge with respect to TD. (A cross edge in G is between two nodes neither of which is an ancestor of the other in TD.) (II) For every edge (u,v) of G, if u is at depth i and v is at depth j in TB, then |i-j|=1. Which of the statements above must necessarily be true?Q19.
Let G be a finite group on 84 elements. The size of a largest possible proper subgroup of G is ________.Q20.
Consider the following C program: #include < stdio.h > void fun1(char *s1, char *s2){ char *tmp; tmp = s1; s1 = s2; s2 = tmp; } void fun2(char **s1, char **s2){ char *tmp; tmp = *s1; *s1 = *s2; *s2 = tmp; } int main(){ char *str1 = "Hi", *str2 = "Bye"; fun1(str1, str2); printf("%s %s ", str1, str2); fun2(&str1, &str2); printf("%s %s", str1, str2); return 0; } The output of the program above is