Question 1 |
Let U = \{1, 2, 3\}. Let 2^U denote the powerset of U. Consider an undirected graph
G whose vertex set is 2^U. For any A,B \in 2^U, (A,B) is an edge in G if and only
if (i) A \neq B, and (ii) either A \subseteq B or B \subseteq A. For any vertex A in G, the set of
all possible orderings in which the vertices of G can be visited in a Breadth First
Search (BFS) starting from A is denoted by B(A).
If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.
If \phi denotes the empty set, then the cardinality of B(\phi ) is ____.
524 | |
63218 | |
5040 | |
2540 |
Question 1 Explanation:
Question 2 |
Consider functions Function 1 and Function 2 expressed in pseudocode as
follows:

Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively.
Which of the following statements is/are TRUE?

Let f_1(n) and f_2(n) denote the number of times the statement "x = x + 1" is executed in Function 1 and Function 2, respectively.
Which of the following statements is/are TRUE?
f_1(n)\in \Theta (f_2(n)) | |
f_1(n)\in o (f_2(n)) | |
f_1(n)\in \omega (f_2(n)) | |
f_1(n)\in O (n) |
Question 2 Explanation:
Question 3 |
Let f and g be functions of natural numbers given by f(n)=n and g(n)=n^2.
Which of the following statements is/are TRUE?
Which of the following statements is/are TRUE?
f \in O(g) | |
f \in \Omega (g) | |
f \in o(g) | |
f \in \Theta (g) |
Question 3 Explanation:
Question 4 |
Let G(V, E) be a directed graph, where V = \{1, 2, 3, 4, 5 \} is the set of vertices and
E is the set of directed edges, as defined by the following adjacency matrix A.
A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.
A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____
A[i][j]= \left \{ \begin{matrix} 1 &1 \leq j \leq i \leq 5 \\ 0& otherwise \end{matrix} \right.
A[i][j]=1 indicates a directed edge from node i to node j . A directed spanning tree of G , rooted at r \in V , is defined as a subgraph T of G such that the undirected version of T is a tree, and T contains a directed path from r to every other vertex in V . The number of such directed spanning trees rooted at vertex 5 is ____
24 | |
36 | |
12 | |
6 |
Question 4 Explanation:
Question 5 |
Consider a simple undirected weighted graph G, all of whose edge weights are distinct. Which of the following statements about the minimum spanning trees of G is/are TRUE?
MSQ
MSQ
The edge with the second smallest weight is always part of any minimum spanning tree of G . | |
One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . | |
Suppose S\subseteq V be such that S\neq \phi and S\neq V . Consider the edge with the minimum weight such that one of its vertices is in S and the other in V \ S . Such an edge will always be part of any minimum spanning tree of G . | |
G can have multiple minimum spanning trees. |
Question 5 Explanation:
There are 5 questions to complete.
UPDATE THE QUES NO. 33
CORRECT ANS X=5;
Dear MO Rashid,
In question they have not asked for value of x. Value of x is 5. but they have asked for number of possible MST using x=5 which is 4.