Greedy Algorithms
Master algorithmic problem-solving with the greedy approach – making locally optimal choices to achieve global efficiency.
1. Greedy Approach Concepts
Makes the Best Choice at Each Step
Greedy algorithms make the most optimal choice available at each decision point, without considering the bigger picture. Each decision is made with the hope that local optima will lead to a global optimum.
Greedy Decision Process
Locally Optimal Decisions
The algorithm focuses on immediate gains rather than long-term consequences. It never reconsider its choices – what’s done is done.
function greedyAlgorithm(problem) {
// Initialize solution
let solution = [];
while (!problem.isSolved()) {
// Make locally optimal choice
let bestChoice = findBestChoice(problem);
// Add choice to solution
solution.push(bestChoice);
// Reduce problem size
problem = reduceProblem(problem, bestChoice);
}
return solution;
}
Does Not Always Guarantee Globally Optimal Solution
The main limitation of greedy algorithms is that they don’t work for all problems. Sometimes, the sequence of locally optimal choices doesn’t lead to a globally optimal solution.
Simple and Efficient
- Easy to conceptualize and implement
- Typically runs in polynomial time
- Low space complexity
- Well-suited for optimization problems
- Often provides good approximations
2. Popular Problems
Select maximum number of non-overlapping activities from a set of activities with start and end times.
function activitySelection(activities) {
// Sort by finish time
activities.sort((a, b) => a.end - b.end);
let selected = [activities[0]];
let lastEnd = activities[0].end;
for (let i = 1; i < activities.length; i++) {
if (activities[i].start >= lastEnd) {
selected.push(activities[i]);
lastEnd = activities[i].end;
}
}
return selected;
}
Data compression technique that assigns variable-length codes to characters based on frequency.
class HuffmanNode {
constructor(char, freq) {
this.char = char;
this.freq = freq;
this.left = null;
this.right = null;
}
}
function buildHuffmanTree(frequencies) {
// Create priority queue
const queue = new PriorityQueue();
// Build tree by merging nodes
while (queue.size() > 1) {
const left = queue.dequeue();
const right = queue.dequeue();
const merged = new HuffmanNode(
null,
left.freq + right.freq
);
merged.left = left;
merged.right = right;
queue.enqueue(merged);
}
return queue.dequeue();
}
Maximize total value in knapsack by taking fractions of items, sorted by value-to-weight ratio.
function fractionalKnapsack(items, capacity) {
// Sort by value/weight ratio
items.sort((a, b) =>
(b.value / b.weight) - (a.value / a.weight)
);
let totalValue = 0;
let remaining = capacity;
for (let item of items) {
if (remaining >= item.weight) {
totalValue += item.value;
remaining -= item.weight;
} else {
totalValue += (remaining / item.weight) * item.value;
break;
}
}
return totalValue;
}
Find minimum weight subset of edges that connects all vertices in a graph.
// Prim's Algorithm
function primMST(graph) {
const visited = new Set();
const mst = [];
const priorityQueue = new PriorityQueue();
visited.add(0);
graph[0].forEach(edge =>
priorityQueue.enqueue(edge)
);
while (visited.size < graph.length) {
const edge = priorityQueue.dequeue();
if (!visited.has(edge.to)) {
mst.push(edge);
visited.add(edge.to);
// Add new edges to queue
}
}
return mst;
}
Activity Selection Example
Given activities with start and end times: [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11)]
Fractional Knapsack Example
Items: [(value: 60, weight: 10), (value: 100, weight: 20), (value: 120, weight: 30)]
Capacity: 50
Algorithm Comparison
| Problem | Time Complexity | Space Complexity | Greedy Choice | Optimality |
|---|---|---|---|---|
| Activity Selection | O(n log n) | O(1) | Select activity with earliest finish time | Always optimal |
| Huffman Coding | O(n log n) | O(n) | Merge nodes with smallest frequencies | Always optimal |
| Fractional Knapsack | O(n log n) | O(1) | Take item with highest value/weight ratio | Always optimal |
| Prim's MST | O(E log V) | O(V) | Add edge with smallest weight | Always optimal |
| Kruskal's MST | O(E log V) | O(V) | Add smallest safe edge | Always optimal |
Project: Greedy Algorithm Visualizer
Build an interactive visualization tool that demonstrates greedy algorithms in action.
class GreedyVisualizer {
constructor() {
this.problems = {
activity: [], // Activity selection
knapsack: [], // Fractional knapsack
huffman: {}, // Huffman coding frequencies
mst: [] // Graph for MST
};
this.solution = [];
this.currentStep = 0;
}
// Activity Selection Methods
generateActivities(count) {
this.problems.activity = [];
for (let i = 0; i < count; i++) {
const start = Math.floor(Math.random() * 20);
const end = start + Math.floor(Math.random() * 10) + 1;
this.problems.activity.push({start, end, id: i});
}
}
solveActivitySelection() {
// Sort by end time
const sorted = [...this.problems.activity]
.sort((a, b) => a.end - b.end);
this.solution = [sorted[0]];
let lastEnd = sorted[0].end;
for (let i = 1; i < sorted.length; i++) {
if (sorted[i].start >= lastEnd) {
this.solution.push(sorted[i]);
lastEnd = sorted[i].end;
}
}
return this.solution;
}
// Visualization methods
visualizeStep(step) {
// Visualize current step of algorithm
// Update UI to show current state
}
}
// Usage
const visualizer = new GreedyVisualizer();
visualizer.generateActivities(8);
const solution = visualizer.solveActivitySelection();