# Algorithm

 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 ____.
 A 524 B 63218 C 5040 D 2540
GATE CSE 2023      Graph Traversal
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?
 A $f_1(n)\in \Theta (f_2(n))$ B $f_1(n)\in o (f_2(n))$ C $f_1(n)\in \omega (f_2(n))$ D $f_1(n)\in O (n)$
GATE CSE 2023      Asymptotic Notation
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?
 A $f \in O(g)$ B $f \in \Omega (g)$ C $f \in o(g)$ D $f \in \Theta (g)$
GATE CSE 2023      Asymptotic Notation
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 24 B 36 C 12 D 6
GATE CSE 2022      Minimum Spanning Tree
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
 A The edge with the second smallest weight is always part of any minimum spanning tree of G . B One or both of the edges with the third smallest and the fourth smallest weights are part of any minimum spanning tree of G . C 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 . D G can have multiple minimum spanning trees.
GATE CSE 2022      Minimum Spanning Tree
Question 5 Explanation:

There are 5 questions to complete.

### 2 thoughts on “Algorithm”

1. UPDATE THE QUES NO. 33
CORRECT ANS X=5;

• 