Algorithms
Q81.
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?Q82.
Consider the depth-first-search of an undirected graph with 3 vertices P, Q, and R. Let discovery time d(u) represent the time instant when the vertex u is first visited, and finish time f(u) represent the time instant when the vertex u is last visited. Given that \begin{array}{l|l}\hline \text{$d(P) = 5$ units } & \text{ $f(P) = 12$ units } \\\hline \text{$d(Q) = 6$ units} & \text{ $f(Q) = 10$ units} \\\hline \text{$d(R) = 14$ unit} & \text{$f(R) = 18$ units} \\\hline \end{array} Which one of the following statements is TRUE about the graph?Q83.
Let T be a depth first search tree in a undirected graph G Vertices u and v are leaves of this tree T. The degrees of both u and v in G are at least 2. Which one of the following statements is true?Q84.
Consider the DAG with V = {1,2,3,4,5,6}, shown below. Which of the following is NOT a topological ordering?Q85.
Let G be an undirected graph. Consider a depth-first traversal of G, and let T be the resulting depth-first search tree. Let u be a vertex in G and let v be the first new (unvisited) vertex visited after visiting u in the traversal. Which of the following statement is always true?Q86.
Consider the following graph Among the following sequences (I) a b e g h f (II) a b f e h g (III) a b f h g e (IV) a f g h b e Which are depth first traversals of the above graph?Q87.
Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct ?Q88.
A depth-first search is performed on a directed acyclic graph. Let d[u] denote the time at which vertex u is visited for the first time and f[u] the time at which the DFS call to the vertex u terminates. Which of the following statements is always TRUE for all edges (u, v) in the graph ?Q89.
Let G be a graph with n vertices and m edges. What is the tightest upper bound on the running time of Depth First Search on G, when G is represented as an adjacency matrix?Q90.
Define R_n to be the maximum amount earned by cutting a rod of length n meters into one or more pieces of integer length and selling them. For i > 0, let p[i] denote the selling price of a rod whose length is i meters. Consider the array of prices: \text{p}[1]=1,\text{p}[2]=5,\text{p}[3]=8,\text{p}[4]=9,\text{p}[5]=10,\text{p}[6]=17,\text{p}[7]=18 which of the following statements is/are correct about R_7?[MSQ]