ALG'25: L06 - Greedy | Idea & Examples

This lecture introduces the Greedy design paradigm (idea, steps, when to use, analysis...) together with two common examples (max sequence sum & fractional knapsack). It also introduces the D&C solution of the max sequence sum and compares it with the greedy one. 0:00 Goal & Agenda 1:45 Greedy Paradigm (idea, conditions, steps...) 14:08 Ex1: Max Sequence Sum (D&C) 31:13 Ex1: Max Sequence Sum (GREEDY) 44:57 Ex2: Fractional Knapsack (description) 58:43 Summary & Questions 60:23 Competition Results & Lessons