Greedy Algorithms: Design and Proof of Correctness

Hello! In our previous lesson, we delved into the "Divide and Conquer" paradigm, where problems are broken down, solved recursively, and their solutions are combined. We saw this strategy yield efficient algorithms like Karatsuba's for multiplication and an $O (n lo g n)$ solution for the Closest Pair of Points problem.

Today, we shift our focus to a different, often simpler, but equally powerful algorithmic design paradigm: Greedy Algorithms. Your learning outcome for this lesson is to design greedy algorithms for problems like activity selection and fractional knapsack, and provide a proof of correctness. Unlike Divide and Conquer, which often postpones decisions until subproblems are solved, the greedy approach makes a decisive, locally optimal choice at each step, hoping to build towards a globally optimal solution. We will explore when this bold strategy works and, just as importantly, how to prove that it does.

The Greedy Philosophy

At its heart, a greedy algorithm is one that builds up a solution piece by piece, always choosing the next piece that offers the most obvious and immediate benefit. It makes a "greedy" choice—the one that looks best at the current moment—without considering future consequences. The hope is that a series of locally optimal choices will lead to a globally optimal solution.

This approach is fundamentally about optimizing a problem, typically by maximizing a profit or minimizing a cost. To formalize this, a problem solvable by a greedy algorithm usually has:

A solution space: All possible solutions to the problem.
Feasible solutions: A subset of solutions that satisfy the problem's constraints.
An optimal solution: A feasible solution that maximizes or minimizes the objective function.

The following video from Gate Smashers provides a great introduction to these concepts in the context of the GATE exam.

L-4.1: Introduction to Greedy Techniques With Example | What is Greedy Techniques

This video, "Introduction to Greedy Techniques," explains the core idea of making locally optimal choices to find a global optimum.

Watch the initial definition here to grasp the main idea of a greedy choice. Next, focus on the explanation of solution space, feasible solutions, and optimal solutions. The real-life career choice analogy helps clarify how we narrow down options based on criteria. Finally, the segment from this timestamp summarizes the greedy principle and crucially points out that while the algorithm makes the best local choice, it doesn't always guarantee a global optimum. This is a key point to remember.

For a greedy algorithm to work correctly and produce an optimal solution, the problem must exhibit two key properties:

Greedy-Choice Property: A globally optimal solution can be achieved by making a sequence of locally optimal choices. The first choice made by the greedy algorithm must be part of some optimal solution. This allows us to "commit" to a choice without ever having to backtrack.
Optimal Substructure: An optimal solution to the problem contains within it optimal solutions to the resulting subproblems. After making a greedy choice, the remaining problem (minus the chosen element and any conflicting ones) is a smaller version of the original, and an optimal solution to the overall problem must include an optimal solution to this subproblem.

Now, let's see these principles in action with two classic problems.

Application 1: Activity Selection (Interval Scheduling)

This is a canonical problem for illustrating the greedy method.

Problem: You are given a set of n activities, each with a start time $s_{i}$ and a finish time $f_{i}$ . You need to select the maximum number of non-overlapping activities that can be performed by a single person.

Let's consider a few possible greedy strategies:

Select the shortest activity first? This seems intuitive, but a very short activity might conflict with two longer activities that you could have otherwise scheduled.
Select the activity that starts earliest? Again, this seems plausible. However, an activity that starts very early might run for a very long time, preventing many other activities from being scheduled.
Select the activity that finishes earliest? This is the key. By choosing the activity that finishes first, you free up the resource as soon as possible, maximizing the time available for other activities.

The Greedy Algorithm for Activity Selection

Sort the activities in ascending order of their finish times.
Select the first activity from the sorted list and add it to your solution set. Let its finish time be last_finish_time.
Iterate through the rest of the sorted activities. For each activity i, if its start time s_i is greater than or equal to last_finish_time, select activity i, add it to your solution set, and update last_finish_time to f_i.

Proof of Correctness: The Exchange Argument

This is where the "provide a proof of correctness" part of your learning outcome comes in. How do we know for sure that "earliest finish time" is the right greedy choice? We use a technique called an exchange argument.

The Back To Back SWE video provides one of the clearest explanations of this proof available. It walks through the algorithm and then meticulously proves its correctness.

Interval Scheduling Maximization (Proof w/ Exchange Argument)

The video "Interval Scheduling Maximization (Proof w/ Exchange Argument)" is an excellent, detailed walkthrough of both the algorithm and its formal proof.

