GATE CSE 2014 SET-3
Q11.
Consider the following minterm expression for F. F(P,Q,R,S) = \Sigma 0, 2, 5, 7, 8, 10, 13, 15 The minterms 2, 7, 8 and 13 are 'do not care terms. The minimal sum of-products form for F isQ12.
Consider the set of all functions f:{0,1,...,2014}\rightarrow{0,1...,2014} such that f(f(i))=i, for 0\leqi\leq2014 . Consider the following statements. P. For each such function it must be the case that for every i, f(i) = i, Q. For each such function it must be the case that for some i,f(i) = i, R. Each such function must be onto. Which one of the following is CORRECT?Q13.
If G is a forest with n vertices and k connected components, how many edges does G have?Q14.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.Q15.
Let \oplus denote the Exclusive OR (XOR) operation. Let '1' and '0' denote the binary constants. Consider the following Boolean Algebra for F over two variables P and Q. F(P,Q)=((1\oplus P)\oplus (P\oplus Q)) \oplus ((P\oplus Q) \oplus (Q\oplus 0)) The equivalent expression for F isQ16.
Suppose depth first search is executed on the graph below starting at some unknown vertex. Assume that a recursive call to visit a vertex is made only after first checking that the vertex has not been visited earlier. Then the maximum possible recursion depth (including the initial call) is _________.Q17.
There are two elements x,y in a group (G,*) such that every element in the group can be written as a product of some number of x's and y's in some order. It is known that x * x = y * y = x * y *x * y = y* x * y *x = e where e is the identity element. The maximum number of elements in such a group is _______.Q18.
Let G be a group with 15 elements. Let L be a subgroup of G. It is known that L\neqG and that the size of L is at least 4. The size of L is _______.Q19.
Consider a hash table with 100 slots. Collisions are resolved using chaining. Assuming simple uniform hashing, what is the probability that the first 3 slots are unfilled after the first 3 insertions?Q20.
Consider the following combinational function block involving four Boolean variables x, y, a, b where x, a, b are inputs and y is the output. f (x, y, a, b) { if (x is 1) y = a; else y = b; } Which one of the following digital logic blocks is the most suitable for implementing this function?