Greedy Algorithms

1. Introduction
• Definition:
A greedy algorithm is an algorithmic paradigm that builds up a solution piece by piece,
always choosing the option that seems best at the moment. It is primarily used for
optimization problems.
• Key Idea:
At every step, the algorithm makes the "locally optimal" choice in the hope that this
leads to a "globally optimal" solution.

2. When to Use Greedy Algorithms

• Optimization Problems:
Problems where you need to make a sequence of decisions to optimize (minimize or
maximize) a given objective.
• Suitable Properties:
o Greedy Choice Property:
The overall optimal solution can be achieved by making the locally optimal
choice at each step.
o Optimal Substructure:
An optimal solution to the problem contains optimal solutions to its
subproblems.
• Common Examples:
o Fractional Knapsack Problem
o Kruskal’s and Prim’s Algorithms for minimum spanning trees
o Huffman Coding for data compression

3. Characteristics of Greedy Algorithms

• Simplicity and Ease of Implementation:
The straightforward nature of always choosing the best available option makes greedy
algorithms simple to design.
• Efficiency:
Often very efficient in terms of time complexity, making them suitable for problems
where a quick, if approximate, solution is acceptable.
• No Reconsideration:
 Greedy algorithms do not reconsider past decisions. Once a choice is made, it is never
revisited even if it might later turn out to be suboptimal.
• Comparison with Other Techniques:
In problems where both greedy and dynamic programming approaches are applicable
(e.g., Jump Game, Single Source Shortest Path without negative weights), the greedy
approach is typically faster and easier to implement.

4. How Greedy Algorithms Work

Step-by-Step Process:
1. Initialization:
Start with an initial state of the problem.
2. Evaluation:
At each step, consider all possible choices from the current state.
3. Selection:
Choose the option that looks best at that moment (i.e., the locally optimal choice).
4. Transition:
Move to the new state that results from the chosen option.
5. Iteration:
Repeat the evaluation and selection process until you reach the goal state or no further
progress can be made.

Knapsack Algorithm

The Knapsack Algorithm is a well-known optimization algorithm used to solve the

Knapsack Problem, which is a combinatorial problem in computer science and
optimization. The problem can be described as follows:
Problem Statement
Given a set of items, each with a weight and a value, determine the maximum value
that can be obtained by selecting a subset of items, ensuring that the total weight does
not exceed a given capacity.
Types of Knapsack Problems
1. 0/1 Knapsack Problem
o Each item can either be included once (1) or not at all (0).
o Solved using Dynamic Programming (DP).
2. Fractional Knapsack Problem
 o Items can be broken into smaller pieces.
o Solved using Greedy Approach.
Example
Let's consider an example to understand the Fractional Knapsack Problem using the
Greedy Algorithm.
Problem Statement
You are given a knapsack with a capacity of 50 kg, and the following items:

Item Value ($) Weight (kg) Value/Weight ($/kg)

1 60 10 6.0

2 100 20 5.0

3 120 30 4.0

Find the maximum value you can obtain.

Step-by-Step Solution
Step 1: Calculate Value-to-Weight Ratio
We calculate the value per weight for each item:
• Item 1: 60/10=6.060 / 10 = 6.060/10=6.0
• Item 2: 100/20=5.0100 / 20 = 5.0100/20=5.0
• Item 3: 120/30=4.0120 / 30 = 4.0120/30=4.0
Step 2: Sort Items by Value/Weight Ratio (Descending Order)

Item Value ($) Weight (kg) Value/Weight ($/kg)

1 60 10 6.0

2 100 20 5.0

3 120 30 4.0

Step 3: Select Items Greedily

We start with 50 kg capacity and select items:
1. Take full Item 1 (10 kg, value = $60)
o Remaining capacity = 50 - 10 = 40 kg
o Total value = $60
2. Take full Item 2 (20 kg, value = $100)
o Remaining capacity = 40 - 20 = 20 kg
 o Total value = $160
3. Take 20 kg of Item 3 (partial, value = (20/30) × 120 = $80)
o Remaining capacity = 0 kg (Knapsack full)
o Total value = $240
Final Answer
The maximum value we can carry in the Fractional Knapsack is $240.

Job Sequencing Algorithm

The Job Sequencing Problem is a greedy algorithm used to schedule jobs to maximize profit,
given that each job has a deadline and profit and can only be scheduled within a limited time.
Problem Statement
You are given n jobs, where each job has:
• Profit (P[i]) – The amount earned if the job is completed.
• Deadline (D[i]) – The latest time by which the job must be completed.
• Execution Time – Each job takes exactly one unit of time.
The objective is to schedule jobs to maximize profit, ensuring that no two jobs overlap.
Step-by-Step Approach (Greedy Algorithm)
1. Sort jobs in decreasing order of profit (highest profit first).
2. Create a schedule array of size max deadline (to track assigned slots).
3. For each job, place it in the latest available slot before its deadline.
4. If a slot is available, assign the job; otherwise, move to the previous slot.
5. Continue until all jobs are placed or no slots are left.
Example
Given Jobs:

