Question

A greedy algorithm is an approach for solving a problem by:

• A. Decision taken previously will be reversed on finding a best choice
• B. Best solution is chosen out of all resultant solutions
• C. The solutions of sub-problems are combined in order to achieve the best solution
• D. Selecting the best option available at the moment

Hint:

A greedy algorithm always makes the best possible decision at each step, leading to an optimal or near-optimal solution.
Examples:
- Dijkstra’s Algorithm (Shortest Path)
- Kruskal’s Algorithm (Minimum Spanning Tree)
- Huffman Encoding (Optimal Compression)

Answer 1

The Correct Option is D

Step 1: Understanding the Greedy Algorithm
- A greedy algorithm makes a locally optimal choice at each step with the hope of finding the global optimum.
- The decision is never reconsidered or reversed.
- Greedy algorithms work well when:
1. The problem has an optimal substructure.
2. A greedy choice property exists, meaning a local decision leads to a global optimum.
Step 2: Evaluating the Options
- (A) Incorrect: Greedy algorithms do not reverse previous decisions.
- (B) Incorrect: The greedy algorithm does not evaluate all solutions, but makes locally optimal choices.
- (C) Incorrect: Combining sub-problems to form a solution is dynamic programming (not greedy).
- (D) Correct: The greedy approach selects the best available option at each step, which fits the definition.