Greedy Algorithm
Alapan Kuila
Sitare University, Lucknow
September 16, 2025
Alapan Kuila Greedy Algorithm September 16, 2025 1 / 15
Greedy Strategy
Greedy Choice Property
Optimal Substructure
Alapan Kuila Greedy Algorithm September 16, 2025 2 / 15
Problem 1
Given an array F with size n. Assume that the array content F [i] indicates
the length of the ith file, and we want to merge all these files into one
single file. What will be the best strategy?
Note: Given two files A and B with sizes m and n, the complexity of
merging is O(m + n)
Alapan Kuila Greedy Algorithm September 16, 2025 3 / 15
Problem 1: Solution
F = {10, 5, 100, 50, 20, 15}
Algorithm 1: Merge the files contigiously. That means select the
first two files and merge them. Then select the output of previous
merge with third file and keep going.
Total cost of merging: ??
Algorithm 2: Merge the files in pairs. After first step, we need to
consider these intermediate files and merge them in pairs and keep
going.
Total cost of merging: ??
Alapan Kuila Greedy Algorithm September 16, 2025 4 / 15
Problem 1: Greedy Solution
Algorithm 3:
1 Sort the file sizes in ascending order.
2 Repeat the following until there is only one file:
1 Take first two elements (smallest) X and Y.
2 Merge X and Y and insert this new file in the sorted list.
Time Complexity: ?
Alapan Kuila Greedy Algorithm September 16, 2025 5 / 15
Fractional Knapsack Problem
During a robbery, a burglar finds much more loot than he had expected
and has to decide what to take. His bag (“knapsack”) will hold a total
weight of at most W . There are n items to pick from, of weight
[w1 ,...,wn ] and value [v1 ,...,vn ]. What is the most valuable combination of
items he can fit into his knapsack(bag)?
Goal: Maximize the total value of items in the knapsack, without
exceeding capacity W.
Alapan Kuila Greedy Algorithm September 16, 2025 6 / 15
Problem 2: Fractional Knapsack
Figure: Knapsack Capacity W = 50
Alapan Kuila Greedy Algorithm September 16, 2025 7 / 15
Problem 2: Solution
Maximum Value earned = ?
Combination of the items and their weight = ?
Alapan Kuila Greedy Algorithm September 16, 2025 8 / 15
Problem 2: Greedy Solution
Greedy Approach
1 Compute value/weight ratio (r[i]) for each item
2 Sort items in descending order of ratio r[i]
3 Pick items one by one:
If the current item fits completely, take it.
If it does not, take the fraction that fits.
4 Stop when the knapsack is full.
Maximum Value earned = ?
Combination of the items and their weight = ?
Alapan Kuila Greedy Algorithm September 16, 2025 9 / 15
Graph and Tree
A graph G = (V, E) consists of:
A set of vertices (nodes) V
A set of edges E connecting pairs of vertices
A tree is a special case of a graph with the following properties:
Connected: There is a path between every pair of nodes.
Acyclic: No cycles (closed loops) exist.
If a tree has n nodes, it has exactly (n − 1) edges.
1 We can think of a tree as the minimal connected graph
2 If you remove even one edge, it becomes disconnected; if you add an
edge, it creates a cycle.
Alapan Kuila Greedy Algorithm September 16, 2025 10 / 15
Spanning Tree
A spanning tree of a connected graph is a subgraph that:
Includes all the vertices of the original graph.
Is a tree (connected + acyclic).
If the graph has n vertices, the spanning tree will have n − 1 edges.
A graph can have many different spanning trees.
Alapan Kuila Greedy Algorithm September 16, 2025 11 / 15
Minimum Spanning Tree
When the graph is weighted (each edge has a weight/cost), a minimum
spanning tree is a spanning tree such that:
The total weight of its edges is minimum among all possible
spanning trees.
Alapan Kuila Greedy Algorithm September 16, 2025 12 / 15
Problem 3: Finding Minimum Spanning Tree for a Graph
Alapan Kuila Greedy Algorithm September 16, 2025 13 / 15
MST: Kruskal’s Algorithm
1 List all edges of the graph in non-decreasing order of weights.
2 Add edges one by one
Pick the smallest weight edge from the sorted list.
If adding this edge does not form a cycle, include it in the MST.
If it forms a cycle, skip it.
3 Repeat until MST is formed
Continue until the MST has n − 1 edges (where n = number of
vertices)
Alapan Kuila Greedy Algorithm September 16, 2025 14 / 15
MST: Prim’s Algorithm
1 Start with any vertex
Choose any vertex as the starting point.
Mark it as part of the MST.
2 Pick the minimum edge
From all edges that connect a vertex in the MST to a vertex outside,
Choose the minimum-weight edge.
3 Add the new vertex
Add this edge and its connected vertex to the MST.
4 Repeat
Continue selecting the minimum edge that connects MST to an outside
vertex.
Stop when all vertices are included (MST will have n − 1 edges for n
vertices).
Alapan Kuila Greedy Algorithm September 16, 2025 15 / 15