Greedy Algorithms: Optimization Strategies

Master greedy algorithms for optimization problems. Learn when to apply them, their limitations, and real-world applications with implementation examples.

Greedy Algorithm Usage (2023)

Scheduling (30%)

Networking (25%)

Compression (20%)

Finance (15%)

Other (10%)

1. Greedy Algorithm Fundamentals

Core Principles:

Local Optimal Choices: Select best option at each step
No Backtracking: Decisions are final
Efficient: Often O(n log n) or O(n)
Not Always Optimal: Works only for specific problems

When to Use:

Property	Description
Greedy Choice Property	Local optimal leads to global optimal
Optimal Substructure	Problem can be broken into subproblems

Comparison with Other Paradigms:

Approach	Pros	Cons
Greedy	Fast, simple	Not always optimal
Dynamic Programming	Guaranteed optimal	Higher complexity
Brute Force	Finds all solutions	Extremely slow

2. Classic Greedy Problems

Activity Selection


function activitySelection(activities) {
  // Sort by finish time
  activities.sort((a, b) => a.finish - b.finish);
  
  const selected = [activities[0]];
  let lastFinish = activities[0].finish;
  
  for (let i = 1; i < activities.length; i++) {
    if (activities[i].start >= lastFinish) {
      selected.push(activities[i]);
      lastFinish = activities[i].finish;
    }
  }
  
  return selected;
}

Complexity: O(n log n)
Use Case: Scheduling rooms/events

Fractional Knapsack


function fractionalKnapsack(items, capacity) {
  // Sort by value/weight ratio
  items.sort((a, b) => (b.value / b.weight) - (a.value / a.weight));
  
  let totalValue = 0;
  
  for (const item of items) {
    if (capacity >= item.weight) {
      capacity -= item.weight;
      totalValue += item.value;
    } else {
      totalValue += item.value * (capacity / item.weight);
      break;
    }
  }
  
  return totalValue;
}

Complexity: O(n log n)
Use Case: Resource allocation

3. Advanced Applications

Huffman Coding


class HuffmanNode {
  constructor(char, freq, left = null, right = null) {
    this.char = char;
    this.freq = freq;
    this.left = left;
    this.right = right;
  }
}

function buildHuffmanTree(text) {
  const freqMap = {};
  for (const char of text) freqMap[char] = (freqMap[char] || 0) + 1;

  const nodes = Object.entries(freqMap)
    .map(([char, freq]) => new HuffmanNode(char, freq));

  while (nodes.length > 1) {
    nodes.sort((a, b) => a.freq - b.freq);
    const left = nodes.shift();
    const right = nodes.shift();
    nodes.push(new HuffmanNode(null, left.freq + right.freq, left, right));
  }

  return nodes[0];
}

Complexity: O(n log n)
Use Case: Data compression (ZIP, JPEG)

Dijkstra's Shortest Path


function dijkstra(graph, start) {
  const distances = {};
  const heap = new PriorityQueue();
  
  // Initialize
  for (const vertex in graph) {
    distances[vertex] = vertex === start ? 0 : Infinity;
    heap.enqueue(vertex, distances[vertex]);
  }

  while (!heap.isEmpty()) {
    const { element: u, priority: dist } = heap.dequeue();
    
    for (const { node: v, weight } of graph[u]) {
      const alt = dist + weight;
      if (alt < distances[v]) {
        distances[v] = alt;
        heap.enqueue(v, alt); // Greedy relaxation
      }
    }
  }
  
  return distances;
}

Complexity: O(E + V log V)
Use Case: Network routing

Greedy Algorithm Patterns

Pattern	Example Problems	Strategy
Selection	Activity Selection, Job Scheduling	Pick earliest finishing time
Fractional Choice	Fractional Knapsack	Take maximum value/weight ratio
Merge	Huffman Coding, Merge Intervals	Combine smallest pairs first
Edge Selection	Kruskal's MST, Dijkstra's	Choose locally optimal edges

4. Limitations & Alternatives

When Greedy Fails

Counterexamples:

0/1 Knapsack (needs DP)
Travelling Salesman (needs approximation)
Non-optimal substructure problems

Hybrid Approaches

Combine with:

Dynamic Programming (e.g., Prim's MST)
Backtracking (e.g., Branch and Bound)
Heuristics (e.g., Genetic Algorithms)

Greedy Algorithm Checklist

✓ Verify greedy choice property

✓ Check for optimal substructure

✓ Sort input if needed (O(n log n))

✓ Test edge cases where greedy fails

✓ Compare with DP solution if unsure

Pro Tip: To prove a greedy algorithm's correctness, use either the "greedy stays ahead" argument or an exchange argument. Always start with a brute force solution to identify if greedy choices lead to the global optimum.

0 Interaction

0 Views

0 Likes