Greedy Algorithms

Learn to solve optimization problems by making the best local choice at each step. Master the greedy approach and understand when it leads to globally optimal solutions.

Greedy Algorithm Principles

Greedy Choice Property

A globally optimal solution can be reached by making locally optimal choices

Example: In activity selection, choosing earliest finish time is always optimal

Optimal Substructure

An optimal solution contains optimal solutions to subproblems

Example: In MST, removing any edge gives optimal spanning tree for remaining vertices

No Backtracking

Once a choice is made, it is never reconsidered or undone

Example: Dijkstra never updates distance to visited vertices

Greedy vs Other Approaches

Greedy Algorithm

• Make locally optimal choice
• Never reconsider decisions
• Fast and simple
• Works for specific problems

Dynamic Programming

• Consider all subproblems
• Optimal substructure
• Slower but more general
• Guaranteed optimal solution

Brute Force

• Try all possibilities
• Guaranteed optimal
• Exponential time
• Impractical for large inputs

Classic Greedy Algorithms

Activity Selection Problem

Select maximum number of non-overlapping activities

Earliest Finish Time

Sort by finish time, select greedily

Proof Technique:

Exchange argument - greedy choice is always part of optimal solution

Fractional Knapsack

Maximize value by taking fractions of items within weight limit

Strategy:

Highest Value-to-Weight Ratio

Sort by value/weight ratio, take greedily

Proof Technique:

Cut-and-paste argument proves optimality

Huffman Coding

Optimal prefix-free binary encoding for data compression

Strategy:

Minimum Frequency First

Build tree bottom-up merging least frequent nodes

Proof Technique:

Optimal substructure and greedy choice property

Job Scheduling with Deadlines

Schedule jobs to maximize profit within deadlines

Highest Profit First

Sort by profit, schedule at latest possible time

Proof Technique:

Exchange argument with disjoint set optimization

Coin Change (Greedy)

Make change with minimum number of coins (for canonical systems)

Strategy:

Largest Denomination First

Always pick largest coin ≤ remaining amount

Proof Technique:

Works only for canonical coin systems (US, Euro)

Kruskal's MST Algorithm

Find minimum spanning tree using edge-based greedy approach

Strategy:

Minimum Weight Edge First

Sort edges, add if no cycle (union-find)

Proof Technique:

Cut property - minimum edge crossing any cut is in MST

Prim's MST Algorithm

Build minimum spanning tree by growing from starting vertex

Strategy:

Minimum Edge from Tree

Maintain tree, add minimum edge to new vertex

Proof Technique:

Cut property applied to tree vs non-tree vertices

Dijkstra's Shortest Path

Find shortest paths from source using greedy edge relaxation

Strategy:

Closest Unvisited Vertex

Maintain distances, always relax from closest vertex

Proof Technique:

Optimal substructure with non-negative weights

Gas Station Problem

Find starting gas station to complete circular tour

Reset at Deficit

Track surplus, reset start when deficit occurs

Proof Technique:

If solution exists, greedy choice finds it

How to Prove Greedy Optimality

Exchange Argument

Show that any optimal solution can be transformed to greedy solution without losing optimality

Common Steps:

1. Start with optimal solution
2. Exchange non-greedy choice with greedy one
3. Prove new solution is still optimal

Example:

Activity Selection: Exchange any activity with later finish time for earlier one

Cut-and-Paste

Remove part of optimal solution and replace with greedy choice

Common Steps:

1. Remove suboptimal part
2. Replace with greedy choice
3. Show improvement or equality

Example:

Fractional Knapsack: Replace any item with lower ratio with higher ratio item

Stays Ahead

Prove greedy algorithm always maintains better or equal state than any other algorithm

Common Steps:

1. Define invariant
2. Prove invariant maintained
3. Show invariant implies optimality

Example:

Dijkstra: Greedy distances are always ≤ actual shortest distances

Back to Divide & Conquer Explore Searching Algorithms