What is a greedy algorithm and in what cases is it…

Greedy algorithm is an approach to solving optimization problems that, at each step, chooses the best local solution (the most advantageous option at the current moment) in the hope that this sequence of optimal local solutions will lead to a globally optimal solution. It does not consider the possible consequences of the current choice on future steps.

Characteristics:

Simplicity: Usually easier to implement than dynamic programming or other optimization methods.
Speed: Often has lower computational complexity.
Optimality guarantee: Does not always guarantee finding a globally optimal solution. The guarantee exists only for certain classes of problems.

It is used in problems where it is proven that a locally optimal choice at each step leads to a globally optimal solution. Examples:

Activity Selection Problem: Choosing the maximum number of non-overlapping activities by time.
Knapsack problem (with item divisibility): When items can be divided. If not, it is a dynamic programming problem.
Prim's and Kruskal's algorithms: For finding the minimum spanning tree in a graph.
Dijkstra's algorithm: For finding the shortest path in a graph with non-negative edge weights.
Huffman coding: For constructing an optimal prefix code.

Pseudo-code example for activity selection algorithm:

Function SelectActivities(activities):
  Sort activities by finish time
  selected_activities = empty list
  last_finish_time = 0

  For each activity in activities:
    If activity.start_time >= last_finish_time:
      Add activity to selected_activities
      last_finish_time = activity.finish_time

  Return selected_activities

It is important to verify whether the greedy algorithm is applicable to a specific problem, as otherwise it may produce a suboptimal solution.

# A simple example of a problem where the greedy algorithm is not optimal
# Change-making problem: give the smallest number of coins
# Available coins: [1, 5, 10, 25] USD
# Example: 30 cents

# Greedy algorithm:
#  Take the largest coin <= 30 (25) -> remainder 5
#  Take the largest coin <= 5 (5) -> remainder 0
#  Result: 2 coins (25 + 5). This is optimal here.

# Available coins: [1, 6, 10]
# Example: 12 cents

# Greedy algorithm:
#  Take the largest coin <= 12 (10) -> remainder 2
#  Take the largest coin <= 2 (1) -> remainder 1
#  Take the largest coin <= 1 (1) -> remainder 0
#  Result: 3 coins (10 + 1 + 1).
#  Optimal solution: 2 coins (6 + 6).

# This example shows that the greedy algorithm does not always lead to a global optimum,
# if the problem's properties do not match its applicability (for example,
# standard currency denominations often allow greedy algorithms,
# but arbitrary denominations do not).

What is a greedy algorithm and in what cases is it used?