# GATE 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,

## What is the Weightage of Greedy in GATE Exam?

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 ____________.

##### Show Answer

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 ____.

##### Show Answer

The number of distinct minimum spanning trees for the weighted graph below is _____ ##### Show Answer

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?

##### Show Answer

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. ##### Show Answer

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?

##### Show Answer

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

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer

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.

##### Show Answer

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?

##### Show Answer

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?

##### Show Answer Dijkstra’s single source shortest path algorithm when run from vertex a in the above graph, computes the correct shortest path distance to

##### Show Answer

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

##### Show Answer

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?

##### Show Answer

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 ?

##### Show Answer

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.

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