Scribd
Upload
12 views

Greedy Algorithm_Lab Manual

Uploaded by

parvezscribd2829
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
12 views

Greedy Algorithm_Lab Manual

Uploaded by

parvezscribd2829
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
You are on page 1/ 3

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.

You might also like