Lab Manual
Greedy Algorithms
1. Activity Selection Problem
Input: A set of activities S = {a1,…, an}
Each activity has start time and a finish time
ai=(si, fi)
Two activities are compatible if and only if their time does not overlap
Output: a maximum-size subset of mutually compatible activities
• {a3, a9, a11} can be completed
• But so can {a1, a4, a8’ a11} which is a larger set
• But it is not unique, consider {a2, a4, a9’ a11}
Pseudocode
2. Knapsack Problem
• There are n different items in a store
• Item i :
o weighs wi pounds
o worth $vi
• A thief breaks in
• Can carry up to W pounds in his knapsack
• What should he take to maximize the value?
0-1 Knapsack Problem:
• The items cannot be divided
• Thief must take entire item or leave it behind
• Greedy strategy does not work for the 0-1 knapsack problem
Fractional Knapsack Problem:
• Thief can take partial items
• For instance, items are liquids or powders
• Solvable with a greedy algorithm
Pseudocode
3. Counting Money
Suppose you want to count out a certain amount of money, using the fewest possible bills and
coins
Greedy algorithm to do this would be:
At each step, take the largest possible bill or coin that does not overshoot
Example: To make $6.39, you can choose:
• a $5 bill
• a $1 bill, to make $6
• 25¢ coin, to make $6.25
• A 10¢ coin, to make $6.35
• four 1¢ coins, to make $6.39
For US money, the greedy algorithm always gives the optimum solution
Implement this money counting problem using Bangladeshi monetary system.
4. Connect n ropes with minimum cost
There are given n ropes of different lengths, we need to connect these ropes into one rope. The
cost to connect two ropes is equal to sum of their lengths.
We need to connect the ropes with minimum cost.
