Question 1 |

Let G be a simple, finite, undirected graph with vertex set \{v_1,...,v_n\}. Let \Delta (G)
denote the maximum degree of G and let N=\{1,2,...\} denote the set of all possible
colors. Color the vertices of G using the following greedy strategy:
for i = 1,...,n

color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}

Which of the following statements is/are TRUE?

color(v_i)\leftarrow min\{ j \in N: \text{ no neighbour of } v_i \text{ is colored } j\}

Which of the following statements is/are TRUE?

This procedure results in a proper vertex coloring of G. | |

The number of colors used is at most \Delta (G)+1. | |

The number of colors used is at most \Delta (G). | |

The number of colors used is equal to the chromatic number of G. |

Question 1 Explanation:

Question 2 |

Consider a random experiment where two fair coins are tossed. Let A be the event
that denotes HEAD on both the throws, B be the event that denotes HEAD on
the first throw, and C be the event that denotes HEAD on the second throw.
Which of the following statements is/are TRUE?

A and B are independent. | |

A and C are independent. | |

B and C are independent. | |

Prob(B|C) = Prob(B) |

Question 2 Explanation:

Question 3 |

Let X be a set and 2^X denote the powerset of X.

Define a binary operation \Delta on 2^X as follows:

A \Delta B=(A-B) \cup (B-A)

Let H=(2^X,\Delta ) . Which of the following statements about H is/are correct?

Define a binary operation \Delta on 2^X as follows:

A \Delta B=(A-B) \cup (B-A)

Let H=(2^X,\Delta ) . Which of the following statements about H is/are correct?

H is a group. | |

Every element in H has an inverse, but H is NOT a group. | |

For every A \in 2^X, the inverse of A is the complement of A. | |

For every A \in 2^X, the inverse of A is A. |

Question 3 Explanation:

Question 4 |

Let f:A\rightarrow B be an onto (or surjective) function, where A and B are nonempty
sets. Define an equivalence relation \sim on the set A as

a_1\sim a_2 \text{ if } f(a_1)=f(a_2),

where a_1, a_2 \in A . Let \varepsilon =\{[x]:x \in A\} be the set of all the equivalence classes under \sim . Define a new mapping F: \varepsilon \rightarrow B as

F([x]) = f(x), for all the equivalence classes [x] in \varepsilon

Which of the following statements is/are TRUE?

a_1\sim a_2 \text{ if } f(a_1)=f(a_2),

where a_1, a_2 \in A . Let \varepsilon =\{[x]:x \in A\} be the set of all the equivalence classes under \sim . Define a new mapping F: \varepsilon \rightarrow B as

F([x]) = f(x), for all the equivalence classes [x] in \varepsilon

Which of the following statements is/are TRUE?

F is NOT well-defined. | |

F is an onto (or surjective) function. | |

F is a one-to-one (or injective) function. | |

F is a bijective function. |

Question 4 Explanation:

Question 5 |

Let U = {1, 2,...,n}, where n is a large positive integer greater than 1000. Let
k be a positive integer less than n. Let A, B be subsets of U with |A| = |B| = k
and A\cap B=\phi . We say that a permutation of U separates A from B if one of the
following is true.

- All members of A appear in the permutation before any of the members of B.

- All members of B appear in the permutation before any of the members of A.

How many permutations of U separate A from B?

- All members of A appear in the permutation before any of the members of B.

- All members of B appear in the permutation before any of the members of A.

How many permutations of U separate A from B?

n! | |

\binom{n}{2k} (n-2k)! | |

\binom{n}{2k} (n-2k)! (k!)^2 | |

2 \binom{n}{2k} (n-2k)! (k!)^2 |

Question 5 Explanation:

There are 5 questions to complete.