CSE 101 Class NotesGreedy AlgorithmsNovember 6, 2006OverviewGreedy algorithms always choose the intuitively “best” option at each decisionpoint, and (unlike backtracking) do not consider other alternatives. The prob-lem is that while this powerful intuition is powerful, it is often wrong – just asin life, acting in one’s immediate best interest is not always the best longer-termstrategy. Therefore it is especially important to prove that a greedy algorithmfinds the best solution. Luckily, these proofs typically follow a standard form,which we will discuss today.Example: Event schedulingInstance: a set of events E = {Ei= (si, fi)} where si< fi.Solution form: A subset S ⊂ E.Constraints: No two events in S intersect.Objective: Maximize the number of events, |S|.AlgorithmThe right heuristic is to always choose the event with the earliest end-time.Here is the backtracking version of Schedule using this choice heuristic:1 Schedule(E)2 e <- event minimizing finish(e)3 s1 <- Schedule(E - overlap(e)) + { e }4 s2 <- Schedule(E - e)5 if |s1| > |s2|6 return s17 else8 return s2The greedy version differs by never considering s2 on line 4, always returnings1.1CorrectnessWe need to prove that s1 is always at least as good as s2, i.e. |S1| ≤ |S2|.Consider an event eichosen by the greedy algorithm. Let S0be the bestschedule not containing ei, i.e. the best solution violating our greedy heuristic;and let S be the best schedule including ei, i.e. the best following the heuristicin considering ei. Our goal is to show that S is at least as good as S0.Theorem: The greedy schedule is always a largest legal schedule.Lemma: Let Eibe the event with minimal fi. Let S0be any legalschedule s.t. Ei/∈ S. Then there is a legal schedule S s.t. Ei∈ Sand |S| ≥ |S0|.Proof: Let C(Ei) be the set of elements that conflict with Ei. Anyeven Ej∈ C(Ei) must have si≤ fj≤ fi. Let S = S0−C(Ei)∪{Ei}.Then S, containing Ei, is a legal schedule, since S0has no conflicts,and S does not contain any events in C(Ei).We still need to show that |S| ≥ |S0|, i.e. that |C(Ei)| ≤ 1. Assumethat this is not the case, i.e. ∃Ej, Ekwith si≤ fj, fk≤ fi. ThenEj, Ekmust conflict, contradicting our assumption that S0is a legalschedule. Therefore |C(Ei)| ≤ 1, and |S| ≥ |S0|.Proof: (by strong induction on |S|, the number of events)Inductive hypothesis: for all n, if there exists a schedule S0with n events,then the transformation above can be used to generate a greedy schedule S with|S| ≥ |S0|.Base case: If |S| = 0, 1, the algorithm finds either 0 or 1 event.Inductive case: Assume the greedy algorithm is optimal for |S| < n, andlet Eibe the first remaining event to finish (i.e. the greedy choice). Let S0nbe the non-greedy optimal schedule making a non-greedy choice instead of Ei,and let S0n−1be its first n − 1 events. By our lemma, the schedule S00=S0n−1− C(Ei) ∪ {Ei} has |S00| ≥ |S0n| and Ei∈ S00. By our inductive hypothesis,|Sn−1| ≥ |S0n−1|. Also, since Sn−1is greedy, the last event in S0n−1finishes nosooner than the last event in Sn−1, so Sn−1∪ {Ei} is a legal solution.Therefore|Sn| = |Sn−1∪ {Ei}| = |Sn−1− C(Ei) ∪ {Ei}|≥ |S0n−1− C(Ei) ∪ {Ei}| = S00≥ |S0n|proving our inductive hypothesis.2Example(1,3),(2,4),(3,6),(0,6),(5,7),(5,8),(9,10)S2: + + +A: + - (-)B: + - (-)S1: + + +Here S2’s first move is non-greedy. The transformation in our proof replaces(2,4) with (1,3) (line A), then performs another greedy transformation (lineB), yielding an equal-sized schedule S1.ImplementationA naive implementation of the above approach, searching the entire list at eachstep for the next choice, then for overlapping events, would take O(n2). Anefficient implementation instead sorts the list by finish time, and skips overoverlapping events as it traverses this sorted list:1 Schedule2(E)2 E <- sort_by_finish(E)3 S <- E[1]4 f <- finish(E[1])5 for i = 2 .. n6 if start(E[i]) > f7 S <- S + E[i]8 f <- finish(E[i])General approachThe “modify-the-solution” approach used above can be applied to prove thecorrectness of many greedy algorithms. In general, we proceed by the followingsteps:1. Let d be the first decision point, and let g be the greedy choice at d.2. Let S0be a solution not choosing g.3. Show how to transform S0into some S that chooses g, and that is at leastas good as S0.4. Conclude by induction that any S0with a series of non-greedy decisions atd1. . . dncan be transformed into an equal-or-better greedy solution, andthat therefore the greedy algorithm is