Proving Correctness of Greedy Algorithms
COMP3121/9101 21T3 November 27, 2021
This document presents two approaches to prove the correctness of the greedy algorithm presented in lecture 6 for the Activity Selection Problem. These two proofs are written in full detail, using notation to be as precise as possible. Assignment submissions can use worded arguments instead, as long as they are logically sound, clear and convincing.
Problem
Suppose you have a list of n activities, the ith starting at time si and finishing at time fi. A set of activities is said to be compatible if no two of them overlap. Find a compatible set of activities which is of maximum size.
Algorithm
Sort the activities in increasing order of finishing time. Then traverse the sorted list, maintaining the finishing time of the most recently selected activ- ity. An activity i is selected if and only if it does not overlap with the most recently selected activity j, i.e. its starting time si is later than the finishing time fj.
Proofs of Correctness
Both proofs will begin by relabelling the activities in order of increasing endpoints, so that f1 ≤ f2 ≤ … ≤ fn.
1
Proof 1: Exchange Argument
Suppose our greedy algorithm takes a set of activities
A = {a1,a2,…,ak} where a1 < a2 < ... < ak.
Assume for a contradiction that the maximum size of a compatible set is l > k, and therefore let
B = {b1,b2,…,bl} where b1 < b2 < ... < bl be a compatible set.
Suppose the jth smallest entries of sets A and B are the first place in which they differ, i.e. a1 = b1, a2 = b2, ..., aj−1 = bj−1 and aj ̸= bj.
Consider B′ = B ∪ {aj} \ {bj}. We claim that B′ is also a compatible set of size l.
First, we find the size of B′. B′ is formed by removing an element from B and replacing it with aj. To ensure that |B′| = |B| we only need to confirm that aj ∈/ B. If aj were to be an element of B, then it must appear after bj. But then the greedy strategy would have picked bj as its jth choice before getting to aj, giving a contradiction.
Now we prove that B′ is compatible. We know there are no conflicts in B, so any conflicts in B′ would have to be between an existing element bi and the new element aj.
Case1: i
Activities bj and bi do not conflict (since they are both part of the
compatible set B) so bj must finish before bi starts, i.e. fbj < sbi . However, the greedy algorithm chose activity aj instead of bj, so aj
must finish no later than bj . Then faj ≤ fbj .
Therefore faj < sbi and hence activities aj and bi do not conflict. Therefore B′ is a compatible set of size l. We can now compare A to B′, in
which at least the j smallest entries agree. 2
Continuing in this way, we can resolve any differences between the greedy selection and an optimal solution, until all k choices made by the greedy selection A also appear as the first k choices of the optimal solution B. Since |B| = l > k, there is still at least one activity j = bk+1 ∈ B unaccounted for. However, we have one final contradiction; this activity does not conflict with anything in A, so our greedy algorithm would have selected it. Therefore the maximum size of a compatible set is indeed k, i.e. the greedy algorithm is optimal.
Proof 2: Greedy Stays Ahead
Let m(k) be the maximum size of a compatible subset of activities {1, 2, . . . , k}. We will prove by induction that our greedy algorithm achieves m(k) for all k = 1..n.
Clearly m(1) = 1, and the greedy algorithm selects the earliest finishing activity, so the required statement is true for k = 1.
Suppose the greedy algorithm achieves m(1),m(2),…,m(k). We will now prove that it also achieves m(k + 1).
First, we show that m(k + 1) equals either m(k) or m(k) + 1. Clearly, m(k+1) ≥ m(k). It is also true that m(k+1) ≤ m(k)+1, as a selection from the first k + 1 activities can take at most m(k) of the first k and potentially one more (activity k + 1).
In the first case, the correctness is self-evident; our greedy algorithm picked m(k) of the first k activities, so the same selection takes the most possible activities out of the first k+1. Hereafter we assume that m(k+1) = m(k)+1.
Case 1: the greedy algorithm takes activity k + 1
By the assumption, the greedy algorithm took m(k) of the first k activities, so if it also takes activity k + 1, we now have m(k) + 1 = m(k + 1) of the first k + 1 activities, as required. So in this case, the greedy algorithm successfully achieves m(k + 1).
Case 2: the greedy algorithm does not take activity k + 1
In this case, the greedy algorithm would only take m(k) of the first k + 1 activities, rather than m(k + 1) = m(k) + 1, so it would not be optimal. Therefore our task is to prove that this case never arises.
Suppose that from the first k activities, the greedy algorithm takes a
3
set
A = {a1,a2,…,am(k)} where a1 < a2 < ... < am(k),
and let the last chosen activity be j (= am(k)). We assume in this case that activity k + 1 was not chosen, so it must overlap with the last chosen activity j, i.e. fj ≥ sk+1.
Assume for a contradiction that there is a compatible set of m(k + 1) = m(k) + 1 of the first k + 1 activities. From the proof that m(k + 1) ≤ m(k) + 1, we know that such a set must include activity k + 1. Therefore let
B = {b1,b2,...,bm(k),bm(k)+1} where b1 < b2 < ... < bm(k) < bm(k)+1 be such a set, and let the last activity bm(k)+1 be k + 1 and the
penultimate activity bm(k) be i.
Since set B is compatible, we know that activities bm(k) and bm(k)+1 do not conflict, i.e. fi < sk+1. We therefore have that fi < fj, so i