PPT: Greedy Techniques | Algorithms - Computer Science Engineering (CSE) PDF Download

 Page 1


Greedy 
Techniques
Page 2


Greedy 
Techniques
Introduction
Objective
Understand the greedy method and its application 
in algorithm design.
Definition
A problem-solving strategy that makes the locally 
optimal choice at each step to achieve a globally 
optimal solution.
Key Steps
Identify the greedy choice, make the choice and 
reduce the problem, repeat until solved.
Applications
Scheduling, shortest paths, minimum spanning 
trees, coding.
Page 3


Greedy 
Techniques
Introduction
Objective
Understand the greedy method and its application 
in algorithm design.
Definition
A problem-solving strategy that makes the locally 
optimal choice at each step to achieve a globally 
optimal solution.
Key Steps
Identify the greedy choice, make the choice and 
reduce the problem, repeat until solved.
Applications
Scheduling, shortest paths, minimum spanning 
trees, coding.
Greedy vs. Other Techniques
Greedy Method
Makes locally optimal choices that 
are fast and simple, but not always 
globally optimal. Examples include 
Fractional Knapsack (optimal) and 
Activity Selection.
Dynamic Programming
Considers all possibilities and 
guarantees global optimum, as 
seen in the 0/1 Knapsack problem. 
More comprehensive but 
potentially slower.
Divide and Conquer
Splits the problem and solves 
recursively, like in Merge Sort. 
Effective for problems that can be 
broken down into similar 
subproblems.
Use greedy algorithms when the problem has greedy choice property and optimal substructure. Always verify that 
the greedy choice leads to a global optimum before implementation.
Page 4


Greedy 
Techniques
Introduction
Objective
Understand the greedy method and its application 
in algorithm design.
Definition
A problem-solving strategy that makes the locally 
optimal choice at each step to achieve a globally 
optimal solution.
Key Steps
Identify the greedy choice, make the choice and 
reduce the problem, repeat until solved.
Applications
Scheduling, shortest paths, minimum spanning 
trees, coding.
Greedy vs. Other Techniques
Greedy Method
Makes locally optimal choices that 
are fast and simple, but not always 
globally optimal. Examples include 
Fractional Knapsack (optimal) and 
Activity Selection.
Dynamic Programming
Considers all possibilities and 
guarantees global optimum, as 
seen in the 0/1 Knapsack problem. 
More comprehensive but 
potentially slower.
Divide and Conquer
Splits the problem and solves 
recursively, like in Merge Sort. 
Effective for problems that can be 
broken down into similar 
subproblems.
Use greedy algorithms when the problem has greedy choice property and optimal substructure. Always verify that 
the greedy choice leads to a global optimum before implementation.
Activity Selection Problem
Sort Activities
Arrange all activities by their finish times in 
ascending order.
Select First Activity
Choose the activity with the earliest finish time and 
set last_finish to its finish time.
Select Next Compatible Activities
For each subsequent activity, if its start time g last_finish, select it and update last_finish.
For example, with activities [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)], after sorting by finish time, we select (1, 4), 
(5, 7), and (5, 9), resulting in 3 activities. The time complexity is O(n log n) due to sorting.
Page 5


Greedy 
Techniques
Introduction
Objective
Understand the greedy method and its application 
in algorithm design.
Definition
A problem-solving strategy that makes the locally 
optimal choice at each step to achieve a globally 
optimal solution.
Key Steps
Identify the greedy choice, make the choice and 
reduce the problem, repeat until solved.
Applications
Scheduling, shortest paths, minimum spanning 
trees, coding.
Greedy vs. Other Techniques
Greedy Method
Makes locally optimal choices that 
are fast and simple, but not always 
globally optimal. Examples include 
Fractional Knapsack (optimal) and 
Activity Selection.
Dynamic Programming
Considers all possibilities and 
guarantees global optimum, as 
seen in the 0/1 Knapsack problem. 
More comprehensive but 
potentially slower.
Divide and Conquer
Splits the problem and solves 
recursively, like in Merge Sort. 
Effective for problems that can be 
broken down into similar 
subproblems.
Use greedy algorithms when the problem has greedy choice property and optimal substructure. Always verify that 
the greedy choice leads to a global optimum before implementation.
Activity Selection Problem
Sort Activities
Arrange all activities by their finish times in 
ascending order.
Select First Activity
Choose the activity with the earliest finish time and 
set last_finish to its finish time.
Select Next Compatible Activities
For each subsequent activity, if its start time g last_finish, select it and update last_finish.
For example, with activities [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9)], after sorting by finish time, we select (1, 4), 
(5, 7), and (5, 9), resulting in 3 activities. The time complexity is O(n log n) due to sorting.
Fractional Knapsack Problem
Compute Value/Weight Ratio
Calculate the value-to-weight ratio for each available item.
Sort Items
Arrange items by decreasing value/weight ratio.
Fill Knapsack
Add items (or fractions) in order until capacity is reached.
For example, with items [(60, 10), (100, 20), (120, 30)] and capacity W = 50, we calculate ratios [6, 5, 4]. We add the 
entire first two items and 2/3 of the third, achieving a total value of 240. Unlike the 0/1 Knapsack problem, the 
fractional version allows for greedy optimality.