Unit 4

Greedy Algorithms
A greedy algorithm always makes the choice that looks best at the moment.
It makes a locally optimal choice in the hope that this choice leads to a globally optimal solution.
Greedy algorithms do not always yield optimal solutions.
Minimum-spanning-tree algorithms furnish a classic example of the greedy method
Q. Explain the general method for designing greedy algorithms. Describe the three major steps
involved and explain why each step is necessary for proving correctness.
Solution:
We can design greedy algorithms according to the following sequence of steps:
1. Cast the optimization problem as one in which you make a choice and are left with one
subproblem to solve.
2. Prove that there is always an optimal solution to the original problem that makes the greedy
choice, so that the greedy choice is always safe.
3. Demonstrate optimal substructure by showing that, having made the greedy choice, what remains
is a subproblem with the property that if you combine an optimal solution to the subproblem with
the greedy choice you have made, you arrive at an optimal solution to the original problem

Q. what is a greedy choice property?

Solution:
At every step, you can make a locally optimal choice (the best choice available at that moment),
and this choice will always be part of a globally optimal solution.
In simpler words:
A problem has the greedy choice property if choosing the best option right now always leads to an
overall best solution.
Example:
• In Activity Selection, choosing the activity that finishes earliest is always part of the optimal
schedule.
• In Huffman Coding, picking the two smallest-frequency nodes first is always correct.

Q what is an Optimal substructure property.

Solution:
A problem has optimal substructure if an optimal solution to the problem contains optimal
solutions to its subproblems.
In simple words:
Solving the small parts of the problem optimally helps build the optimal solution to the whole
problem.
Example:
• Shortest path:
If the shortest path from A → C goes through B, then
the path from A → B and B → C must each be shortest paths.
Q. Differentiate between Greedy and Dynamic programming?
Solution:

Greedy Algorithm Dynamic Programming (DP)

Makes the best local choice at each step. Considers all subproblems and builds an
optimal solution.
Decisions are final; no backtracking. Decisions may be revised using stored results.
 Requires greedy-choice property and optimal Requires only optimal substructure.
substructure.
Usually faster (O(n) or O(n log n)). Usually slower (O(n²) or more).
Uses very little memory. Uses more memory (tables, memoization).
Works for fractional knapsack, activity Works for 0/1 knapsack, LCS, matrix chain
selection, MST, Huffman coding. multiplication, coin change.
Finds optimum only for problems where local Always finds the global optimum.
optimum = global optimum.
Simple to implement. Complex to implement.

Q. A thief breaks into a warehouse and can carry a maximum weight of 50 units.
He finds the following items:
Item Weight Value
1 10 60
2 20 100
3 30 120
Using the fractional knapsack algorithm, determine the maximum profit the thief can obtain.
Show all steps including value/weight ratios, sorting, and fractions taken.
Solution:
Given: capacity 𝑊 = 50. Items:
Item Weight 𝑤𝑖 Value 𝑣𝑖
1 10 60
2 20 100
3 30 120
Step 1 — Compute value/weight ratios
𝑣𝑖
ratio𝑖 =
𝑤𝑖

• Item 1: 60/10 = 6.0

• Item 2: 100/20 = 5.0
• Item 3: 120/30 = 4.0
Step 2 — Sort items by ratio (descending)
Order: Item 1 (6.0), Item 2 (5.0), Item 3 (4.0).
Step 3 — Fill the knapsack greedily
Start with remaining capacity = 50, total value = 0.
1. Take Item 1 completely (weight 10, value 60).
Remaining capacity = 50 − 10 = 40. Total value = 60.
2. Take Item 2 completely (weight 20, value 100).
Remaining capacity = 40 − 20 = 20. Total value = 60 + 100 = 160.
2
3. Item 3 has weight 30 but remaining capacity is 20, so take fraction 20/30 = 3of Item 3.
2
Value taken = 3 × 120 = 80.
Remaining capacity = 0. Total value = 160 + 80 = 240.
2
Maximum profit = 240, achieved by taking Item 1, Item 2, and 3of Item 3.

