The greedy approach is one of the techniques that follow the divide and conquer strategy. This technique is used for decoding optimisation problems.
Table of Contents
- More About Greedy Algorithms
- Pros of Greedy Algorithms
- Cons of Greedy Algorithms
- Applications of Greedy Algorithms
- Pseudo Code of Greedy Algorithm
- Example of Greedy Algorithm
- Greedy Approach
- Practice Problems
- Video on Greedy Algorithm
- FAQ Related to Greedy Algorithm
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 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).
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 _____.
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.
(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 <| 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 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
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 Criteria, GATE 2023, GATE Admit Card, GATE Syllabus for CSE (Computer Science Engineering), GATE CSE Notes, GATE CSE Question Paper, and more.
Also Explore,
