This note is part of my learning notes on Data Structures & Algorithms.

Greedy Algorithms

A greedy algorithm is an algorithmic approach that builds up a solution piece by piece. It makes a locally optimal choice in the hope that this choice will lead to a globally optimal solution (hoping the next choice will be best for all further choices). Greedy algorithms are used to solve optimization problems, where the goal is to find the best solution from all feasible solutions.

Key Characteristics

  • Greedy Choice Property: A global optimum can be arrived at by selecting a local optimum.
  • Optimal Substructure: An optimal solution to the problem contains an optimal solution to subproblems.

Prove the Correctness of a Greedy Algorithm Using Mathematical Induction

Steps

  1. Base Case: Show that the algorithm works for the smallest instance of the problem (usually when there is only one choice or a trivial solution).
  2. Inductive Hypothesis: Assume that the algorithm works optimally for all instances of size nn or less.
  3. Inductive Step: Show that if the algorithm works for instances of size nn, it also works for instances of size n+1n+1.

Example: Activity Selection Problem

Given a set of activities $S= {a_1, a_2, …, a_n }, each with a start time sis_i and a finish time fif_i, select the maximum number of non-overlapping activities.

Activities aia_i and aja_j are compatible if the intervals [si,fi)[s_i,f_i) and [sj,fj)[s_j,f_j) do not overlap.

(): open intervals, do not include the number
[]: closed intervals, include the number

Assume the activities are sorted by their finish times fif_i:

f1≤f2≤...≤fn−1≤f(n)f_1 \leq f_2 \leq ... \leq f_{n-1} \leq f(n)

Greedy Choice

Always select the activity that finishes first and then recursively select from the remaining activities that start after the current activity finishes.

Proof of Correctness Using Mathematical Induction

  1. Base case
    • If there is only one activity, the algorithm trivially selects it, which is obviously optimal. A1={(s1,f1)}A_1 = \{(s_1,f_1)\}
    • If there are no activities, the solution is also trivially optimal (selecting zero activities).
  2. Inductive hypothesis
    • Assume that for a set of nn activities, the greedy algorithm produces an optimal solution.
  3. Inductive step
    • For a set of n+1n+1 activities A={(s1,f1),(s2,f2),...,(sn+1,fn+1)}A = \{(s_1,f_1), (s_2,f_2),...,(s_{n+1},f_{n+1})\}
    • Select the activity a1(s1,f1)a_1 (s_1,f_1) with the earliest finish time
    • Remove all activities that overlap with a1a_1, resulting in a reduced problem with a set of A′A' of non-overlapping activities.