Greedy Algorithms

A greedy algorithm is a simple, intuitive algorithmic paradigm that follows the problem-solving heuristic of making the locally optimal choice at each stage with the hopes of finding the global optimum.

Characteristics

• Heuristic

• Local optimum

• Intuitive

• No long term planning

• Approximate, no guarantee to find the best solution

• Less time complexity than exact algorithms

Relationships with other paradigms

Greedy algorithms and backtracking are both decision-making paradigms in algorithm design, distinguished by their approach to finding solutions.

Greedy	Backtracking
Approximate	Exact
Make a decision	Make a decision
Never look back	Look back
No long term planning	Long term planning
Less time complexity	More time complexity
May fail to find the best solution	Always find the best solution by finding all solutions

Application Domain

Solve Optimization (find best) problems. Many combinatorial optimization problems can be solved by a greedy algorithm.

• Graph problems

  • Shortest path: Dijkstra’s algorithm

  • Minimum spanning tree: Prim’s algorithm, Kruskal’s algorithm

  • Graph coloring

• Bin packing problem

• Activity selection problem

• Fractional knapsack problem

• Huffman coding

Example Problems

• Greedy Solution to Bin Packing Problem
  • Bin Packing Problem
  • Algorithms to Solve Bin Packing Problem
  • Baseline Solution
  • Greedy Solution
• Greedy Solution to Huffman Coding Problem
  • Huffman Coding
  • Characteristics
  • Applications
  • Prefix Coding Tree
  • Example coding trees
  • Algorithm to build a Huffman coding tree
  • Steps to build the example tree