Greedy Algorithms
A Greedy Algorithm solves problems by making the locally optimal choice at each
step, hoping that these local choices lead to a globally optimal solution. It is often
used for optimization problems and works well when the problem exhibits the
greedy-choice property and optimal substructure.
Key Properties of Greedy Algorithms
1. Greedy-Choice Property:
o A global solution can be constructed by choosing the optimal local
solution at each step.
2. Optimal Substructure:
o The problem can be broken down into subproblems, and solutions to
subproblems can be used to construct the global solution.
Steps to Solve Using a Greedy Algorithm
1. Understand the problem and constraints.
2. Identify the greedy property.
3. Design a strategy to make the best choice at each step.
4. Prove that the greedy strategy leads to an optimal solution (if applicable).
5. Implement the algorithm.
Common Problems Solved by Greedy Algorithms
1. Activity Selection Problem
Problem: Given nnn activities with start and finish times, select the
maximum number of activities that don’t overlap.
Approach:
o Sort activities by their finishing times.
, o Select the activity that finishes earliest and doesn’t overlap with the
previously selected activities.
Time Complexity: O(nlogn)O(n \log n)O(nlogn) (for sorting).
Applications:
o Scheduling tasks.
o Resource allocation.
2. Huffman Coding
Problem: Build a prefix-free binary code tree with minimum cost for data
compression.
Approach:
o Use a priority queue to repeatedly combine the two nodes with the
smallest frequencies into a new node.
Time Complexity: O(nlogn)O(n \log n)O(nlogn).
Applications:
o Data compression (e.g., ZIP files, MP3, JPEG).
3. Fractional Knapsack Problem
Problem: Maximize the value of items that can be placed in a knapsack of
capacity WWW when fractions of items are allowed.
Approach:
o Sort items by their value-to-weight ratio.
o Take as much of the item with the highest ratio as possible.
Time Complexity: O(nlogn)O(n \log n)O(nlogn) (for sorting).
Applications:
o Resource allocation.
4. Minimum Spanning Tree (MST)
A Greedy Algorithm solves problems by making the locally optimal choice at each
step, hoping that these local choices lead to a globally optimal solution. It is often
used for optimization problems and works well when the problem exhibits the
greedy-choice property and optimal substructure.
Key Properties of Greedy Algorithms
1. Greedy-Choice Property:
o A global solution can be constructed by choosing the optimal local
solution at each step.
2. Optimal Substructure:
o The problem can be broken down into subproblems, and solutions to
subproblems can be used to construct the global solution.
Steps to Solve Using a Greedy Algorithm
1. Understand the problem and constraints.
2. Identify the greedy property.
3. Design a strategy to make the best choice at each step.
4. Prove that the greedy strategy leads to an optimal solution (if applicable).
5. Implement the algorithm.
Common Problems Solved by Greedy Algorithms
1. Activity Selection Problem
Problem: Given nnn activities with start and finish times, select the
maximum number of activities that don’t overlap.
Approach:
o Sort activities by their finishing times.
, o Select the activity that finishes earliest and doesn’t overlap with the
previously selected activities.
Time Complexity: O(nlogn)O(n \log n)O(nlogn) (for sorting).
Applications:
o Scheduling tasks.
o Resource allocation.
2. Huffman Coding
Problem: Build a prefix-free binary code tree with minimum cost for data
compression.
Approach:
o Use a priority queue to repeatedly combine the two nodes with the
smallest frequencies into a new node.
Time Complexity: O(nlogn)O(n \log n)O(nlogn).
Applications:
o Data compression (e.g., ZIP files, MP3, JPEG).
3. Fractional Knapsack Problem
Problem: Maximize the value of items that can be placed in a knapsack of
capacity WWW when fractions of items are allowed.
Approach:
o Sort items by their value-to-weight ratio.
o Take as much of the item with the highest ratio as possible.
Time Complexity: O(nlogn)O(n \log n)O(nlogn) (for sorting).
Applications:
o Resource allocation.
4. Minimum Spanning Tree (MST)
