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.