What is a Greedy algorithm?

A greedy algorithm is a problem-solving method that makes the locally optimal selection at every stage to reach a globally optimal solution. It solves a problem in two stages: Scanning the list of items and Optimization. However, in most problems, the greedy algorithm fails to provide a globally optimal solution.

The greedy algorithm has three variants: the pure greedy algorithm, the orthogonal greedy algorithm, and the relaxed greedy algorithm.

Why use the Greedy algorithm?

Some reasons to choose the greedy algorithm for solving a problem include:

1. Using the greedy approach, the solution can be found immediately.
2. With the greedy approach, the problem can be divided recursively depending on a condition, and the solutions need not be combined.
3. In the activity selection technique, the recursive division step can be derived by scanning a list of items a single time and considering some activities.

Components and Properties of the Greedy algorithm

A greedy algorithm consists of the following five components:

1. A candidate set: The set used to create a solution.
2. A selection function: This function selects the best candidate to add to the solution.
3. Feasibility function: This function determines whether a candidate should be used to contribute to the solution.
4. An objective function: This function assigns a value to a complete or partial solution.
5. A solution function: This function indicates whether a complete solution has been obtained or not.

Greedy algorithms provide good solutions for specific mathematical problems only. For the problems which it works, it will follow these properties:

• Greedy-choice property: Greedy choice property selects a path or option by considering the current values only. It does not take into account the future values or paths for a particular problem. It then solves the sub-problems later on. As a result, the greedy choice iteratively chooses one decision after another.
• Optimal substructure: For a problem, if the sub-problems have an optimal solution, the solution for the entire problem will be optimal. This property is known as an optimal substructure.

Benefits of the Greedy algorithm

The advantages of applying the greedy algorithm are as follows:

• It is easy to find a solution with the greedy strategy.
• Analyzing the run time for the greedy algorithm is easier when compared to other algorithms.

Drawbacks of the Greedy algorithm

The greedy algorithm has the following drawbacks:

• Proving the correctness of a solution is hard in the case of the greedy approach.
• Greedy algorithms do not work appropriately for problems where a solution is needed for every sub-problem.
• In the worst case, a greedy algorithm can lead to a non-optimal solution while solving problems.

Worst-case example: Finding the largest sum using the greedy algorithm

Here, the goal is to reach the largest sum. At every stage, the greedy algorithm will select the largest optimal solution. Beginning from 7 as the initial point, in the first step, the algorithm will select 12 instead of 3. This will take the algorithm far from the correct solution since it will not reach 99. That indicates that the greedy algorithm may not necessarily reach the global optimal solution by selecting the immediate local optimal solutions.

Examples of the Greedy algorithm

The greedy method works well with most problems. Some techniques that use the greedy algorithm are as follows:

Activity selection problem

Activity selection problem is a problem where there are n different activities. Each activity has a start and ending time. The goal is to select the maximum number of activities that a single person can solve. In this problem, the selection of activities is done such that they do not clash with each other. For a given problem, the algorithm sorts the activities as per the finishing time. Then at every step, the algorithm will select the activity whose finish time is the least from the activities remaining and start time is greater than the finish time of the previous activity. The time complexity of this problem for a sorted list will be O(n), and for a non-sorted list, will be O(n log n).

Dijkstra’s algorithm for adjacency list representation

For a graph G (V, E) with adjacency list representation, Dijkstra’s algorithm is applied to determine the shortest path between a source vertex and another vertex. This algorithm uses two lists, one to store vertices whose shortest path is already determined and another to hold the not yet considered vertices. The algorithm chooses the vertex having the minimum shortest path and adds it to the list.

Huffman Coding algorithm

Huffman coding is a lossless data compression algorithm. It assigns variable-length codes to input characters. The lengths of the codes are based on the frequencies of the characters. For instance, the most often used character is assigned the smallest code, and the less frequent characters get the largest code. The algorithm works in two parts, the first is to create a Huffman tree, and the second is to traverse the tree to search the codes.

Fractional Knapsack problem

For the knapsack problem, consider a list of items, each having a value and weight. The goal is to put the items in a knapsack such that the weight is less than or equal to W and the value is maximized. For a given problem, the knapsack approach selects the item having the highest weight. Knapsack problem can be 0-1 or fractional knapsack. In 0-1 knapsack, the items need to be put in as a whole unit, whereas they can be divided into smaller parts in fractional.

Kruskal’s minimum spanning algorithm

For a graph G (V, E) with weight or cost for each edge, Kruskal’s algorithm helps find the minimum spanning tree using the graph and the cost. The optimal solution may or may not be unique. The algorithm begins by sorting the edges in increasing order of weights and then selects the smallest edge that does not form a cycle. It continues the same process until all edges are visited.

Prim’s minimum spanning algorithm

With Prim’s algorithm, the minimum spanning tree for a graph G (V, E) is generated using graph G. This algorithm follows the growing tree approach. The goal behind this algorithm is simple. It only needs all the vertices in a spanning tree connected. At every step, the algorithm picks the least weighted connection from one vertex to another vertex in the tree.

Context and Applications

The greedy algorithm is an essential topic for all competitive exams and studies related to:

• Bachelors in Computer Applications
• Bachelors in Science (Information Technology)
• Masters in Computer Applications
• Masters in Science (Information Technology)

Practice Problems

1. From the given options, which one is not a greedy algorithm?

1. Dijkstra’s shortest path algorithm
2. Prim’s algorithm
3. Huffman encoding
4. Bellmen Ford shortest path algorithm

Answer: Option d

Explanation: Dijkstra’s shortest path algorithm, Prim’s algorithm, and Huffman encoding algorithm are all examples of greedy algorithms. The correct answer is the Bellmen Ford shortest path algorithm.

2. Which type of algorithm is Prim’s algorithm?

1. Dynamic programming
2. Greedy algorithm
3. Branch and bound
4. Recursion

Answer: Option b

Explanation: Prim’s algorithm follows the greedy approach to produce a minimum spanning tree.

3. Which of the following type of problems aim to select the maximum number of activities that a person or machine can complete?

1. Eight queen’s problem
2. Activity selection problem
3. Suboptimal backtracking
4. Combinatorial problem

Answer: Option b

Explanation: The activity selection problem uses the greedy algorithm to select the maximum number of activities that a person can complete from a given set of activities.

4. What type of trees are generated using Kruskal and Prim’s algorithms?

1. Compiler
2. Computation subtree
3. Minimum spanning tree
4. Initialized objective function

Answer: Option c

Explanation: Kruskal and Prim’s algorithms generate minimum spanning trees for a given graph using the greedy algorithm.

5. What will be the time complexity of the activity selection problem for the sorted list?

1. O(n)
2. O(n log n)
3. O(log n)
4. None of the above

Answer: Option a

Explanation: For a sorted list, the activity selection problem's time complexity will be O(n).

Common Mistakes

For specific problems, the use of a greedy algorithm may lead to incorrect solutions. Students should identify whether the greedy approach should be used for a problem or another technique would give the optimal solution in less time.

Related Concepts

• Job sequencing problem
• The traveling salesman problem
• Sorting and searching algorithms
• Divide and conquer algorithm
• Lists and arrays