Algorithms
Q81.
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?Q82.
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)?Q83.
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?Q84.
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?Q85.
Consider the DAG with V = {1,2,3,4,5,6}, shown below. Which of the following is NOT a topological ordering?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.
Consider the string abbccddeee. Each letter in the string must be assigned a binary code satisfying the following properties: For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter. Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?