Greedy Algorithms

Greedy Algorithms – Full-Stack

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

Consider all available choices

Select the choice that seems best at this moment

Add this choice to solution set

Reduce problem size and repeat

Locally Optimal Decisions

The algorithm focuses on immediate gains rather than long-term consequences. It never reconsider its choices – what’s done is done.

General Greedy Algorithm Template

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.

Advantages Disadvantages ✓ Simple to design and implement ✗ May not find optimal solution ✓ Usually very efficient ✗ Hard to prove correctness ✓ Fast execution time ✗ Limited problem applicability ✓ Low memory requirements ✗ Greedy choices can’t be undone

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

Activity Selection

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;
}

Huffman Coding

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();
}

Fractional Knapsack

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;
}

Minimum Spanning Tree

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)]

Sort activities by finish time: [(1,4), (3,5), (0,6), (5,7), (3,8), (5,9), (6,10), (8,11)]

Select first activity: (1, 4)

Next activity with start ≥ 4: (5, 7)

Next activity with start ≥ 7: (8, 11)

Fractional Knapsack Example

Items: [(value: 60, weight: 10), (value: 100, weight: 20), (value: 120, weight: 30)]
Capacity: 50

Calculate ratios: [60/10=6, 100/20=5, 120/30=4]

Take all of item 1: Value=60, Remaining capacity=40

Take all of item 2: Value=160, Remaining capacity=20

Take 20/30 of item 3: Value=240, Remaining capacity=0

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.

Project Starter Code

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();