Greedy Algorithms
Open in the Padhaiko app4.1 Basic concepts
A greedy algorithm builds a solution step by step, always making the choice that looks best at the current moment (a locally optimal choice) without reconsidering previous choices, hoping this sequence leads to a globally optimal solution.
Two Essential Properties for Greedy Optimality
For a greedy algorithm to guarantee a globally optimal solution, the problem must exhibit two properties:
- Greedy-Choice Property: A globally optimal solution can be arrived at by making a locally optimal (greedy) choice first, without solving all subproblems beforehand.
- Optimal Substructure: An optimal solution to the whole problem contains within it optimal solutions to its remaining subproblems.
| Aspect | Greedy Method | Dynamic Programming |
|---|---|---|
| Decision Strategy | Makes one irreversible locally optimal choice at each step | Evaluates all choices across overlapping subproblems |
| Direction | Top-down (commit choice, reduce to one smaller subproblem) | Typically bottom-up (or memoized top-down) |
| Subproblem Dependency | Choice does not depend on subproblem solutions | Choice depends directly on solutions to subproblems |
| Speed vs. Generality | Faster ( typical) when valid, but works on fewer problems | Broader applicability, usually or |
4.2 Fractional knapsack problem
Given items where item has weight and value/profit , and a knapsack of capacity , select fractions to:
Greedy Strategy: Compute the value-to-weight ratio for each item and sort items in non-increasing order of . Take as much of the highest-ratio item as fits; if the remaining capacity , take fraction and stop.
// Items must be pre-sorted in decreasing order of profit[i] / weight[i]
double fractionalKnapsack(int n, double weight[], double profit[], double W) {
double totalProfit = 0.0, rem = W;
for (int i = 0; i < n && rem > 0; i++) {
if (weight[i] <= rem) {
totalProfit += profit[i];
rem -= weight[i];
} else {
totalProfit += profit[i] * (rem / weight[i]);
rem = 0;
}
}
return totalProfit;
}- Time Complexity: Sorting takes and the greedy scan takes , giving total time (and extra space if sorted in-place).
- Note: Greedy by is optimal for Fractional Knapsack, but fails for 0/1 Knapsack (where items cannot be split).
4.3 Job sequencing with deadlines
Given unit-time jobs, where job has a deadline and profit (earned only if completed by time , with at most one job scheduled per unit time slot ), find a feasible subset of jobs maximizing total profit.
Greedy Strategy:
- Sort all jobs in non-increasing order of profit .
- Maintain an array of time slots
slot[1 .. d_max](initially empty). - For each job in sorted order, scan backward from down to and assign job to the latest free slot (leaving earlier slots open for tighter-deadline jobs).
int jobSequencing(int n, int deadline[], int profit[], int maxD) {
// Assumes jobs are sorted in decreasing order of profit[]
int slot[maxD + 1];
for (int t = 0; t <= maxD; t++) slot[t] = -1;
int totalProfit = 0;
for (int i = 0; i < n; i++) {
int limit = (deadline[i] < maxD) ? deadline[i] : maxD;
for (int t = limit; t >= 1; t--) {
if (slot[t] == -1) {
slot[t] = i;
totalProfit += profit[i];
break;
}
}
}
return totalProfit;
}- Time Complexity: Sorting takes and slot searching takes in the naive implementation (reducible to using Disjoint-Set Union with path compression).
1
- Solve the Fractional Knapsack instance with and items .
- Find the optimal schedule and maximum profit for Job Sequencing with Deadlines given jobs:
- , , , , .
Fractional Knapsack (): Compute profit-to-weight ratios :
- Item 1:
- Item 2:
- Item 3:
Already sorted in decreasing ratio order ():
- Take all of Item 1 (, profit , remaining ).
- Take all of Item 2 (, profit , remaining ).
- Take fraction of Item 3 (profit , remaining ).
Total maximum profit .
Job Sequencing with Deadlines (): Sort jobs by profit descending: , , , , . Initialize 3 unit slots :
- : assign to latest free slot Slot 2 (
[_, J1, _]). - : Slot 2 taken, assign to Slot 1 (
[J3, J1, _]). - : Slot 1 taken rejected.
- : Slot 1 taken rejected.
- : assign to Slot 3 (
[J3, J1, J5]).
Optimal sequence is with total profit .
- Fractional Knapsack optimal vector gives total profit .
- Optimal job schedule is in slots with total profit .
4.4 Analysis of minimum spanning trees related algorithms
A Minimum Spanning Tree (MST) of a connected, undirected, weighted graph is an acyclic subset connecting all vertices (so ) with minimum total edge weight .
Cut Property (Safe-Edge Theorem)
Let be any partition (cut) of the vertices of such that no edge in a partial MST crosses the cut. If is a light edge crossing (minimum weight among all edges with one endpoint in and one in ), then is safe to add to (it belongs to some MST extending ).
Kruskal's Algorithm
Kruskal's algorithm grows a forest of trees by processing edges globally in increasing weight order:
- Sort all edges in non-decreasing order of weight .
- Initialize disjoint singleton sets (
MAKE-SET(v)). - For each edge in sorted order: if
FIND-SET(u) != FIND-SET(v), add to and executeUNION(u, v)(otherwise skip to avoid a cycle).
- Time Complexity: Sorting edges takes ; Union-Find operations (with union by rank and path compression) take , where is the inverse Ackermann function. Since , , giving total time.
Prim's Algorithm
Prim's algorithm grows a single tree starting from an arbitrary root :
- Initialize
key[v] = infinityfor all ,key[r] = 0, and insert all vertices into a min-priority queue . - While is non-empty, extract .
- For each neighbor of still in : if , set and
DECREASE-KEY(v, w(u, v)).
| Aspect | Kruskal's Algorithm | Prim's Algorithm |
|---|---|---|
| Growth Pattern | Grows a forest of trees merged globally | Grows a single tree from start vertex |
| Core Data Structure | Edge sorting + Disjoint-Set Union (Union-Find) | Min-Priority Queue (Binary Heap / Array / Fibonacci Heap) |
| Time Complexity | array; binary heap; Fibonacci heap | |
| Best Graph Density | Sparse graphs () | Dense graphs (, with array/Fib heap) |
2
Find the Minimum Spanning Tree (MST) and its total weight for the -vertex undirected graph with vertices and weighted edges:
using Kruskal's algorithm, and verify the same MST weight via Prim's algorithm starting at .
Kruskal's algorithm (edges sorted by weight): Sorted edges: , , , , , , , , .
- Add weight — components: .
- Add weight — merges .
- Add weight — merges .
- Add weight — merges .
- Skip weight — and already in (would form cycle ).
- Add weight — merges with into one spanning tree ( edges). Remaining cross edges and are heavier, so is optimal. Total MST weight .
Prim's algorithm starting from :
- Start: . Lightest edge out of : .
- Out of : , , , pick .
- Out of : , , pick .
- Out of : , pick .
- Out of : (vs ) pick .
Edges selected: , identical to Kruskal's with total weight .
Both Kruskal's and Prim's algorithms select the MST edges with total minimum weight .
4.5 Analysis of single source shortest path algorithm
Given a weighted directed (or undirected) graph with edge weights and a source vertex , Dijkstra's algorithm finds the shortest-path weight from to every vertex .
Dijkstra's Greedy Relaxation Principle
Dijkstra's algorithm maintains a set of vertices whose final shortest-path weights from are already determined, and a min-priority queue keyed by current distance estimates (, for ). At each step:
- Extract with minimum and add to .
- Relax each outgoing edge :
void dijkstra(int V, int graph[V][V], int src, int dist[]) {
int visited[V];
for (int i = 0; i < V; i++) { dist[i] = 1000000000; visited[i] = 0; }
dist[src] = 0;
for (int count = 0; count < V; count++) {
int u = -1;
for (int v = 0; v < V; v++)
if (!visited[v] && (u == -1 || dist[v] < dist[u])) u = v;
if (u == -1 || dist[u] == 1000000000) break;
visited[u] = 1;
for (int v = 0; v < V; v++) {
if (graph[u][v] > 0 && dist[u] + graph[u][v] < dist[v])
dist[v] = dist[u] + graph[u][v];
}
}
}Complexity & Negative-Weight Limitation:
- Simple Array / Matrix: ( linear scans for min + relaxations).
- Binary Min-Heap + Adjacency List:
EXTRACT-MINcalls at each plusDECREASE-KEYcalls at each (or for connected graphs). - Fibonacci Heap: (since
DECREASE-KEYis amortized). - Why Non-Negative Weights Are Required: Dijkstra's greedy step assumes adding edges cannot decrease path length. With negative edge weights, a later path through an unvisited vertex could yield a smaller distance to an already-finalized vertex , breaking correctness (use Bellman-Ford in when negative weights exist).
3
Run Dijkstra's algorithm from source vertex on the directed weighted graph with vertices and directed edges:
Show the distance table after each vertex extraction.
Initialization and iterations: Initially , .
| Extracted | Relaxations Performed | |||||
|---|---|---|---|---|---|---|
| Init | — | |||||
| () | , | |||||
| () | , | |||||
| () | , | |||||
| () | ||||||
| () | No outgoing edges |
Shortest path distances from : (e.g., shortest path has total weight ).
Exercises
Exercises — Greedy Algorithms
Explain the Greedy-Choice Property and Optimal Substructure. Using the items , , with capacity , prove why sorting greedily by fails when items cannot be split (0/1 Knapsack).
Greedy properties:
- Greedy-Choice Property: A locally optimal choice at the current step can always be extended to a globally optimal solution, without reconsidering earlier decisions.
- Optimal Substructure: After making the greedy choice, the optimal solution to the whole problem combines that choice with an optimal solution to the resulting subproblem.
Counterexample on 0/1 Knapsack (): The profit-to-weight ratios are , , :
- Greedy by picks Item 1 (), then Item 2 (), using capacity ; Item 3 () no longer fits (), yielding profit .
- Optimal 0/1 solution skips Item 1 and takes (total weight ), yielding profit .
Greedy fails on 0/1 Knapsack because choosing Item 1 () leaves capacity, forcing profit , whereas skipping Item 1 and choosing achieves the optimal .
Find the optimal solution for the Fractional Knapsack instance with capacity and items:
- Item 1:
- Item 2:
- Item 3:
- Item 4:
Computing ratios and sorting descending:
- Item 1:
- Item 2:
- Item 3:
- Item 4:
Sorted order: Item 1 (), Item 2 (), Item 3 (), Item 4 ().
Greedy selection up to :
- Take Item 1 completely: , profit , remaining .
- Take Item 2 completely: , profit , remaining .
- Take of Item 3: profit , remaining .
Total profit .
Take for a maximum profit of .
Using the greedy Job Sequencing with Deadlines algorithm, find the optimal schedule and total profit for unit-time jobs with profits and deadlines .
Sorting jobs in decreasing profit order: , , , , . Maximum deadline , so slots are .
Assigning each job to the latest free slot :
- : assign to Slot 3 .
- : assign to Slot 1 .
- : assign to Slot 2 .
- and cannot fit (all slots are full).
Total profit .
Optimal schedule: in slots with maximum profit .
Find the Minimum Spanning Tree weight using Kruskal's algorithm on the -vertex undirected graph with edges:
State the asymptotic time complexities of Kruskal's algorithm and binary-heap Prim's algorithm.
Kruskal's algorithm trace (sorted edges): Sorted weights: , , , , , , , , , .
- Add
- Add
- Add
- Add
- Skip (cycle ).
- Add ( edges chosen; stop).
Total MST weight .
Asymptotic complexities:
- Kruskal's algorithm: (dominated by sorting edges; Union-Find takes ).
- Prim's algorithm (binary heap): for connected graphs (or with an unsorted array).
MST edges: with total weight . Both Kruskal's and binary-heap Prim's algorithms run in time.
- Trace Dijkstra's algorithm from vertex on the -vertex directed graph with edges:
- Give a concrete -vertex example showing why Dijkstra's algorithm fails when an edge has a negative weight.
Dijkstra trace from vertex :
- Start: .
- Extract (): , .
- Extract (): , .
- Extract (): , .
- Extract (): (along path ).
- Extract (): done.
Negative-weight counterexample ( vertices ): Let edges be , , and . Dijkstra extracts , sets and , then extracts first (since ) and permanently finalizes . Later when is extracted, path has length , so Dijkstra misses the true shortest path to .
- Final shortest distances from vertex : .
- With , , , Dijkstra prematurely locks before discovering of length .