Job Profit ($) Deadline

J1 100 2

J2 50 1

J3 20 2

J4 200 1

J5 150 3

Step 1: Sort Jobs by Profit (Descending Order)

Job Profit ($) Deadline

J4 200 1

J5 150 3

J1 100 2

J2 50 1

J3 20 2

Step 2: Schedule Jobs

• J4 → Slot 1
• J5 → Slot 3
• J1 → Slot 2
• J2 → No available slot (slot 1 is already occupied by J4)
• J3 → No available slot (slots 1 & 2 are occupied by J4 & J1)
Final Schedule:
 Time Slot Job

1 J4

2 J1

3 J5

Total Profit = 200 + 100 + 150 = $450

Example 2: Given Jobs:

Job Profit ($) Deadline

J1 100 3

J2 50 1

J3 200 3

J4 30 2

Total Slots Available: 3 (Since the maximum deadline is 3)

Step 1: Sort Jobs by Profit (Descending Order)

Job Profit ($) Deadline

J3 200 3

J1 100 3

J2 50 1

J4 30 2

Step 2: Assign Jobs to Slots (Checking Backward If Needed)

1. J3 (Profit = 200, Deadline = 3)
o Check Slot 3 → Empty (Yes) → Place J3 in Slot 3
2. J1 (Profit = 100, Deadline = 3)
o Check Slot 3 → Already occupied by J3
o Check Slot 2 → Empty (Yes) → Place J1 in Slot 2
3. J2 (Profit = 50, Deadline = 1)

o Check Slot 1 → Empty (Yes)→ Place J2 in Slot 1

4. J4 (Profit = 30, Deadline = 2)
 o Check Slot 2 → Already occupied by J1
o Check Slot 1 → Already occupied by J2
o No earlier slots available → J4 is skipped

Final Job Schedule (After Backward Checking)

Time Slot Job

1 J2

2 J1

3 J3

Total Profit = 50 + 100 + 200 = $350

Failure of Greedy Algorithm in Job Sequencing Problem

While the Greedy Algorithm for Job Sequencing works well in most cases, it fails to find the
optimal solution in some scenarios because it prioritizes immediate highest profit without
considering future benefits.

Example Where Greedy Fails

Consider the following set of jobs:

Job Profit ($) Deadline

J1 40 2

J2 20 1

J3 30 2

J4 10 1

Total Available Slots = 2 (max deadline is 2).

 Huffman Coding
