Related Questions8 Items
Q1.MCQ
Let $G(V, E)$ be an undirected and unweighted graph with $100$ vertices. Let $d(u, v)$ denote the number of edges in a shortest path between vertices $u$ and $v$ in $V$. Let the maximum value of $d(u, v)$, $u, v \in V$ such that $u \neq v$, be $30$. Let $T$ be any breadth-first-search tree of $G$. Which ONE of the given options is CORRECT for every such graph $G$?
Q2.MCQ
Let $G$ be any undirected graph with positive edge weights, and $T$ be a minimum spanning tree of $G$. For any two vertices, $u$ and $v$, let $d1(u, v)$ and $d2(u, v)$ be the shortest distances between $u$ and $v$ in $G$ and $T$, respectively. Which ONE of the options is CORRECT for all possible $G$, $T$, $u$ and $v$?
Q3.MCQ
Consider the following recurrence relation:
$T(n) = 2T(n - 1) + n2^n$ for $n > 0$, $\quad T(0) = 1$.
Which ONE of the following options is CORRECT?
Q4.NUMERICAL
In a double hashing scheme, $h1(k) = k \pmod{11}$ and $h2(k) = 1 + (k \pmod 7)$ are the auxiliary hash functions. The size $m$ of the hash table is $11$. The hash function for the $i$-th probe in the open address table is $h1(k) + i \cdot h2(k) \pmod m$. The following keys are inserted in the given order: $63, 50, 25, 79, 67, 24$.
The slot at which key $24$ gets stored is \\\\\\\. (Answer in integer)
Q5.NUMERICAL
The maximum value of $x$ such that the edge between the nodes B and C is included in every minimum spanning tree of the given graph is \\\\\\\. (answer in integer)
!image(https://uadmin.udsfgecw.tech/file/download/public/public:f8962db5-bc12-4d27-874a-88843a320f23.png)
Q6.MCQ
Consider the following recurrence relation:
$$T(n) = \begin{cases} \sqrt{n}T(\sqrt{n}) + n & \text{for } n \geq 1, \\ 1 & \text{for } n = 1. \end{cases}$$
Which one of the following options is CORRECT?
Q7.M-MCQ
Let $G$ be a directed graph and $T$ a depth first search (DFS) spanning tree in $G$ that is rooted at a vertex $v$. Suppose $T$ is also a breadth first search (BFS) tree in $G$, rooted at $v$. Which of the following statements is/are TRUE for every such graph $G$ and tree $T$ ?
Q8.NUMERICAL
The number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with $100$ vertices is $40$. The number of connected components in $G$ is
Computer Science And EngineeringAlgorithmsNumerical Answer (NAT)2 Marks
Q4.
In a double hashing scheme, h1(k)=k(mod11) and h2(k)=1+(k(mod7)) are the auxiliary hash functions. The size m of the hash table is 11. The hash function for the i-th probe in the open address table is [h1(k)+i⋅h2(k)](modm). The following keys are inserted in the given order: 63,50,25,79,67,24. The slot at which key 24 gets stored is _______. (Answer in integer)
A
10