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?
EX-NOR | |
implication, negation | |
OR, negation | |
NAND |
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) ?
P(A\cap B) = \dfrac{1}{2}, P(A') = \dfrac{1}{3}, P(B') =\dfrac{1}{3}.
What is P(A\cup B) ?
\left(\dfrac{11}{12}\right) | |
\left(\dfrac{10}{12}\right) | |
\left(\dfrac{9}{12}\right) | |
\left(\dfrac{8}{12}\right) |
Question 2 Explanation:
Question 3 |
What is the chromatic number of the following graph?


2 | |
3 | |
4 | |
5 |
Question 3 Explanation:
Question 4 |
What is the size of the smallest MIS (Maximal Independent Set) of a chain of nine nodes
5 | |
4 | |
3 | |
2 |
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?
(0 + 1)^ * \ 11(0 + 1) ^* | |
0 ^* \ 110 ^* | |
0 ^* 10 ^* 10 ^* | |
(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^* |
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?
m \leq 2^n | |
n \leq m | |
M has one accept state | |
m = 2^n |
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
1 10000011 101000000000000000000000
The value of the number in decimal form is
-10 | |
-13 | |
-26 | |
None of the above |
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
f(A, B, C, D) = \sum(2, 3, 6, 7, 8, 9, 10, 11, 12, 13)
The function is
independent of one variable | |
independent of two variables | |
independent of three variable | |
dependent on all the variables |
Question 8 Explanation:
Question 9 |
What Boolean function does the circuit below realize?


xz + \bar{x}\bar{z} | |
x\bar{z} + \bar{x}{z} | |
\bar{x}\bar{y} + {y}{z} | |
xy + \bar{y}\bar{z} |
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. n^{1/3}
b. e^n
c. n^{7/4}
d. n \log^9n
e. 1.0000001^n
a, d, c, e, b | |
d, a, c, e, b | |
a, c, d, e, b | |
a, c, d, b, e |
Question 10 Explanation:
There are 10 questions to complete.