Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.
The number of distinct minimum spanning trees for the weighted graph below is _____
Let G be a weighted graph with edge weights greater than one and G' be the graph constructed by squaring the weights of edges in G. Let T and T' be the minimum spanning trees of G and G', respectively, with total weights t and t'. Which of the following statements is TRUE?
Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra’s shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.
An undirected graph G(V,E) contains n (n > 2) nodes named v_{1},v_{2}.....v_{n}.two node v_{i},v_{j} are connected if and only if 0 <| i - j | ≤ 2. Each edge (v_{i}, v_{j})is assigned a weight i +j. A sample graph with n = 4 is shown below.
What will be the cost of minimum spanning tree(MST) of such agraph with n node?
The length of the path from v_{5} to v_{6} in the MST of previous question with n=10 is
The weight of a sequence a_{0}, a_{1},…, a_{n-1} of real numbers is defined as a_{0} + a_{1} /2 +…+ a_{a-1}/2^{n-1}. A subsequence of a sequence is obtained by deleting some elements from the sequence. keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a_{0}, a_{1},…, a_{n-1 }and Y the maximum possibble weight of a subsequence of a_{0}, a_{1},…, a_{n-1}. Then X is equal to
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge { i , j}.
W=$\left[\begin{array}{ccccc}0& 1& 8& 1& 4\\ 1& 0& 12& 4& 9\\ 8& 12& 0& 7& 3\\ 1& 4& 7& 0& 2\\ 4& 9& 3& 2& 0\\ & & & & \end{array}\right]$
What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?
Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry W_{ij} in the matrix W below is the weight of the edge {i, j}.
What is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?
Which of the following statement (s) is / are correct regarding Bellman-Ford shortest path algorithm?
P. Always finds a negative weighted cycle, if one exists. Q. Finds whether any negative weighted cycle is reachable from the source.
Consider the following graph:
Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal’s algorithm?
G is a graph on n vertices and 2n-2 edges. The edges of G can be partitioned into two edge-disjoint spanning trees. Which of the following is NOT true for G?
Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to
In an unweighted, undirected connected graph, the shortest path from a node S to every other node is computed most efficiently, in terms of time complexity, by
Let w be the minimum weight among all edge weights in an undirected connected graph. Let e be a specific edge of weight. Which of the following is FALSE?
Suppose the letters a, b, c, d, e, f have probabilities $\frac{1}{2},\frac{1}{4},\frac{1}{8},\frac{1}{16},\frac{1}{32},\frac{1}{32}$, respectively.
Which of the following is the Huffman etter a, b, c, d, e, f ?
What is the average length of the correct answer to Q.76?