Scribd
Upload
6 views8 pages

Algorithm 06 2025

Chapter 6 discusses greedy algorithms, which make locally optimal choices at each step for optimization problems. The Activity Selection Problem is presented, where the goal is to select the maximum number of non-overlapping activities based on their start and finish times. The greedy approach involves sorting activities by finish time and selecting the earliest finishing activity that starts after the last selected activity.

Uploaded by

Noah Nathenael
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
6 views8 pages

Algorithm 06 2025

Chapter 6 discusses greedy algorithms, which make locally optimal choices at each step for optimization problems. The Activity Selection Problem is presented, where the goal is to select the maximum number of non-overlapping activities based on their start and finish times. The greedy approach involves sorting activities by finish time and selecting the earliest finishing activity that starts after the last selected activity.

Uploaded by

Noah Nathenael
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Chapter 6- Greedy Algorithms

Prepared By: Beimnet G


Greedy Algorithms

Algorithms for optimization problems typically go through a sequence of


steps, with a set of choices at each step.
A greedy algorithm always makes the choice that looks best at the
moment.
That is, it makes a locally optimal choice.
Activity Selection Problem

Problem Statement:
You are given n activities with their start and finish times. Select the
maximum number of activities that can be performed by a single person,
assuming that a person can only work on a single activity at a time.
Activity Selection Problem

a0 a1 a2 a3 a4 a5 a6 a7

si 0 2 1 3 4 6 5 ∞

fi 0 3 4 5 6 8 9 ∞

Si,j - the set of activities which starts after ai finishes and finishes before

aj starts.

Ai,j - the set of compatible activities in Si,j (the solution set)


4
Activity Selection Problem

If we know an activity ak in in the optimal solution, we know that the final


solution will contain all compatible activities in Si,k and Sk,j and ak.

What is ak?

A[i,j]- the max number of activities in the optimal solution.

{ 0,
A[i,j]= max 1+ A[i,k]+ A[k,j], Si,j ≠ Ø
i<k<j

Si,j = Ø
5
Activity Selection Problem: Greedy Approach

Making the Greedy Choice:

What if we could choose an activity to add to our solution without


having to solve all the subproblems?

Intuition: If we pick an activity that finishes early it will free up the


resource for more activities that follow it.

6
Activity Selection Problem: Greedy Approach
The greedy choice is to always pick the next activity whose finish time is
least among the remaining activities and the start time is more than or
equal to the finish time of the previously selected activity. We can sort the
activities according to their finishing time so that we always consider the
next activity as minimum finishing time activity.

1) Sort the activities according to their finishing time


2) Select the first activity from the sorted array and print it.
3) Do the following for the remaining activities in the sorted array.
7
Greedy Approach: Problems

1. Fractional knapsack problem


2. Egyptian fractions
3. Minimum spanning tree

You might also like