•
Huffman coding is a lossless data compression algorithm. The idea is to assign variable-length
codes to input characters, lengths of the assigned codes are based on the frequencies of
corresponding characters. The variable-length codes assigned to input characters are Prefix
Codes, means the codes (bit sequences) are assigned in such a way that the code assigned to
one character is not the prefix of code assigned to any other character. This is how Huffman
Coding makes sure that there is no ambiguity when decoding the generated bitstream.
Let us understand prefix codes with a counter example. Let there be four characters a, b, c and
d, and their corresponding variable length codes be 00, 01, 0 and 1. This coding leads to
ambiguity because code assigned to c is the prefix of codes assigned to a and b. If the
compressed bit stream is 0001, the de-compressed output may be “cccd” or “ccb” or “acd” or
“ab”.
There are mainly two major parts in Huffman Coding
1. Build a Huffman Tree from input characters.
2. Traverse the Huffman Tree and assign codes to characters.
Algorithm:
The method which is used to construct optimal prefix code is called Huffman coding.
This algorithm builds a tree in bottom up manner. We can denote this tree by T
Let, |c| be number of leaves
|c| -1 are number of operations required to merge the nodes. Q be the priority queue which can be used
while constructing binary heap.
Algorithm Huffman (c)
{
n= |c|

Q=c
for i<-1 to n-1

do
{

temp <- get node ()

left (temp] Get_min (Q) right [temp] Get Min (Q)

a = left [templ b = right [temp]

 F [temp]<- f[a] + [b]

insert (Q, temp)

return Get_min (0)

}

Steps to build Huffman Tree

1. Input is an array of unique characters along with their frequency of
occurrences and output is Huffman Tree.
2. Create a leaf node for each unique character and build a min heap of all leaf
nodes (Min Heap is used as a priority queue. The value of frequency field is
used to compare two nodes in min heap. Initially, the least frequent character
is at root)
3. Extract two nodes with the minimum frequency from the min heap.
4. Create a new internal node with a frequency equal to the sum of the two
nodes frequencies. Make the first extracted node as its left child and the other
extracted node as its right child. Add this node to the min heap.
5. Repeat steps#2 and #3 until the heap contains only one node. The remaining
node is the root node and the tree is complete.
Let us understand the algorithm with an example:

character Frequency
a 5
b 9
c 12
d 13
e 16
f 45
Step 1. Build a min heap that contains 6 nodes where each node represents root of a tree with single
node.
Step 2 Extract two minimum frequency nodes from min heap. Add a new internal node with
frequency 5 + 9 = 14.
 Illustration of step 2
Now min heap contains 5 nodes where 4 nodes are roots of trees with single element each, and one
heap node is root of tree with 3 elements
character Frequency
c 12
d 13
Internal Node 14
e 16
f 45
Step 3: Extract two minimum frequency nodes from heap. Add a new internal node with frequency 12
+ 13 = 25

Illustration of step 3
Now min heap contains 4 nodes where 2 nodes are roots of trees with single element each, and two
heap nodes are root of tree with more than one nodes

character Frequency
Internal Node 14
e 16
Internal Node 25
f 45
Step 4: Extract two minimum frequency nodes. Add a new internal node with frequency 14 + 16 = 30
 Illustration of step 4
Now min heap contains 3 nodes.

character Frequency
Internal Node 25
Internal Node 30
f 45
Step 5: Extract two minimum frequency nodes. Add a new internal node with frequency 25 + 30 = 55

Illustration of step 5
Now min heap contains 2 nodes.
character Frequency
f 45
Internal Node 55
Step 6: Extract two minimum frequency nodes. Add a new internal node with frequency 45 + 55 =
100
 Illustration of step 6
Now min heap contains only one node.
character Frequency
Internal Node 100
Since the heap contains only one node, the algorithm stops here.
Steps to print codes from Huffman Tree:
Traverse the tree formed starting from the root. Maintain an auxiliary array. While moving to the left
child, write 0 to the array. While moving to the right child, write 1 to the array. Print the array when a
leaf node is encountered.

Steps to print code from HuffmanTree

The codes are as follows:
 character code-word
f 0
c 100
d 101
a 1100
b 1101
e 111

Kruskal's minimal spanning tree algorithm

Kruskal's minimal spanning tree algorithm is one of the efficient methods to find the minimum
spanning tree of a graph. A minimum spanning tree is a subgraph that connects all the vertices
present in the main graph with the least possible edges and minimum cost (sum of the weights
assigned to each edge).
The algorithm first starts from the forest which is defined as a subgraph containing only vertices
of the main graph of the graph, adding the least cost edges later until the minimum spanning
tree is created without forming cycles in the graph.
Kruskal's algorithm has easier implementation than prims algorithm, but has higher
complexity.
Kruskal's Algorithm
The inputs taken by the kruskals algorithm are the graph G {V, E}, where V is the set of vertices
and E is the set of edges, and the source vertex S and the minimum spanning tree of graph G is
obtained as an output.
Algorithm
• Sort all the edges in the graph in an ascending order and store it in an array edge[].
• Construct the forest of the graph on a plane with all the vertices in it.
• Select the least cost edge from the edge[] array and add it into the forest of the graph.
Mark the vertices visited by adding them into the visited[] array.
• Repeat the steps 2 and 3 until all the vertices are visited without having any cycles
forming in the graph
• When all the vertices are visited, the minimum spanning tree is formed.
• Calculate the minimum cost of the output spanning tree formed.
Examples
Construct a minimum spanning tree using kruskals algorithm for the graph given below −
Solution
As the first step, sort all the edges in the given graph in an ascending order and store the
values in an array.

Edge B→D A→B C→F F→E B→C G→F A→G C→D D→E C→G

Cost 5 6 9 10 11 12 15 17 22 25

Then, construct a forest of the given graph on a single plane.

From the list of sorted edge costs, select the least cost edge and add it onto the forest in
output graph.
B→D=5
Minimum cost = 5
Visited array, v = {B, D}

Similarly, the next least cost edge is B → A = 6; so we add it onto the output graph.
Minimum cost = 5 + 6 = 11
Visited array, v = {B, D, A}
The next least cost edge is C → F = 9; add it onto the output graph.
Minimum Cost = 5 + 6 + 9 = 20
Visited array, v = {B, D, A, C, F}

The next edge to be added onto the output graph is F → E = 10.

Minimum Cost = 5 + 6 + 9 + 10 = 30
Visited array, v = {B, D, A, C, F, E}
The next edge from the least cost array is B → C = 11, hence we add it in the output graph.
Minimum cost = 5 + 6 + 9 + 10 + 11 = 41
Visited array, v = {B, D, A, C, F, E}

The last edge from the least cost array to be added in the output graph is F → G = 12.
Minimum cost = 5 + 6 + 9 + 10 + 11 + 12 = 53
Visited array, v = {B, D, A, C, F, E, G}

The obtained result is the minimum spanning tree of the given graph with cost = 53.
 Prims Minimal Spanning Tree
Prim's minimal spanning tree algorithm is one of the efficient methods to find the minimum
spanning tree of a graph. A minimum spanning tree is a sub graph that connects all the vertices
present in the main graph with the least possible edges and minimum cost (sum of the weights
assigned to each edge).
The algorithm, similar to any shortest path algorithm, begins from a vertex that is set as a root
and walks through all the vertices in the graph by determining the least cost adjacent edges.

Prim's Algorithm
To execute the prim's algorithm, the inputs taken by the algorithm are the graph G {V, E},
where V is the set of vertices and E is the set of edges, and the source vertex S. A minimum
spanning tree of graph G is obtained as an output.
Algorithm
• Declare an array visited[] to store the visited vertices and firstly, add the arbitrary root,
say S, to the visited array.
• Check whether the adjacent vertices of the last visited vertex are present in
the visited[] array or not.
• If the vertices are not in the visited[] array, compare the cost of edges and add the least
cost edge to the output spanning tree.
• The adjacent unvisited vertex with the least cost edge is added into the visited[] array
and the least cost edge is added to the minimum spanning tree output.
• Steps 2 and 4 are repeated for all the unvisited vertices in the graph to obtain the full
minimum spanning tree output for the given graph.
• Calculate the cost of the minimum spanning tree obtained.
Examples
• Find the minimum spanning tree using prims method (greedy approach) for the graph
given below with S as the arbitrary root.

Solution
Step 1
Create a visited array to store all the visited vertices into it.
V={}
The arbitrary root is mentioned to be S, so among all the edges that are connected to S we
need to find the least cost edge.
S→B=8
V = {S, B}

Step 2
Since B is the last visited, check for the least cost edge that is connected to the vertex B.
B →A=9
B → C = 16
B → E = 14
Hence, B → A is the edge added to the spanning tree.
V = {S, B, A}

Step 3
Since A is the last visited, check for the least cost edge that is connected to the vertex A.
A → C = 22
A→B=9
A → E = 11
But A → B is already in the spanning tree, check for the next least cost edge. Hence, A → E
is added to the spanning tree.
V = {S, B, A, E}

Step 4
Since E is the last visited, check for the least cost edge that is connected to the vertex E.
E → C = 18
E→D=3
Therefore, E → D is added to the spanning tree.
V = {S, B, A, E, D}

Step 5
Since D is the last visited, check for the least cost edge that is connected to the vertex D.
D → C = 15
E→D=3
Therefore, D → C is added to the spanning tree.
V = {S, B, A, E, D, C}

The minimum spanning tree is obtained with the minimum cost = 46

 Activity Selection Problem
The Activity Selection Problem is a classic problem in Greedy Algorithms, where the goal
is to select the maximum number of non-overlapping activities that can be scheduled using a
single resource.
Problem Statement
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.
Greedy Approach
The idea is to always choose the activity that finishes first (to leave space for upcoming
activities).
Algorithm
1. Sort the activities based on their finish time.
2. Select the first activity (which has the earliest finish time).
3. Iterate through the remaining activities:
o If the start time of an activity is greater than or equal to the finish time of the
previously selected activity, select it.
4. Repeat until all activities are checked.
Example Walkthrough
Given Activities (Start Time, Finish Time)

Activity Start Time Finish Time

A1 1 3

A2 2 5

A3 3 9

A4 6 8

A5 5 7

Step 1: Sort Activities by Finish Time

The greedy approach sorts the activities in increasing order of finish time.

Activity Start Time Finish Time

A1 1 3
 Activity Start Time Finish Time

A2 2 5

A5 5 7

A4 6 8

A3 3 9

Step 2: Select Activities Using the Greedy Strategy

• Initialize last_finish_time = 0
• Iterate through sorted activities and select if start_time >= last_finish_time.

Step Considered Activity Start Time Finish Time Can be Selected? Selected Activities

1 A1 1 3 ✅ Yes (1 ≥ 0) {A1}

2 A2 2 5 ❌ No (2 < 3) {A1}

3 A5 5 7 ✅ Yes (5 ≥ 3) {A1, A5}

4 A4 6 8 ❌ No (6 < 7) {A1, A5}

5 A3 3 9 ❌ No (3 < 7) {A1, A5}

Final Selected Activities

The maximum number of non-overlapping activities selected using the Greedy Algorithm
is: ✅ A1 (1,3) ✅ A5 (5,7)
Thus, the final selected activities are:
{A1, A5}