First, understand the problem and the greedy strategy: sort by finish times. Watch the example walkthrough to see the algorithm in action. This will solidify your intuition before diving into the proof. Pay close attention to the setup for the proof. The goal is to show that the size of the greedy solution is equal to the size of the optimal solution. The exchange argument is introduced here. Finally, and most importantly, work through the exchange argument step-by-step. The core idea is to assume an optimal solution exists that differs from the greedy solution. You then show that you can swap the first differing element of the optimal solution with the greedy choice without making the solution worse. By repeating this process, you transform the optimal solution into the greedy solution, proving the greedy solution is itself optimal.

The essence of the exchange argument is this: you show that your greedy choice is "safe". By taking the activity with the earliest finish time, you are not closing off the possibility of an optimal solution. Any optimal solution can be transformed, step-by-step, into the greedy solution without losing its optimality.

Application 2: Fractional Knapsack Problem

Let's look at another problem where a greedy strategy shines.

Problem: You have a knapsack with a maximum weight capacity W. You are given n items, each with a value $v_{i}$ and a weight $w_{i}$ . You can take fractions of items. Your goal is to fill the knapsack to maximize the total value of the items inside.

This is different from the 0/1 Knapsack Problem, where you must either take an entire item or leave it. The 0/1 version is a classic dynamic programming problem. The ability to take fractions is what makes a greedy approach viable here.

What's the best greedy choice?

Highest value item first? A very valuable item might be so heavy that it fills the entire knapsack, leaving no room for other items that, combined, could offer more value.
Lightest item first? You might fill the knapsack with many light but low-value items.
Item with the highest value-to-weight ratio ( $v_{i} / w_{i}$ ) first? This is the winner. This metric represents the "value density" of each item. It makes sense to prioritize items that give you the most value per unit of weight.

The Greedy Algorithm for Fractional Knapsack

For each item, calculate its value-to-weight ratio, $r_{i} = v_{i} / w_{i}$ .
Sort the items in descending order based on their ratios.
Initialize current_weight = 0 and total_value = 0.
Iterate through the sorted items:
- If the current item's weight w_i can be fully added to the knapsack (i.e., current_weight + w_i <= W), take the whole item. Update current_weight += w_i and total_value += v_i.
- Otherwise, take a fraction of the item that fills the remaining capacity. The fraction is (W - current_weight) / w_i. Update total_value by adding fraction * v_i and set current_weight = W. Break the loop.

Proof of Correctness (Intuitive Exchange Argument)

The proof is similar in spirit to the activity selection problem.

Assume the greedy solution G is not optimal, and there is an optimal solution O with a higher value.
Since G and O are different, there must be a first item i (in the sorted list of ratios) that the greedy algorithm takes more of than the optimal solution.
The greedy algorithm would have filled the knapsack with as much of item i (the highest-ratio item available) as possible. For O to be different, it must have taken less of i and instead taken more of some other item j that has a lower ratio ( $r_{j} < r_{i}$ ).
Now, perform an exchange. In solution O, replace a small amount of item j with an equal weight of item i. Since $r_{i} > r_{j}$ , replacing a lower-density item with a higher-density item will increase the total value of O.
This contradicts our initial assumption that O was the optimal solution. Therefore, no such O can exist, and the greedy solution G must be optimal.

Conclusion

In this lesson, we introduced the Greedy paradigm, a powerful tool for optimization problems. We contrasted it with Divide and Conquer, noting its focus on making immediate, locally optimal choices.

Key Takeaways:

Greedy algorithms make the choice that seems best at the moment to construct a solution step-by-step.
For a greedy strategy to be optimal, the problem must exhibit the Greedy-Choice Property and Optimal Substructure.
The Activity Selection Problem is solved greedily by sorting activities by their finish times.
The Fractional Knapsack Problem is solved greedily by sorting items by their value-to-weight ratio.
Correctness proofs for greedy algorithms often rely on an exchange argument, where you show that any supposed optimal solution can be transformed into the greedy solution without loss of optimality.

Greedy algorithms are fast and often simple to implement, but they don't work for all problems. How do you solve problems like the 0/1 Knapsack problem where making a greedy choice can lead to a suboptimal outcome? For that, we need a more exhaustive approach. In our next lesson, we will explore Dynamic Programming, a technique that systematically evaluates all choices and combinations to guarantee a globally optimal solution, even when a greedy approach fails.

Recommended resources