# 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 1 Explanation:
 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 2 Explanation:
 Question 3
What is the chromatic number of the following graph?

 A 2 B 3 C 4 D 5
Discrete Mathematics   Graph Theory
Question 3 Explanation:
 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 4 Explanation:
 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 5 Explanation:
 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 6 Explanation:
 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 7 Explanation:
 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 8 Explanation:
 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 9 Explanation:
 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
Question 10 Explanation:
There are 10 questions to complete.