Q. A truck can carry 25 kg. It has the following goods:

Item Weight (kg) Profit
A 5 30
B 10 40
C 15 45
Solve the problem using the greedy fractional knapsack approach and compute the maximum
[Link] your working.
Solution:
Given: capacity 𝑊 = 25kg.
Items:
Item Weight (kg) 𝑤𝑖 Profit 𝑣𝑖
A 5 30
B 10 40
C 15 45
Step 1 — Compute value/weight ratios
𝑣𝑖
ratio𝑖 =
𝑤𝑖

• A: 30/5 = 6.0
• B: 40/10 = 4.0
• C: 45/15 = 3.0
Step 2 — Sort by ratio (highest first)
Order: A (6.0), B (4.0), C (3.0).
Step 3 — Fill the truck greedily
Start: remaining capacity = 25 kg, total profit = 0.
1. Take A completely: weight = 5, profit = 30.
Remaining capacity = 25 − 5 = 20. Total profit = 30.
2. Take B completely: weight = 10, profit = 40.
Remaining capacity = 20 − 10 = 10. Total profit = 30 + 40 = 70.
2
3. Item C has weight 15 but only 10 kg capacity left → take fraction 10/15 = 3of C.
2
Profit from fraction = 3 × 45 = 30.
Remaining capacity = 0. Total profit = 70 + 30 = 100.
Maximum profit = 100.
2
• Selection: take A (full), B (full), and 3of C.

Q. Given the following items and knapsack capacity W = 20:

Item Weight Value
1 5 25
2 8 50
3 12 60
Apply the fractional knapsack algorithm.
Calculate:
(a) value/weight ratio
(b) which items (or fraction) you select
(c) maximum obtainable value.
Solution:
Given: Knapsack capacity 𝑾 = 𝟐𝟎
Item Weight 𝑤𝑖 Value 𝑣𝑖
1 5 25
2 8 50
3 12 60
(a) Compute value/weight ratios
value
ratio =
weight

• Item 1: 25/5 = 5.0

• Item 2: 50/8 = 6.25
• Item 3: 60/12 = 5.0
Ratios:
Item Ratio
1 5.0
2 6.25
3 5.0
(b) Select items using fractional knapsack
Step 1 — Sort by ratio (highest first)
Order: Item 2, Item 1, Item 3.
Step 2 — Fill knapsack
Start with capacity = 20, total value = 0.
Take Item 2
• Weight = 8, Value = 50
• Remaining capacity = 20 − 8 = 12
• Total value = 50
Next Item 1
• Weight = 5, Value = 25
• Remaining capacity = 12 − 5 = 7
• Total value = 50 + 25 = 75
Next Item 3
• Weight = 12, but remaining capacity = 7
7
• Take fraction = 12
Value taken =
7
× 60 = 35
12

Remaining capacity = 0
Total value = 75 + 35 = 110
(c) Maximum obtainable value
110
Items selected:
• Item 2 → full
• Item 1 → full
 7
