GATE IT 2008

Question 1
A set of Boolean connectives is functionally complete if all Boolean functions can be synthesized using those. Which of the following sets of connectives is NOT functionally complete?
A
EX-NOR
B
implication, negation
C
OR, negation
D
NAND
Digital Logic   Boolean Algebra
Question 2
A sample space has two events A and B such that probabilities
P(A\cap B) = \dfrac{1}{2}, P(A') = \dfrac{1}{3}, P(B') =\dfrac{1}{3}.
What is P(A\cup B) ?
A
\left(\dfrac{11}{12}\right)
B
\left(\dfrac{10}{12}\right)
C
\left(\dfrac{9}{12}\right)
D
\left(\dfrac{8}{12}\right)
Discrete Mathematics   Probability Theory
Question 3
What is the chromatic number of the following graph?

A
2
B
3
C
4
D
5
Discrete Mathematics   Graph Theory
Question 4
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes
A
5
B
4
C
3
D
2
Discrete Mathematics   Graph Theory
Question 5
Which of the following regular expressions describes the language over\{0, 1\} consisting of strings that contain exactly two 1's?
A
(0 + 1)^ * \ 11(0 + 1) ^*
B
0 ^* \ 110 ^*
C
0 ^* 10 ^* 10 ^*
D
(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*
Theory of Computation   Regular Expression
Question 6
Let N be an NFA with n states and let M be the minimized DFA with m states recognizing the same language. Which of the following in NECESSARILY true?
A
m \leq 2^n
B
n \leq m
C
M has one accept state
D
m = 2^n
Theory of Computation   Finite Automata
Question 7
The following bit pattern represents a floating point number in IEEE 754 single precision format
1 10000011 101000000000000000000000
The value of the number in decimal form is
A
-10
B
-13
C
-26
D
None of the above
Digital Logic   Number System
Question 8
Consider the following Boolean function of four variables
f(A, B, C, D) = \sum(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)
The function is
A
independent of one variable
B
independent of two variables
C
independent of three variable
D
dependent on all the variables
Digital Logic   Boolean Algebra
Question 9
What Boolean function does the circuit below realize?

A
xz + \bar{x}\bar{z}
B
x\bar{z} + \bar{x}{z}
C
\bar{x}\bar{y} + {y}{z}
D
xy + \bar{y}\bar{z}
Digital Logic   Combinational Circuit
Question 10
Arrange the following functions in increasing asymptotic order:
a. n^{1/3}
b. e^n
c. n^{7/4}
d. n \log^9n
e. 1.0000001^n
A
a, d, c, e, b
B
d, a, c, e, b
C
a, c, d, e, b
D
a, c, d, b, e
Algorithm   Asymptotic Notation
There are 10 questions to complete.

Leave a Comment