# Questions & Answers of Greedy

## What is Greedy ?

Greedy algorithms determine minimum number of coins to give while making change. These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using only coins with values {1, 5, 10, 20}. The coin of the highest value,

## Weightage of Greedy

Total 18 Questions have been asked from Greedy topic of Algorithms subject in previous GATE papers. Average marks 1.94.

Consider the weights and values of items listed below. Note that there is only one unit of each item.
 Item number Weight (in Kgs) Value (in Rupees) 1 10 60 2 7 28 3 4 20 4 2 24

The task is to pick a subset of these items such that their total weight is no more than 11 Kg sand their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by Vopt. A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by Vgreedy.

The value of Vopt Vgreedy is ____________.

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=$\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 Wij 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 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 ?

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.