• Item 3 → 12fraction
Q. write the recursive statement for finding the optimal solution in fractional knapsack problem
Solution:
Let:
• 𝑊= remaining capacity
• (𝑤𝑖 , 𝑣𝑖 )= weight and value of the current item
• 𝑥𝑖 ∈ [0,1]= fraction of item 𝑖taken
𝑣
• 𝑟𝑖 = 𝑖 = value/weight ratio
𝑤 𝑖
Assume items are sorted in descending order of ratio.
Recursive formula:
0 if 𝑊 = 0
𝐹(𝑊) = {𝑣𝑖 + 𝐹(𝑊 − 𝑤𝑖 ) if 𝑤𝑖 ≤ 𝑊 (take full item)
𝑊 ⋅ 𝑟𝑖 if 𝑤𝑖 > 𝑊 (take a fraction and stop)

• If the knapsack is full → value is 0 because nothing more can be added.

• If the current item fits → take it completely and recur with the remaining capacity.
• If it does not fit → take the fraction that fits and terminate (no further recursion needed).
Q. Give iterative code for finding optimal solution of fractional knapsack problem.
Solution:
• = remaining capacity of knapsack
• Items are sorted in descending order of value/weight ratio
• For each item 𝑖, weight 𝑤𝑖 , value 𝑣𝑖 , ratio 𝑟𝑖 = 𝑣𝑖 /𝑤𝑖
Initialize totalValue = 0
Initialize remainingCapacity = W
For i = 1 to n:
If remainingCapacity == 0:
break
If w_i ≤ remainingCapacity:
// Take full item
totalValue = totalValue + v_i
remainingCapacity = remainingCapacity - w_i
Else:
// Take fractional part
fraction = remainingCapacity / w_i
totalValue = totalValue + fraction * v_i
remainingCapacity = 0
break
Q. Give the greedy solution to activity selection problem?
Solution:
The greedy strategy for activity selection is:
Always select the activity that finishes earliest.
Your steps match this perfectly:
1. Pick the request with the smallest finishing time.
✔ Greedy choice property
2. Add it to the solution set A.
3. Remove all incompatible activities (those that start before this one finishes).
4. Repeat until no activities remain.
Q. Prove that the greedy solution to activity selection problem yields an optimal set A.
Solution:
• We have a set of requests (activities) 𝑅 = {1,2, . . . , 𝑛}.
• Each activity 𝑖has a start time 𝑠𝑖 and a finish time 𝑓𝑖 .
• Two activities are compatible if their time intervals do not overlap.
• Goal: Select the maximum number of compatible activities.
The greedy algorithm is:
1. Initialize 𝐴 = ∅.
2. While 𝑅 ≠ ∅:
o Choose 𝑖 ∈ 𝑅with the earliest finishing time 𝑓𝑖 .
o Add 𝑖to 𝐴.
o Remove 𝑖and all activities incompatible with 𝑖from 𝑅.
3. Return 𝐴.
We want to prove that 𝐴is optimal.
Proof (Greedy Choice Property + Optimal Substructure)
We use induction and the greedy choice property.
Step 1: Greedy Choice Property
Claim: Choosing the activity with the earliest finish time is safe—it can be extended to an optimal
solution.
Reasoning:
• Let 𝐴∗ be an optimal solution.
• Let 𝑖be the activity selected by the greedy algorithm (earliest finish time).
• Suppose 𝑖 ∉ 𝐴∗ .
We can replace the first activity in 𝐴∗ with 𝑖without reducing the total number of activities, because:
• 𝑖finishes earliest, so any activity that starts after 𝑖is compatible with it.
• Therefore, the rest of the activities in 𝐴∗ that start after the first one are still compatible.
So we can assume there exists an optimal solution that includes the greedy choice.
This proves the greedy choice property.
Step 2: Optimal Substructure
After choosing the greedy activity 𝑖:
• Let 𝑅 ′ be the set of activities compatible with 𝑖(i.e., start after 𝑖finishes).
• The problem of selecting the maximum number of activities from 𝑅 ′ is the same problem on
a smaller set.
Let 𝐴′ be the set returned by recursively applying the greedy algorithm on 𝑅 ′ .
• By induction, 𝐴′ is optimal for 𝑅 ′ .
• Adding 𝑖to 𝐴′ gives the optimal solution for the original problem.
Step 3: Induction
Base case: If 𝑅is empty, 𝐴 = ∅is trivially optimal.
Induction step:
• Assume greedy algorithm works for sets smaller than 𝑛.
• For a set of size 𝑛, pick the activity 𝑖with earliest finish time.
• Remove incompatible activities, leaving 𝑅 ′ .
• By induction, the greedy algorithm finds the optimal solution for 𝑅 ′ .
• Adding 𝑖gives the optimal solution for the original problem.
By induction, the greedy algorithm always produces an optimal set of activities.
Step 4: Conclusion
• The greedy choice property ensures that picking the earliest finishing activity is safe.
 • Optimal substructure ensures that solving the smaller subproblem recursively leads to an
optimal solution.
Therefore, the algorithm returns an optimal set 𝐴of compatible activities.
Suppose we have activities with start and finish times:
Activity Start 𝑠𝑖 Finish 𝑓𝑖
A 1 4
B 3 5
C 0 6
D 5 7
E 8 9
F 5 9
We want the maximum set of non-overlapping activities.
Step 1: Sort by finish time
Sorted by 𝑓𝑖 :
Activity Start Finish
A 1 4
B 3 5
C 0 6
D 5 7
E 8 9
F 5 9
Step 2: Apply the greedy algorithm
1. Pick A (earliest finish, 4) → add to 𝐴.
2. Remove incompatible activities (overlapping with A).
o B (3–5) overlaps → remove
o C (0–6) overlaps → remove
3. Remaining activities: D, E, F
4. Pick D (earliest finish 7) → add to 𝐴.
5. Remove incompatible: F (5–9 overlaps) → remove
6. Remaining: E
7. Pick E (finish 9) → add to 𝐴.
8. No remaining activities.
Resulting set
𝐴 = {𝐴, 𝐷, 𝐸}

This is optimal, as no other set can have more than 3 compatible activities.
Step 3: Replacement Argument
Suppose an optimal solution was: 𝐴∗ = {𝐵, 𝐷, 𝐸}
• Greedy chose A instead of B.
• Since A finishes earlier than B, we can replace B with A in 𝐴∗ without affecting compatibility.
• This proves the greedy choice property visually.
Diagram (timeline)
Time: 0 1 2 3 4 5 6 7 8 9
C: |---------|
A: |----|
B: |---|
D: |--|
F: |----|
E: |--|

Greedy selection: A (1–4), D (5–7), E (8–9)

• Overlapping activities are skipped automatically.
• Picking earliest finish ensures maximum room for future activities.
Q. Prove that in any instance of Interval Partitioning, the number of resources needed is at least
the depth of the set of intervals.
Solution:
• Interval Partitioning Problem:
Given a set of intervals 𝐼 = {𝐼1 , 𝐼2 , … , 𝐼𝑛 }with start times 𝑠𝑖 and finish times 𝑓𝑖 , assign
resources (rooms, machines, etc.) so that no two overlapping intervals share the same
resource.
• Depth:
The depth of the set of intervals is the maximum number of intervals that overlap at any
point in time.
Claim:
The minimum number of resources required ≥depth of the intervals.
Proof
Step 1: Consider the point of maximum overlap
• Let 𝑡 ∗ be the time where the depth is achieved.
• Let the number of intervals overlapping at 𝑡 ∗ be 𝑑(so depth = 𝑑).
Step 2: Argument
• At time 𝑡 ∗ , there are 𝑑intervals that all overlap.
• By definition of interval partitioning: no two overlapping intervals can use the same
resource.
Therefore, to schedule the 𝑑overlapping intervals simultaneously, you need at least 𝑑different
resources.
Step 3: Conclude
• Let 𝑅min = minimum number of resources required.
• Then clearly, 𝑅min ≥ 𝑑(because you cannot schedule 𝑑overlapping intervals on fewer than
𝑑resources).
Hence, the number of resources needed is at least the depth of the set of intervals.

Q. When Is It Safe to Include an Edge in the Minimum Spanning Tree?

Solution:
Safe Edge
An edge 𝑒 = (𝑢, 𝑣)is safe to include in the MST if it can be added to the growing MST without
violating the MST properties, i.e., it will not create a cycle and it can potentially belong to some MST.
Formally:
An edge is safe if it is a lightest edge crossing some cut of the graph.
Step 1: Definitions
1. Cut:
o A cut of a graph is a partition of the vertices into two disjoint sets 𝑆and 𝑉 ∖ 𝑆.
o Denote the cut as (𝑆, 𝑉 ∖ 𝑆).
2. Edge Crossing a Cut:
 o An edge (𝑢, 𝑣)crosses the cut if one endpoint is in 𝑆and the other is in 𝑉 ∖ 𝑆.
3. Light Edge:
o An edge (𝑢, 𝑣)crossing a cut is light if it has minimum weight among all edges
crossing the cut.
Step 2: Safe Edge Property (Cut Property)
Cut Property: Let 𝑆be any subset of vertices and let edge (𝑢, 𝑣)be a light edge crossing the cut
(𝑆, 𝑉 ∖ 𝑆). Then (𝑢, 𝑣)is safe to include in the MST.
Explanation:
• Suppose we already have a set of MST edges 𝐴that does not violate any MST.
• Consider a cut (𝑆, 𝑉 ∖ 𝑆)that respects 𝐴(no edge in 𝐴crosses the cut).
• Adding the lightest edge crossing the cut cannot create a cycle.
• Therefore, it is safe to include in some MST.
Step 3: Intuition
• Always pick the smallest edge connecting two disjoint parts of the graph.
• Adding it ensures minimum weight and keeps the MST property.
• This is exactly why Kruskal’s algorithm works:
1. Sort edges by weight
2. Add edges in increasing order
3. Skip edges that form a cycle
• And Prim’s algorithm works because:
1. Start from a vertex
2. Always add the minimum-weight edge connecting MST-so-far to a new vertex
3. This is always a safe edge by the cut property
Step 4: Summary (Safe Edge Condition)
An edge (𝑢, 𝑣)is safe to include in an MST if:
1. There exists a cut (𝑆, 𝑉 ∖ 𝑆)such that:
o One vertex of the edge is in 𝑆, the other in 𝑉 ∖ 𝑆
o The edge is the minimum weight edge crossing the cut
2. Adding it does not form a cycle with edges already in the MST
If both conditions hold, the edge can be safely added to the MST.
Q. prove that Assume that all edge costs are distinct. Let S be any subset of nodes that is neither
empty nor equal to all of V, and let edge e = (v, w) be the minimumcost edge with one end in S and
the other in V − S. Then every minimum spanning tree contains the edge e.
Solution:
Let 𝐺 = (𝑉, 𝐸)be a connected graph with distinct edge costs. Let 𝑆 ⊂ 𝑉be any subset that is neither
empty nor all of 𝑉. Let 𝑒 = (𝑣, 𝑤)be the minimum-cost edge crossing the cut (𝑆, 𝑉 ∖ 𝑆). Then every
minimum spanning tree of G contains the edge e.
Proof
Step 1: Assume the contrary
Suppose there exists an MST 𝑇that does not include edge 𝑒.
• Let 𝑇be any MST of 𝐺.
• Since 𝑇is a spanning tree, it connects all vertices in 𝑉, including vertices in 𝑆and 𝑉 ∖ 𝑆.
• Therefore, there must exist another edge 𝑓 ∈ 𝑇that crosses the cut (𝑆, 𝑉 ∖ 𝑆).
• 𝑓 ≠ 𝑒because we assumed 𝑒 ∉ 𝑇.
Step 2: Compare weights
• By assumption, all edge weights are distinct.
• 𝑒is the minimum-cost edge crossing the cut.
• Therefore:
 𝑐(𝑒) < 𝑐(𝑓)

Step 3: Create a new spanning tree

• Add edge 𝑒to 𝑇.
• Adding 𝑒to 𝑇creates a cycle (because 𝑇is already a tree).
• This cycle must include 𝑓because 𝑓is the edge connecting the two sides of the cut.
• Remove 𝑓from the cycle.
• The resulting graph is still a spanning tree, let’s call it 𝑇 ′ .
Step 4: Compare total costs
Cost(𝑇 ′ ) = Cost(𝑇) − 𝑐(𝑓) + 𝑐(𝑒) < Cost(𝑇)

• Because 𝑐(𝑒) < 𝑐(𝑓), the total cost of 𝑇 ′ is less than that of 𝑇.
• But 𝑇was assumed to be an MST. Contradiction!
Step 5: Conclude
• Therefore, our assumption that some MST does not contain 𝑒is false.
• Hence, every MST must contain the minimum-cost edge crossing any cut.
Step 6: Why distinct weights matter
• Distinct edge weights ensure that the minimum-cost edge across the cut is unique.
• This guarantees that every MST contains that specific edge.
• If weights were not distinct, there could be multiple MSTs, and not all of them need to
include a particular minimum-weight edge.
Summary
• Pick any cut (𝑆, 𝑉 ∖ 𝑆).
• Let 𝑒be the unique minimum-cost edge crossing it.
• Then 𝑒is in every MST.
This is exactly why Kruskal’s and Prim’s algorithms always work: they repeatedly pick the minimum
edge crossing a cut.
Q. Show that Prim’s Algorithm produces a minimum spanning tree of G.
Given a connected, weighted graph 𝐺 = (𝑉, 𝐸):
1. Start with an arbitrary vertex 𝑣0 .
2. Initialize a tree 𝑇containing 𝑣0 .
3. While 𝑇does not include all vertices:
o Find the minimum-weight edge 𝑒 = (𝑢, 𝑣)such that 𝑢 ∈ 𝑇and 𝑣 ∉ 𝑇.
o Add 𝑣and edge 𝑒to 𝑇.
At the end, 𝑇spans all vertices.
Claim
The tree 𝑇produced by Prim’s algorithm is a Minimum Spanning Tree.
Proof (Using the Cut Property)
Step 1: Define the cut
At each step:
• Let 𝑆= set of vertices already included in 𝑇
• Let 𝑉 ∖ 𝑆= remaining vertices
• Consider the cut (𝑆, 𝑉 ∖ 𝑆).
Step 2: Pick the minimum edge crossing the cut
• Prim’s algorithm selects the minimum-weight edge 𝑒crossing the cut.
• By the cut property:
Any minimum-weight edge crossing a cut is safe to include in an MST.
• So adding 𝑒to 𝑇does not prevent 𝑇from being part of an MST.
Step 3: Repeat until all vertices are included
• Each time we add a vertex via the minimum-weight edge crossing the current cut, we
maintain a tree that can be extended to an MST.
• By induction:
1. Initially, 𝑇 = {𝑣0 }is trivially part of some MST.
2. Assume after 𝑘steps, 𝑇can be extended to an MST.
3. Adding the minimum edge crossing the cut preserves the MST property (safe edge).
• Eventually, all vertices are included → 𝑇is an MST.
Step 4: Key Properties
1. Connected: Algorithm only adds edges connecting 𝑇to a new vertex → tree remains
connected.
2. Acyclic: Each edge adds exactly one new vertex → no cycles formed.
3. Spanning: Stops when all vertices included → tree spans all vertices.
4. Minimum Weight: By the cut property, each edge added is safe → total weight is minimized.
Step 5: Conclusion
• Prim’s algorithm always produces a Minimum Spanning Tree.
• Works for any connected, weighted graph (distinct or non-distinct weights).
Q. Give algorithm to find the minimum spanning tree of a graph.
Solution:
Prim’s Algorithm (Vertex-Based)
Idea: Grow MST from a starting vertex by always adding the minimum-weight edge connecting MST
to a new vertex.
Input: Connected graph 𝐺 = (𝑉, 𝐸)with edge weights 𝑤(𝑒)
Output: MST 𝑇 ⊆ 𝐸
Algorithm:
1. Choose an arbitrary starting vertex 𝑣0
2. Initialize 𝑇 = ∅, 𝑋 = {𝑣0 }(vertices in MST)
3. While ∣ 𝑋 ∣<∣ 𝑉 ∣:
o Find the minimum-weight edge (𝑢, 𝑣)such that 𝑢 ∈ 𝑋and 𝑣 ∉ 𝑋
o Add edge (𝑢, 𝑣)to 𝑇
o Add vertex 𝑣to 𝑋
4. Return 𝑇
Time Complexity
• Using a priority queue (min-heap):
o Each vertex insertion and edge update: 𝑂(log⁡ 𝑉)
o Total: 𝑂(𝐸log⁡ 𝑉)