Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests - Download the BYJU'S Exam Prep App for free GATE/ESE preparation videos & tests -

Greedy Algorithm

The greedy approach is one of the techniques that follow the divide and conquer strategy. This technique is used for decoding optimisation problems.

Greedy Algorithm

Table of Contents

More About Greedy Algorithms

We can also say that a greedy algorithm is a method for decoding a problem by choosing the best alternative open at that point. This algorithm doesn’t worry whether the existing and most satisfactory result will obtain the overall optimal result. Also, the algorithm never changes the decision, no matter if the intention is wrong.

Pros of Greedy Algorithms

  • The concept of a greedy algorithm is clear and straightforward.
  • This algorithm performs better than others in terms of efficiency (but not in all cases).

Cons of Greedy Algorithms

The main drawback of greedy algorithms is that they frequently fail to provide the best answer or solution.

Applications of Greedy Algorithms

  • The shortest and fastest path is found using this approach.
  • Using Kruskal’s or Prim’s algorithms, we can determine the minimal spanning tree.
  • For resolving the fractional knapsack issue, it is quite helpful.

Pseudo Code of Greedy Algorithm

Algorithm Greedy (b, p)

{

Solution : = 0;

for y = 0 to n do

{

p: = select(b);

if feasible(solution, p)

{

Solution: = union(solution , p)

}

return solution;

} }

Example of Greedy Algorithm

For example, assume we desire to discover the longest path in the graph below from root to leaf. Let’s see how greedy algorithms apply here:

Greedy Algorithm 1

Greedy Approach

1. The root node (19) will be our starting point. The right child weighs 3, whereas the left child weighs 2.

2. We must identify the broadest route. And 3 is currently the best option. Thus, the greedy algorithm will select 3.

3. Now, the weight of an only child of 3 is 1. This gives us our final outcome 19 + 3 + 1 = 23.

It is not, however, the best option. As seen in the graphic below, there is another route that has greater weight (19 + 2 + 9 = 30).

Greedy Algorithm 2

Therefore, greedy algorithms don’t always produce the best or most practical outcome.

Practice Problems

Q1. 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 and their total value is maximised. 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 ____________.

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

Q3. The number of distinct minimum spanning trees for the weighted graph below is _____.

Greedy Algorithm 2

Q4. 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?

(A) T’ = T with total weight t’ = t2

(B) T’ = T with total weight t’ < t2

(C) T’ ≠ T but total weight t’ = t2

(D) None of the above

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

Greedy Algorithm 2

(A) SDT

(B) SBDT

(C) SACDT

(D) SACET

Q6. An undirected graph G(V,E) contains n (n > 2) nodes named v1,v2…..vn. Two nodes vi,vj are connected if and only if 0 <| ij | ≤ 2. Each edge (vi, vj) is assigned a weight i +j.

A sample graph with n = 4 is shown below.

Greedy Algorithm 2

What will be the cost of the minimum spanning tree (MST) of such a graph with n nodes?

(A) 112(11n2−5n)

(B) n2−n+1

(C) 6n−11

(D) 2n+1

Video on Greedy Algorithm

Frequently Asked Questions on Greedy Algorithm

Q1

What are the restrictions in greedy algorithms?

At times, it happens in greedy algorithms that fail to search for the globally optimal solution as they do not consider all the data.

Keep learning and stay tuned to get the latest updates on GATE Exam along with GATE Eligibility CriteriaGATE 2023GATE Admit CardGATE Syllabus for CSE (Computer Science Engineering)GATE CSE NotesGATE CSE Question Paper, and more.

Also Explore,