Questions & Answers of Greedy

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 v1,v2.....vn.two node vi,vj are connected if and only if 0 <| i - j | ≤ 2. Each edge (vi, vj)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?

An undirected graph G(V,E) contains n (n > 2) nodes named v1,v2.....vn.two node vi,vj are connected if and only if 0 <| i - j | ≤ 2. Each edge (vi, vj)is assigned a weight i +j.
A sample graph with n = 4 is shown below.

The length of the path from v5 to v6 in the MST of previous question with n=10 is

The weight of a sequence a0, a1,…, an-1 of real numbers is defined as a0 + a1 /2 +…+ aa-1/2n-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 a0, a1,…, an-1 and Y the maximum possibble weight of a subsequence of a0, a1,…, an-1. Then X is equal to

Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.

W=018141012498120731470249320

 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 Wij in the matrix W below is the weight of the edge {i, j}.

W=018141012498120731470249320

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 12,14,18,116,132,132, respectively.

Which of the following is the Huffman etter a, b, c, d, e, f ?

Suppose the letters a, b, c, d, e, f have probabilities 12,14,18,116,132,132, respectively.

What is the average length of the correct answer to Q.76?