Greedy algorithms

Working of Greedy Algorithm

• Initialize: Start with an empty solution set.
• Selection: At each step, choose the best available option that provides the maximum immediate benefit.
• Feasibility Check: Ensure the chosen option doesn't violate constraints.
• Update: Modify the problem to exclude the chosen option and repeat until the solution is complete.

Example: Coin Change Problem

Given coins of different denominations, find the minimum number of coins required to make a given amount of money. Greedy choice: always choose the largest denomination that does not exceed the remaining amount.

Characteristics of Greedy Algorithm

• Greedy choice property: Optimal solution at each step.
• Optimal substructure: Optimal solution to the subproblems contributes to the global optimal solution.
• No backtracking or future consideration: Decisions are irreversible.
• Simplicity and speed: Easy to implement with quick execution.

Types of Greedy Algorithms

• Fractional Knapsack: Items can be taken in fractions.
• Dijkstra’s Algorithm: Finds the shortest path from a single source to all other vertices in a weighted graph.
• Kruskal’s Algorithm: Constructs a minimum spanning tree for a connected weighted graph.
• Prim’s Algorithm: Builds a minimum spanning tree by adding vertices one at a time.
• Huffman Coding: Builds an optimal prefix-free binary encoding for data compression.

Advantages and Limitations of the Greedy Algorithms 

Advantages

• Real-time systems: Quick solutions for real-time problems.
• Simpler problems: Efficient for problems with optimal substructure and greedy choice property.

Limitations

• NP-Hard problems: Fail to provide an optimal solution for complex problems like the Traveling Salesman Problem.
• Local optimization: Might miss the global optimum due to its greedy nature.

Greedy vs. Dynamic Programming

Code Example: Coin Change Problem (C++)

#include <iostream> #include <vector> using namespace std;

int coinChange(vector<int>& coins, int amount) {
    int numCoins = 0;
    for (int i = coins.size() - 1; i >= 0; i--) {
        while (amount >= coins[i]) {
            amount -= coins[i];
            numCoins++;
        }
    }
    return numCoins;
}

int main() {
    vector<int> coins = {1, 5, 10, 25}; // Example denominations
    int amount = 47; // Example amount to make change for
    cout << "Minimum coins required: " << coinChange(coins, amount) << endl;
    return 0;
}

You can also try this code with Online C++ Compiler

Run Code

This code snippet demonstrates the greedy approach to solving the coin change problem by choosing the largest denomination first.

Top 10 Greedy Algorithm MCQs with Answers & Explanations 

Q1. Which of the following Algorithms is not a Greedy Algorithm?

a.Prim's algorithm

b.Dijkstra's algorithm

c.Huffman Coding

d.Kruskal's algorithm

e.Bellman ford shortest path algorithm

Ans: e

Q2. Five files F1,F2,F3,F4,F5 have 120,80,50,100,300 records respectively. What should be the order to store them to optimize act? Assume each record is obtained with a similar recurrence.

a.F3,F2,F5,F1,F4

b.F2,F3,F4,F1,F5

c.F1,F2,F3,F5,F4

d.F2,F4,F1,F2,F3

Ans: b

This question is based on Optimal storage, which uses a greedy approach to find the optimal time to retrieve records. There are ‘n’ records of length ‘L’ to be stored in computer tape. Related to each record, the ‘i’ record is of length Li. So to retrieve these records optimally, we need to store them in increasing order of length Li.Therefore, the correct order is F2,F3,F4,F1,F5.

Q3. The time complexity of Huffman Coding is :

a.O(n^2)

b.O(nlogn)

c.O(n)

d.O(n(logn)^2)

Ans: b

O(nlogn) in which ‘n’ is the number of unique characters. For n nodes, extractMin() is called 2*(n-1) times.extractMin takes O(logn) time as it calls minHeapify(). Therefore, the overall time complexity is O(nlogn). Know more about Huffman coding.

Q4. A text is made up of characters a,b,c,d,e each occurring with the probability of 0.12, 0.40, 0.16 , 0.08, 0.24 respectively. What will be the average length of the optimal Huffman coding Technique?

a.2.16

b.2.26

c.2.20

d.2.15

Ans: a

a= 0.12 b =0.40 c=0.16 d=0.08 e=0.24

Huffman tree:

Length for each character= no. of bits * frequency of occurrence.

a = 4* 0.12

   = 0.48

b = 1 * 0.4

   = 0.4

c = 3 * 0.16

   = 0.48

d = 4 * 0.08

   = 0.32

e = 2 * 0.24

   = 0.48

Average length = 0.48 + 0.4 + 0.48 + 0.32 + 0.48 = 2.16

Q5. A letters a,b,c,d,e with probability ½,¼,⅛,1/16, 1/32 respectively. The normal length of the Huffman code is :

a.2.25

b.2.30

c.1.9375

d.2.18

Ans: c

Average length = (1* 1/2 + 2 * 1/4 + 3 * 1/8 + 4 * 1/16 + 5 * 1/32 )

 = 1.9375

Q6. Where does the data in a tree always occur in Huffman coding? 

a.Left subtree

b.Right subtree

c.Roots

d.leaves

Ans: d

Data is always stored at the tree's leaves to compute the codeword effectively in Huffman coding.

Q7. From the diagram given below, the computed codeword for c is:

a.110

b.101

c.011

d.111

Ans: a

By tracing the node's path from root to leaf assignment left branch 0 and right branch 1, the codeword for c is 110.

Q8. The runtime of the Huffman encoding algorithm is:

a.O( Clog C)

b.O(C)

c.O( log C)

d.O( N log C)

Ans: a

Q9. Consider a job scheduling problem with four jobs Q1,Q2,Q3,Q4 and with corresponding deadlines: (d1,d2,d3,d4) = (4,2,4,2) . Which of the following is not feasible without violating any job schedule?

a.Q2,Q4,Q1,Q3

b.Q4,Q1,Q2,Q3

c.Q4,Q2,Q1,Q3

d.Q4,Q2,Q3,Q1

Ans: b

In Option 2, the job is done randomly, not according to the deadline given; therefore, it is not a feasible schedule.

Q10. What is the codeword for ‘a’ in the following diagram?

a.100

b.111

c.010

d.011

Ans: d

By tracing the node's path from root to leaf, the codeword found for a is 011.

Conclusion

In this article, we have discussed some of the quality MCQs of the Greedy algorithm and also some of the previously asked questions in GATE.

Check out this problem - Frog Jump

If this article was helpful, share it as much as possible. You can visit Code360 and Greedy algorithm to learn more on such topics.