The ICFAI University Jaipur

Design and Analysis of Algorithm

First Semester: 2025–2026
Greedy Algorithm

The greedy method is one of the strategies like Divide and conquer used to solve the problems. This
method is used for solving optimization problems. An optimization problem is a problem that
demands either maximum or minimum results. Let's understand through some terms.

The Greedy method is the simplest and straightforward approach. It is not an algorithm, but it is a
technique. The main function of this approach is that the decision is taken on the basis of the currently
available information. Whatever the current information is present, the decision is made without
worrying about the effect of the current decision in future.

This technique is basically used to determine the feasible solution that may or may not be optimal.
The feasible solution is a subset that satisfies the given criteria. The optimal solution is the solution
which is the best and the most favorable solution in the subset. In the case of feasible, if more than
one solution satisfies the given criteria then those solutions will be considered as the feasible, whereas
the optimal solution is the best solution among all the solutions.

Characteristics of Greedy method

The following are the characteristics of a greedy method:
 To construct the solution in an optimal way, this algorithm creates two sets where one set contains all
the chosen items, and another set contains the rejected items.
 A Greedy algorithm makes good local choices in the hope that the solution should be either feasible or
optimal.
Components of Greedy Algorithm
Greedy algorithms have the following five components −
 A candidate set − A solution is created from this set.
 A selection function − Used to choose the best candidate to be added to the solution.
 A feasibility function − Used to determine whether a candidate can be used to contribute to the
solution.
 An objective function − Used to assign a value to a solution or a partial solution.
 A solution function − Used to indicate whether a complete solution has been reached.
Applications of Greedy Algorithm
 It is used in finding the shortest path.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
 It is used to find the minimum spanning tree using the prim's algorithm or the Kruskal's
algorithm.
 It is used in a job sequencing with a deadline.

 This algorithm is also used to solve the fractional knapsack problem.

Pseudo code of Greedy Algorithm

1. Algorithm Greedy (a, n)
2. {
3. Solution : = 0;
4. for i = 0 to n do
5. {
6. x: = select(a);
7. if feasible(solution, x)
8. {
9. Solution: = union(solution , x)
10. }
11. return solution;
12. }}

The above is the greedy algorithm. Initially, the solution is assigned with zero value. We pass the
array and number of elements in the greedy algorithm. Inside the for loop, we select the element one
by one and checks whether the solution is feasible or not. If the solution is feasible, then we perform
the union.

Let's understand through an example.

Suppose there is a problem 'P'. I want to travel from A to B shown as below:

P:A→B

The problem is that we have to travel this journey from A to B. There are various solutions to go from
A to B. We can go from A to B by walk, car, bike, train, aeroplane, etc. There is a constraint in the
journey that we have to travel this journey within 12 hrs. If I go by train or aeroplane then only, I can
cover this distance within 12 hrs. There are many solutions to this problem but there are only two
solutions that satisfy the constraint.

If we say that we have to cover the journey at the minimum cost. This means that we have to travel
this distance as minimum as possible, so this problem is known as a minimization problem. Till
Prepared By Kapil Dev Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
now, we have two feasible solutions, i.e., one by train and another one by air. Since travelling by train
will lead to the minimum cost so it is an optimal solution. An optimal solution is also the feasible
solution, but providing the best result so that solution is the optimal solution with the minimum
cost. There would be only one optimal solution.

The problem that requires either minimum or maximum result then that problem is known as an
optimization problem. Greedy method is one of the strategies used for solving the optimization
problems.
Where Greedy Approach Fails
In many problems, Greedy algorithm fails to find an optimal solution, moreover it may produce a
worst solution. Problems like Travelling Salesman and Knapsack cannot be solved using this
approach.
Advantages:
 Finding solution is quite easy with a greedy algorithm for a problem.
 Analyzing the run time for greedy algorithms will generally be much easier than for other
techniques (like Divide and conquer).

Disadvantages of using Greedy algorithm

Greedy algorithm makes decisions based on the information available at each phase without
considering the broader problem. So, there might be a possibility that the greedy solution does not
give the best solution for every problem.
It follows the local optimum choice at each stage with a intend of finding the global optimum. Let's
understand through an example.
Consider the graph which is given below:

We have to travel from the source to the destination at the minimum cost. Since we have three feasible
solutions having cost paths as 10, 20, and 5. 5 is the minimum cost path so it is the optimal solution.
This is the local optimum, and in this way, we find the local optimum at each stage in order to
calculate the global optimal solution.

Minimum Spanning Tree

Before knowing about the minimum spanning tree, we should know about the spanning tree.
Prepared By Kapil Dev Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
To understand the concept of spanning tree, consider the below graph:

The above graph can be represented as G(V, E), where 'V' is the number of vertices, and 'E' is the
number of edges. The spanning tree of the above graph would be represented as G`(V`, E`). In this
case, V` = V means that the number of vertices in the spanning tree would be the same as the number
of vertices in the graph, but the number of edges would be different. The number of edges in the
spanning tree is the subset of the number of edges in the original graph. Therefore, the number of
edges can be written as:

E` € E

It can also be written as:

E` = |V| - 1

Two conditions exist in the spanning tree, which is as follows:

o The number of vertices in the spanning tree would be the same as the number of vertices in the original
graph.

V` = V
o The number of edges in the spanning tree would be equal to the number of edges minus 1.

E` = |V| - 1
o The spanning tree should not contain any cycle.

o The spanning tree should not be disconnected.

Example : consider the below graph: for all possible spanning tree

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
:

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
What is a minimum spanning tree?
The minimum spanning tree is a spanning tree whose sum of the edges is minimum. Consider the
below graph that contains the edge weight:
The following are the spanning trees that we can make from the above graph.
o The first spanning tree is a tree in which we have removed the edge between the vertices 1 and 5 shown
as below:
The sum of the edges of the above tree is (1 + 4 + 5 + 2): 12
o The second spanning tree is a tree in which we have removed the edge between the vertices 1 and 2
shown as below:
The sum of the edges of the above tree is (3 + 2 + 5 + 4) : 14
o The third spanning tree is a tree in which we have removed the edge between the vertices 2 and 3
shown as below:
The sum of the edges of the above tree is (1 + 3 + 2 + 5) : 11
o The fourth spanning tree is a tree in which we have removed the edge between the vertices 3 and 4
shown as below:
The sum of the edges of the above tree is (1 + 3 + 2 + 4) : 10.
The edge cost 10 is minimum so it is a minimum spanning tree.
General properties of minimum spanning tree:
o If we remove any edge from the spanning tree, then it becomes disconnected. Therefore, we cannot
remove any edge from the spanning tree.
o If we add an edge to the spanning tree then it creates a loop. Therefore, we cannot add any edge to the
spanning tree.
o In a graph, each edge has a distinct weight, then there exists only a single and unique minimum
spanning tree. If the edge weight is not distinct, then there can be more than one minimum spanning
tree.
o A complete undirected graph can have an nn-2 number of spanning trees.(where 'n' is the number of
vertices (or nodes).)
o Every connected and undirected graph contains at least one spanning tree.

o The disconnected graph does not have any spanning tree.

o In a complete graph, we can remove maximum (e-n+1) edges to construct a spanning tree.

Let's understand the last property through an example.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
Consider the complete graph which is given below:

The number of spanning trees that can be made from the above complete graph equals to nn-2 = 44-2 =
16.

Therefore, 16 spanning trees can be created from the above graph.

The maximum number of edges that can be removed to construct a spanning tree equals to e-n+1 = 6
-4+1=3
Application of Minimum Spanning Tree
1. Consider n stations are to be linked using a communication network & laying of communication links
between any two stations involves a cost.
The ideal solution would be to extract a subgraph termed as minimum cost spanning tree.
2. Suppose you want to construct highways or railroads spanning several cities then we can use the
concept of minimum spanning trees.
3. Designing Local Area Networks.
4. Laying pipelines connecting offshore drilling sites, refineries and consumer markets.
5. Suppose you want to apply a set of houses with
o Electric Power
o Water
o Telephone lines
o Sewage lines

To reduce cost, you can connect houses with minimum cost spanning trees.
Methods of Minimum Spanning Tree

There are two methods to find Minimum Spanning Tree

1. Kruskal's Algorithm
2. Prim's Algorithm
Prepared By Kapil Dev Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
Kruskal's algorithm - This algorithm is also used to find the minimum spanning tree for a connected
weighted graph. Kruskal's algorithm also follows greedy approach, which finds an optimum solution
at every stage instead of focusing on a global optimum.
Prim's algorithm - It is a greedy algorithm that starts with an empty spanning tree. It is used to find
the minimum spanning tree from the graph. This algorithm finds the subset of edges that includes
every vertex of the graph such that the sum of the weights of the edges can be minimized.
Kruskal's Algorithm:
An algorithm to construct a Minimum Spanning Tree for a connected weighted graph. It is a Greedy
Algorithm. The Greedy Choice is to put the smallest weight edge that does not because a cycle in the
MST constructed so far.
If the graph is not linked, then it finds a Minimum Spanning Tree.
Steps for finding MST using Kruskal's Algorithm:
1. Arrange the edge of G in order of increasing weight.
2. Starting only with the vertices of G and proceeding sequentially add each edge which does
not result in a cycle, until (n - 1) edges are used.
3. EXIT.
MST- KRUSKAL (G, w)
1. A ← ∅
2. for each vertex v ∈ V [G]
3. do MAKE - SET (v)
4. sort the edges of E into non decreasing order (ascending order) by weight w
5. for each edge (u, v) ∈ E, taken in non-decreasing (ascending order) order by weight
6. do if FIND-SET (μ) ≠ if FIND-SET (v)
7. then A ← A ∪ {(u, v)}
8. UNION (u, v)
9. return A
Example of Kruskal's algorithm
Now, let's see the working of Kruskal's algorithm using an example. It will be easier to understand
Kruskal's algorithm using an example.
Suppose a weighted graph is -

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

The weight of the edges of the above graph is given in the below table –

Edge AB AC AD AE BC CD DE
Weight 1 7 10 5 3 4 2

Now, sort the edges given above in the ascending order of their weights.

Edge AB DE BC CD AE AC AD
Weight 1 2 3 4 5 7 10

Now, let's start constructing the minimum spanning tree.

Step 1 - First, add the edge AB with weight 1 to the MST.

Step 2 - Add the edge DE with weight 2 to the MST as it is not creating the cycle.

Step 3 - Add the edge BC with weight 3 to the MST, as it is not creating any cycle or loop.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 4 - Now, pick the edge CD with weight 4 to the MST, as it is not forming the cycle.

Step 5 - After that, pick the edge AE with weight 5. Including this edge will create the cycle, so
discard it.
Step 6 - Pick the edge AC with weight 7. Including this edge will create the cycle, so discard it.
Step 7 - Pick the edge AD with weight 10. Including this edge will also create the cycle, so discard
it.
So, the final minimum spanning tree obtained from the given weighted graph by using Kruskal's
algorithm is -

The cost of the MST is = AB + DE + BC + CD = 1 + 2 + 3 + 4 = 10.

Now, the number of edges in the above tree equals the number of vertices minus 1. So, the
algorithm stops here.
Prim's Algorithm (Minimum Spanning Tree)
Prim's Algorithm is a greedy algorithm that is used to find the minimum spanning tree from a
graph. Prim's algorithm finds the subset of edges that includes every vertex of the graph such
that the sum of the weights of the edges can be minimized.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
Prim's algorithm starts with the single node and explores all the adjacent nodes with all the
connecting edges at every step. The edges with the minimal weights causing no cycles in the
graph got selected.
How does the prim's algorithm work?
Prim's algorithm is a greedy algorithm that starts from one vertex and continue to add the edges
with the smallest weight until the goal is reached. The steps to implement the prim's algorithm
are given as follows -
o First, we have to initialize an MST with the randomly chosen vertex.
o Now, we have to find all the edges that connect the tree in the above step with the new
vertices. From the edges found, select the minimum edge and add it to the tree.
o Repeat step 2 until the minimum spanning tree is formed.
The applications of prim's algorithm are -
o Prim's algorithm can be used in network designing.
o It can be used to make network cycles.
o It can also be used to lay down electrical wiring cables.

Example of prim's algorithm

Now, let's see the working of prim's algorithm using an example. It will be easier to understand the
prim's algorithm using an example.
Suppose, a weighted graph is -

Step 1 - First, we have to choose a vertex from the above graph. Let's choose B.

Step 2 - Now, we have to choose and add the shortest edge from vertex B. There are two edges
from vertex B that are B to C with weight 10 and edge B to D with weight 4. Among the edges, the
edge BD has the minimum weight. So, add it to the MST.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 3 - Now, again, choose the edge with the minimum weight among all the other edges. In this
case, the edges DE and CD are such edges. Add them to MST and explore the adjacent of C, i.e., E
and A. So, select the edge DE and add it to the MST.

Step 4 - Now, select the edge CD, and add it to the MST.

Step 5 - Now, choose the edge CA. Here, we cannot select the edge CE as it would create a cycle to
the graph. So, choose the edge CA and add it to the MST.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
So, the graph produced in step 5 is the minimum spanning tree of the given graph. The cost of the
MST is given below -
Cost of MST = 4 + 2 + 1 + 3 = 10 units.

Algorithm
1. Step 1: Select a starting vertex
2. Step 2: Repeat Steps 3 and 4 until there are fringe vertices
3. Step 3: Select an edge 'e' connecting the tree vertex and fringe vertex that has minimum weig
ht
4. Step 4: Add the selected edge and the vertex to the minimum spanning tree T
5. [END OF LOOP]
6. Step 5: EXIT
Examples 2: 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}

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
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}

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
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

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Huffman Codes
o (i) Data can be encoded efficiently using Huffman Codes.

o (ii) It is a widely used and beneficial technique for compressing data.

o (iii) Huffman's greedy algorithm uses a table of the frequencies of occurrences of each character to
build up an optimal way of representing each character as a binary string.

Suppose we have 105 characters in a data file. Normal Storage: 8 bits per character (ASCII) - 8 x
105 bits in a file. But we want to compress the file and save it compactly. Suppose only six characters
appear in the file:

How can we represent the data in a Compact way?

(i) Fixed length Code: Each letter represented by an equal number of bits. With a fixed length code,
at least 3 bits per character:

For example:
a 000

b 001

c 010

d 011

e 100

f 101

For a file with 105 characters, we need 3 x 105 bits.

(ii) A variable-length code: It can do considerably better than a fixed-length code, by giving many
characters short code words and infrequent character long codewords.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
For example:
a 0

b 101

c 100

d 111

e 1101

f 1100
Number of bits = (45 x 1 + 13 x 3 + 12 x 3 + 16 x 3 + 9 x 4 + 5 x 4) x 1000
= 2.24 x 105bits
Thus, 224,000 bits to represent the file, a saving of approximately 25%.This is an optimal character
code for this file.

Prefix Codes:
The prefixes of an encoding of one character must not be equal to complete encoding of another
character, e.g., 1100 and 11001 are not valid codes because 1100 is a prefix of some other code word
is called prefix codes.
Prefix codes are desirable because they clarify encoding and decoding. Encoding is always simple
for any binary character code; we concatenate the code words describing each character of the file.
Decoding is also quite comfortable with a prefix code. Since no codeword is a prefix of any other,
the codeword that starts with an encoded data is unambiguous.

Greedy Algorithm for constructing a Huffman Code:

Huffman invented a greedy algorithm that creates an optimal prefix code called a Huffman Code.

The algorithm builds the tree T analogous to the optimal code in a bottom-up manner. It starts with
a set of |C| leaves (C is the number of characters) and performs |C| - 1 'merging' operations to create
Prepared By Kapil Dev Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
the final tree. In the Huffman algorithm 'n' denotes the quantity of a set of characters, z indicates the
parent node, and x & y are the left & right child of z respectively.
Huffman Coding Algorithm
Data may be compressed using the Huffman Coding technique to become smaller without losing
any of its information. After David Huffman, who created it in the beginning? Data that contains
frequently repeated characters is typically compressed using Huffman coding.
A well-known Greedy algorithm is Huffman Coding. The size of code allocated to a character relies
on the frequency of the character, which is why it is referred to be a greedy algorithm. The short-
length variable code is assigned to the character with the highest frequency, and vice versa for
characters with lower frequencies. It employs a variable-length encoding, which means that it gives
each character in the provided data stream a different variable-length code.

Prefix Rule
Essentially, this rule states that the code that is allocated to a character shall not be another code's
prefix. If this rule is broken, various ambiguities may appear when decoding the Huffman tree that
has been created.
Let's look at an illustration of this rule to better comprehend it: For each character, a code is
provided, such as:
1. a-0
2. b-1
3. c - 01
Assuming that the produced bit stream is 001, the code may be expressed as follows when decoded:
0 0 1 = aab
0 01 = ac
What is the Huffman Coding process?
The Huffman Code is obtained for each distinct character in primarily two steps:
o Create a Huffman Tree first using only the unique characters in the data stream provided.
o Second, we must proceed through the constructed Huffman Tree, assign codes to the
characters, and then use those codes to decode the provided text.
Steps to Take in Huffman Coding
The steps used to construct the Huffman tree using the characters provided
1. Input:
2. string str = "abbcdbccdaabbeeebeab"
If Huffman Coding is employed in this case for data compression, the following information must
be determined for decoding:
o For each character, the Huffman Code
o Huffman-encoded message length (in bits), average code length
o Utilizing the formulas covered below, the final two of them are discovered.

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

How Can a Huffman Tree Be Constructed from Input Characters?

The frequency of each character in the provided string must first be determined.
Character Frequency
a 4
b 7
c 3
d 2
e 4
1. Sort the characters by frequency, ascending. These are kept in a Q/min-heap priority queue.
2. For each distinct character and its frequency in the data stream, create a leaf node.
3. Remove the two nodes with the two lowest frequencies from the nodes, and the new root of the tree
is created using the sum of these frequencies.
o Make the first extracted node its left child and the second extracted node its right child while
extracting the nodes with the lowest frequency from the min-heap.
o To the min-heap, add this node.
o Since the left side of the root should always contain the minimum frequency.
4. Repeat steps 3 and 4 until there is only one node left on the heap, or all characters are represented by
nodes in the tree. The tree is finished when just the root node remains.

Algorithm of Huffman Code

Huffman (C)
1. n=|C|
2. Q ← C
3. for i=1 to n-1
4. do
5. z= allocate-Node ()
6. x= left[z]=Extract-Min(Q)
7. y= right[z] =Extract-Min(Q)
8. f [z]=f[x]+f[y]
9. Insert (Q, z)
10. return Extract-Min (Q)
Examples of Huffman Coding :
Let's use an illustration to explain the algorithm:

Algorithm for Huffman Coding

Step 1: Build a min-heap in which each node represents the root of a tree with a single node and
holds 5 (the number of unique characters from the provided stream of data).
Prepared By Kapil Dev Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 2: Obtain two minimum frequency nodes from the min heap in step two. Add a third internal
node, frequency 2 + 3 = 5, which is created by joining the two extracted nodes.

o Now, there are 4 nodes in the min-heap, 3 of which are the roots of trees with a single element each,
and 1 of which is the root of a tree with two elements.
Step 3: Get the two minimum frequency nodes from the heap in a similar manner in step three.
Additionally, add a new internal node formed by joining the two extracted nodes; its frequency in
the tree should be 4 + 4 = 8.

o Now that the minimum heap has three nodes, one node serves as the root of trees with a single element
and two heap nodes serve as the root of trees with multiple nodes.
Step 4: Get the two minimum frequency nodes in step four. Additionally, add a new internal node
formed by joining the two extracted nodes; its frequency in the tree should be 5 + 7 = 12.
o When creating a Huffman tree, we must ensure that the minimum value is always on the left side and
that the second value is always on the right side. Currently, the image below shows the tree that has
formed:

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 5: Get the following two minimum frequency nodes in step 5. Additionally, add a new internal
node formed by joining the two extracted nodes; its frequency in the tree should be 12 + 8 = 20.
Continue until all of the distinct characters have been added to the tree. The Huffman tree created for
the specified cast of characters is shown in the above image.
Now, for each non-leaf node, assign 0 to the left edge and 1 to the right edge to create the code for
each letter.
Rules to follow for determining edge weights:
o We should give the right edges weight 1 if you give the left edges weight 0.
o If the left edges are given weight 1, the right edges must be given weight 0.
o Any of the two aforementioned conventions may be used.
o However, follow the same protocol when decoding the tree as well.
Following the weighting, the modified tree is displayed as follows:

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Understanding the Code

o We must go through the Huffman tree until we reach the leaf node, where the element is present, in
order to decode the Huffman code for each character from the resulting Huffman tree.
o The weights across the nodes must be recorded during traversal and allocated to the items located at
the specific leaf node.
o The following example will help to further illustrate what we mean:
o To obtain the code for each character in the picture above, we must walk the entire tree (until all leaf
nodes are covered).
o As a result, the tree that has been created is used to decode the codes for each node. Below is a list of
the codes for each character:
o
Character Frequency/count Code

a 4 01
b 7 11
c 3 101
d 2 100
e 4 00

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026
Average Code Length (L) :

Where 𝑓𝑖 = frequency,
𝑙𝑖 =code length

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Example: Find an optimal Huffman Code for the following set of frequencies
a: 50 b: 25 c: 15 d: 40 e: 75

Solution:

Again for i=2

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Example: 3
 Huffman’s greedy algorithm uses a table giving how often each character occurs
(i.e., its frequency) to build up an optimal way of representing each character as a binary
string.
 Suppose we have a 100,000-character data file that we wish to store compactly.
 We observe that the characters in the file occur with the frequencies given by following table.
 That is, only 6 different characters appear, and the character a occurs 45,000 times.

Characters a b c d e f
Frequency (in
thousand) 45 13 12 16 9 5

Solution:
 The steps of Huffman’s algorithm for the frequencies given above as step no. 1 to 6.
 Each step shows the contents of the queue sorted into increasing order by frequency.
 At each step, the two trees with lowest frequencies are merged.
 Leaves are shown as rectangles containing a character and its frequency.
 Internal nodes are shown as circles containing the sum of the frequencies of their children.
 An edge connecting an internal node with its children is labeled 0 if it is an edge to a left
child and 1 if it is an edge to a right child.
 The code-word for a letter is the sequence of labels on the edges connecting the root to the leaf

Prepared By Kapil Dev Raghuwanshi

 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

for that letter.

Step-1: Arrange elements in ascending order:-

Step-2: Step-3:

Step-4: Step-5:

Step-6:

Frequency (in a b c d e f
thousand) 45 13 12 16 9 5
Huffman code-
0 101 100 111 1101 1100
word

27
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Single source shortest Paths: Dijkstra’s algorithm

Single Source Shortest Paths (SSSP) :
The Single Source Shortest Path problem (SSSP) is a classic graph problem where we
are given a weighted, directed or undirected graph G(V, E) and a source vertex s.
The goal is to determine the shortest path (minimum cost) from s to every other vertex v
∈ V in the graph.
Types of Graphs
1. Weighted Graph – Each edge (u, v) has an associated weight or cost w(u, v).
2. Directed Graph – Edges have a direction (u → v).
3. Undirected Graph – Edges are bidirectional.
4. Graphs with Negative Weights – Some edges may have negative weights.
3. Shortest Path Concepts
 Path Length: Sum of edge weights on a path.
 Shortest Path: Minimum path length from source s to destination v.
 Relaxation: A process that improves the shortest path estimate by checking if a
better path exists through another vertex.
Relaxation Formula:
if dist[v] > dist[u] + w(u, v)
then dist[v] = dist[u] + w(u, v)
What is Edge Relaxation?

Consider the edge (a,b) in the following graph-

Here, d[a] and d[b] denotes the shortest path estimate for vertices a and b respectively
from the source vertex ‘S’.
Now,
If d[a] + w < d[b]
then d[b] = d[a] + w and Π[b] = a
This is called as edge relaxation.

28
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Dijkstra Algorithm
Dijkstra algorithm is a single-source shortest path algorithm. Here, single-source means
that only one source is given, and we have to find the shortest path from the source to all
the nodes.

dist[S] ← 0 // The distance to source vertex is set to 0

Π[S] ← NIL // The predecessor of source vertex is set as NIL

for all v ∈ V - {S} // For all other vertices

do dist[v] ← ∞ // All other distances are set to ∞

Π[v] ← NIL // The predecessor of all other vertices is set as NIL

S ← ∅ // The set of vertices that have been visited 'S' is initially empty

Q ← V // The queue 'Q' initially contains all the vertices

while Q ≠ ∅ // While loop executes till the queue is not empty

do u ← mindistance (Q, dist) // A vertex from Q with the least distance is selected

S ← S ∪ {u} // Vertex 'u' is added to 'S' list of vertices that have been visited

for all v ∈ neighbors[u] // For all the neighboring vertices of vertex 'u'

do if dist[v] > dist[u] + w(u,v) // if any new shortest path is discovered

then dist[v] ← dist[u] + w(u,v) // The new value of the shortest path is selected

return dist

Let's understand the working of Dijkstra's algorithm. Consider the below graph.

29
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

First, we have to consider any vertex as a source vertex. Suppose we consider vertex 0 as
a source vertex.

Here we assume that 0 as a source vertex, and distance to all the other vertices is infinity.
Initially, we do not know the distances. First, we will find out the vertices which are
directly connected to the vertex 0. As we can observe in the above graph that two vertices
are directly connected to vertex 0.

Let's assume that the vertex 0 is represented by 'x' and the vertex 1 is represented by 'y'.
The distance between the vertices can be calculated by using the below formula:

d(x, y) = d(x) + c(x, y) < d(y)

= (0 + 4) < ∞

=4<∞
30
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Since 4<∞ so we will update d(v) from ∞ to 4.

Therefore, we come to the conclusion that the formula for calculating the distance
between the vertices:

{if( d(u) + c(u, v) < d(v))

d(v) = d(u) +c(u, v) }

Now we consider vertex 0 same as 'x' and vertex 4 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (0 + 8) < ∞

=8<∞

Therefore, the value of d(y) is 8. We replace the infinity value of vertices 1 and 4 with
the values 4 and 8 respectively. Now, we have found the shortest path from the vertex 0
to 1 and 0 to 4. Therefore, vertex 0 is selected. Now, we will compare all the vertices
except the vertex 0. Since vertex 1 has the lowest value, i.e., 4; therefore, vertex 1 is
selected.

Since vertex 1 is selected, so we consider the path from 1 to 2, and 1 to 4. We will not
consider the path from 1 to 0 as the vertex 0 is already selected.

First, we calculate the distance between the vertex 1 and 2. Consider the vertex 1 as 'x',
and the vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (4 + 8) < ∞

= 12 < ∞

Since 12<∞ so we will update d(2) from ∞ to 12.

Now, we calculate the distance between the vertex 1 and vertex 4. Consider the vertex 1
as 'x' and the vertex 4 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (4 + 11) < 8

= 15 < 8

Since 15 is not less than 8, we will not update the value d(4) from 8 to 12.
31
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Till now, two nodes have been selected, i.e., 0 and 1. Now we have to compare the nodes
except the node 0 and 1. The node 4 has the minimum distance, i.e., 8. Therefore, vertex
4 is selected.

Since vertex 4 is selected, so we will consider all the direct paths from the vertex 4. The
direct paths from vertex 4 are 4 to 0, 4 to 1, 4 to 8, and 4 to 5. Since the vertices 0 and 1
have already been selected so we will not consider the vertices 0 and 1. We will consider
only two vertices, i.e., 8 and 5.

First, we consider the vertex 8. First, we calculate the distance between the vertex 4 and
8. Consider the vertex 4 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 7) < ∞

= 15 < ∞

Since 15 is less than the infinity so we update d(8) from infinity to 15.

Now, we consider the vertex 5. First, we calculate the distance between the vertex 4 and
5. Consider the vertex 4 as 'x', and the vertex 5 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (8 + 1) < ∞

=9<∞

Since 5 is less than the infinity, we update d(5) from infinity to 9.

Till now, three nodes have been selected, i.e., 0, 1, and 4. Now we have to compare the
nodes except the nodes 0, 1 and 4. The node 5 has the minimum value, i.e., 9. Therefore,
vertex 5 is selected.

Since the vertex 5 is selected, so we will consider all the direct paths from vertex 5. The
direct paths from vertex 5 are 5 to 8, and 5 to 6.

First, we consider the vertex 8. First, we calculate the distance between the vertex 5 and
8. Consider the vertex 5 as 'x', and the vertex 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (9 + 15) < 15

= 24 < 15

32
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Since 24 is not less than 15 so we will not update the value d(8) from 15 to 24.

Now, we consider the vertex 6. First, we calculate the distance between the vertex 5 and
6. Consider the vertex 5 as 'x', and the vertex 6 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (9 + 2) < ∞

= 11 < ∞

Since 11 is less than infinity, we update d(6) from infinity to 11.

Till now, nodes 0, 1, 4 and 5 have been selected. We will compare the nodes except the
selected nodes. The node 6 has the lowest value as compared to other nodes. Therefore,
vertex 6 is selected.

Since vertex 6 is selected, we consider all the direct paths from vertex 6. The direct paths
from vertex 6 are 6 to 2, 6 to 3, and 6 to 7.

First, we consider the vertex 2. Consider the vertex 6 as 'x', and the vertex 2 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 4) < 12

= 15 < 12

Since 15 is not less than 12, we will not update d(2) from 12 to 15

Now we consider the vertex 3. Consider the vertex 6 as 'x', and the vertex 3 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 14) < ∞

= 25 < ∞

Since 25 is less than ∞, so we will update d(3) from ∞ to 25.

Now we consider the vertex 7. Consider the vertex 6 as 'x', and the vertex 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (11 + 10) < ∞

= 22 < ∞
33
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Since 22 is less than ∞ so, we will update d(7) from ∞ to 22.

Till now, nodes 0, 1, 4, 5, and 6 have been selected. Now we have to compare all the
unvisited nodes, i.e., 2, 3, 7, and 8. Since node 2 has the minimum value, i.e., 12 among
all the other unvisited nodes. Therefore, node 2 is selected.

Since node 2 is selected, so we consider all the direct paths from node 2. The direct paths
from node 2 are 2 to 8, 2 to 6, and 2 to 3.

First, we consider the vertex 8. Consider the vertex 2 as 'x' and 8 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 2) < 15

= 14 < 15

Since 14 is less than 15, we will update d(8) from 15 to 14.

Now, we consider the vertex 6. Consider the vertex 2 as 'x' and 6 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 4) < 11

= 16 < 11

Since 16 is not less than 11 so we will not update d(6) from 11 to 16.

Now, we consider the vertex 3. Consider the vertex 2 as 'x' and 3 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (12 + 7) < 25

= 19 < 25

Since 19 is less than 25, we will update d(3) from 25 to 19.

Till now, nodes 0, 1, 2, 4, 5, and 6 have been selected. We compare all the unvisited
nodes, i.e., 3, 7, and 8. Among nodes 3, 7, and 8, node 8 has the minimum value. The
nodes which are directly connected to node 8 are 2, 4, and 5. Since all the directly
connected nodes are selected so we will not consider any node for the updation.

The unvisited nodes are 3 and 7. Among the nodes 3 and 7, node 3 has the minimum
value, i.e., 19. Therefore, the node 3 is selected. The nodes which are directly connected

34
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

to the node 3 are 2, 6, and 7. Since the nodes 2 and 6 have been selected so we will
consider these two nodes.

Now, we consider the vertex 7. Consider the vertex 3 as 'x' and 7 as 'y'.

d(x, y) = d(x) + c(x, y) < d(y)

= (19 + 9) < 21

= 28 < 21

Since 28 is not less than 21, so we will not update d(7) from 28 to 21.
Problem-

Using Dijkstra’s Algorithm, find the shortest distance from source vertex ‘S’ to remaining
vertices in the following graph-

Also, write the order in which the vertices are visited.

Solution-

Step-01:

The following two sets are created-

 Unvisited set : {S , a , b , c , d , e}
 Visited set : { }

35
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step-02:

The two variables Π and d are created for each vertex and initialized as-
 Π[S] = Π[a] = Π[b] = Π[c] = Π[d] = Π[e] = NIL
 d[S] = 0
 d[a] = d[b] = d[c] = d[d] = d[e] = ∞

Step-03:

 Vertex ‘S’ is chosen.

 This is because shortest path estimate for vertex ‘S’ is least.
 The outgoing edges of vertex ‘S’ are relaxed.

Before Edge Relaxation-

Now,
 d[S] + 1 = 0 + 1 = 1 < ∞
∴ d[a] = 1 and Π[a] = S
 d[S] + 5 = 0 + 5 = 5 < ∞
∴ d[b] = 5 and Π[b] = S

After edge relaxation, our shortest path tree is-

Now, the sets are updated as-

 Unvisited set : {a , b , c , d , e}
 Visited set : {S}

Step-04:

36
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

 Vertex ‘a’ is chosen.

 This is because shortest path estimate for vertex ‘a’ is least.
 The outgoing edges of vertex ‘a’ are relaxed.

Before Edge Relaxation-

Now,
 d[a] + 2 = 1 + 2 = 3 < ∞
∴ d[c] = 3 and Π[c] = a
 d[a] + 1 = 1 + 1 = 2 < ∞
∴ d[d] = 2 and Π[d] = a
 d[b] + 2 = 1 + 2 = 3 < 5
∴ d[b] = 3 and Π[b] = a

After edge relaxation, our shortest path tree is-

37
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Now, the sets are updated as-

 Unvisited set : {b , c , d , e}
 Visited set : {S , a}

Step-05:

 Vertex ‘d’ is chosen.

 This is because shortest path estimate for vertex ‘d’ is least.
 The outgoing edges of vertex ‘d’ are relaxed.

Before Edge Relaxation-

Now,
 d[d] + 2 = 2 + 2 = 4 < ∞
∴ d[e] = 4 and Π[e] = d

After edge relaxation, our shortest path tree is-

Now, the sets are

updated as-
 Unvisited set : {b , c , e}
 Visited set : {S , a , d}

38
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step-06:

 Vertex ‘b’ is chosen.

 This is because shortest path estimate for vertex ‘b’ is least.
 Vertex ‘c’ may also be chosen since for both the vertices, shortest path estimate is least.
 The outgoing edges of vertex ‘b’ are relaxed.
Before Edge Relaxation-

Now,
 d[b] + 2 = 3 + 2 = 5 > 2
∴ No change

After edge relaxation, our shortest path tree remains the same as in Step-05.
Now, the sets are updated as-
 Unvisited set : {c , e}
 Visited set : {S , a , d , b}

Step-07:

 Vertex ‘c’ is chosen.

 This is because shortest path estimate for vertex ‘c’ is least.
 The outgoing edges of vertex ‘c’ are relaxed.

Before Edge Relaxation-

Now,
 d[c] + 1 = 3 + 1 = 4 = 4
∴ No change

After edge relaxation, our shortest path tree remains the same as in Step-05.
39
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Now, the sets are updated as-

 Unvisited set : {e}
 Visited set : {S , a , d , b , c}

Step-08:

 Vertex ‘e’ is chosen.

 This is because shortest path estimate for vertex ‘e’ is least.
 The outgoing edges of vertex ‘e’ are relaxed.
 There are no outgoing edges for vertex ‘e’.
 So, our shortest path tree remains the same as in Step-05.

Now, the sets are updated as-

 Unvisited set : { }
 Visited set : {S , a , d , b , c , e}

Now,
 All vertices of the graph are processed.
 Our final shortest path tree is as shown below.
 It represents the shortest path from source vertex ‘S’ to all other remaining vertices.

The order in which all the vertices are processed is :

S , a , d , b , c , e.

40
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Knapsack Problem-

 A knapsack (kind of shoulder bag) with limited weight capacity.

 Few items each having some weight and value.

The problem states-

Which items should be placed into the knapsack such that-
 The value or profit obtained by putting the items into the knapsack is maximum.
 And the weight limit of the knapsack does not exceed.

Knapsack Problem Variants-

Knapsack problem has the following two variants-

41
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

1. Fractional Knapsack Problem

2. 0/1 Knapsack Problem

Fractional Knapsack Problem-

In Fractional Knapsack Problem,

 As the name suggests, items are divisible here.
 We can even put the fraction of any item into the knapsack if taking the complete
item is not possible.

The fractional knapsack problem is also one of the techniques which are used to solve the
knapsack problem. In fractional knapsack, the items are broken in order to maximize the
profit. The problem in which we break the item is known as a Fractional knapsack
problem.

This problem can be solved with the help of using two techniques:

o Brute-force approach: The brute-force approach tries all the possible solutions with
all the different fractions but it is a time-consuming approach.

o Greedy approach: In Greedy approach, we calculate the ratio of profit/weight, and

accordingly, we will select the item. The item with the highest ratio would be selected
first.

Fractional Knapsack Problem Using Greedy Method-

Fractional knapsack problem is solved using greedy method in the following steps-

Step-01:

For each item, compute its value / weight ratio.

Step-02:

Arrange all the items in decreasing order of their value / weight ratio.

Step-03:

Start putting the items into the knapsack beginning from the item with the highest ratio.

Put as many items as you can into the knapsack.

Algorithm of Fractional Knapsack

42
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Two arrays: v (values of items) and w (weights of items).

An integer W representing the weight capacity of the knapsack.

1. Initialize an array p to store the value-to-weight ratios for each item.

2. For each item i from 1 to the size of the arrays v and w

=>Calculate the value-to-weight ratio: p[i] = v[i] / w[i].

3. Sort the array p in non-ascending order.

4. Initialize a variable i to 1

5. While the knapsack’s weight capacity W is greater than 0

6. Do the following

 Calculate the amount to add to the knapsack

 amount = min(W, w[i])

 Reduce the knapsack’s weight capacity: W = W – amount.

 Move to the next item: i = i + 1.

7. Return the array, which specifies the fraction of each item to include in the knapsack
while maximizing the total value.

Time Complexity-

The main time taking step is the sorting of all items in decreasing order of their value /
weight ratio.

 If the items are already arranged in the required order, then while loop takes O(n) time.

 The average time complexity of Quick Sort is O(nlogn).

 Therefore, total time taken including the sort is O(nlogn).

Space Complexity of Fractional Knapsack problem
The space complexity for this approach is O(n) since you need an additional space
array of size ‘n’ to store the value-to-weight ratios of each item.

Advantages of Fractional Knapsack problem

1. Simplicity – The Fractional Knapsack Algorithm is easy to understand and

implement.

2. Efficiency – It provides a relatively good solution quickly, making it suitable for

large datasets.
43
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

3. Flexibility – It allows fractions of items to be included, providing a realistic

approach to real-world scenarios..

Disadvantages of Fractional Knapsack problem

The Fractional Knapsack problem assumes that items can be divided into fractions, which
may not always be practical or realistic. 15 kg gold powder is hard to get in the above
example.

Applications of Fractional Knapsack problem

The Fractional Knapsack Algorithm finds applications in various domains, including:

1. Determining the best investments to maximize returns within a budget.

2. Optimizing the selection of materials for product assembly.

3. Allocating resources efficiently in projects or operations.

4. Farmers can apply the algorithm to optimize crop planting and resource allocation for
maximum yield and profit.

5. Selecting cargo for efficient shipping or airline baggage allocation.

PRACTICE PROBLEM BASED ON FRACTIONAL KNAPSACK PROBLEM-
Problem-
For the given set of items and knapsack capacity = 60 kg, find the optimal solution for
the fractional knapsack problem making use of greedy approach.

Item Weight Value

1 5 30
2 10 40
3 15 45
4 22 77
5 25 90
OR
44
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Find the optimal solution for the fractional knapsack problem making use of greedy
approach. Consider-
n=5
w = 60 kg
(w1, w2, w3, w4, w5) = (5, 10, 15, 22, 25)
(b1, b2, b3, b4, b5) = (30, 40, 45, 77, 90)
OR
A thief enters a house for robbing it. He can carry a maximal weight of 60 kg into his bag.
There are 5 items in the house with the following weights and values. What items should
thief take if he can even take the fraction of any item with him?

Item Weight Value

1 5 30
2 10 40
3 15 45
4 22 77
5 25 90
Solution-
Step-01:
Compute the value / weight ratio for each item-

Items Weight Value Ratio

1 5 30 6
2 10 40 4
3 15 45 3
4 22 77 3.5
5 25 90 3.6

45
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step-02:

Sort all the items in decreasing order of their value / weight ratio-

I1 I2 I5 I4 I3
6 4 3.6 3.5 3
Step-03:
Start filling the knapsack by putting the items into it one by one.

Knapsack Weight Items in Knapsack Cost

60 Ø 0

55 I1 30

45 I1, I2 70

20 I1, I2, I5 160

Now,
 Knapsack weight left to be filled is 20 kg but item-4 has a weight of 22 kg.
 Since in fractional knapsack problem, even the fraction of any item can be taken.
 So, knapsack will contain the following items-
< I1 , I2 , I5 , (20/22) I4 >

Total cost of the knapsack

= 160 + (20/27) x 77
= 160 + 70
= 230 units
Example 2 :
Problem: Find the optimal solution for knapsack problem (fraction) where knapsack
capacity = 28, P = {9, 5, 2, 7, 6, 16, 3} and w = {2, 5, 6, 11, 1, 9, 1}.
Solution:
Arrange items in decreasing order of profit to weight ratio

Item Profit pi Weight wi Ratio vi/wi

I5 6 1 6

46
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

I1 9 2 4.5
I7 3 1 3
I6 16 9 1.78
I2 5 5 1
I4 7 11 0.64
I3 2 6 0.33

Initialize, Weight = 0, P = 0, M = 28, S = { }

Where S is the solution set, P and W is profit and weight of included items, respectively.
M is the capacity of the knapsack.
Iteration 1
(Weight + w5) ≤ M, so select I5
So, S = { I5 }, Weight = 0 + 1 = 1, P = 0 + 6= 6
Iteration 2
(Weight + w1) ≤ M, so select I1
So, S = {I5 ,I1 }, Weight = 1 + 2 = 3, P = 6 + 9= 15
Iteration 3
(Weight + w7) ≤ M, so select I7
So, S = {I5, I1, I7 }, Weight = 3 + 1 = 4, P = 15 + 3= 18
Iteration 4
(Weight + w6) ≤ M, so select I6
So, S = {I5, I1, I7, I6 }, Weight = 4 + 9 = 13, P = 18 + 16= 34
Iteration 5
(Weight + w2) ≤ M, so select I2
So, S = {I5, I1, I7, I6, I2 }, Weight = 13 + 5 = 18, P = 34 + 5= 39
Iteration 6
(Weight + w4) > M, So I4 must be broken down into two parts x and y such that x =
capacity left in knapsack and y = I4 – x.
Available knapsack capacity is 10 units. So we can select only (28 – 18) / 11 = 0.91 unit
of I4.
So S = {I5, I1, I7, I6, I2, 0.91 * I4 }, Weight = 18 + 0.91*11 = 28, P = 39 + 0.91 * 7= 45.37

Example 3
Suppose you have a knapsack with a weight capacity (w) of 15 Kgs and the following
items:

47
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Let’s use the Fractional Knapsack Algorithm to determine the best combination of items
for the knapsack.
 Calculate value-to-weight ratios

 Sort items by value-to-weight ratio in descending order: C, B, A, D, E.

 Initialize the knapsack with a current weight of 0 and a total value of 0.

 Start with item C (value 50, weight 2)

 It can be fully added to the knapsack, and the knapsack’s current weight
becomes 2 Kgs.
 The total value is updated to 50.
 Knapsack remaining weight = 15 – 2 = 13 Kgs.
 Move to item B (value 150, weight 7).
 It can be fully added to the knapsack, and the knapsack’s current weight
becomes 2 + 7 = 9 Kgs.
 The total value is updated to 50 + 150 = 200.
 Knapsack remaining weight = 13 – 7 = 6 Kgs
 Move to item A (value 100, weight 5)
 It can be fully added to the knapsack, and the knapsack’s current weight
becomes 9 + 5 = 14 Kgs.
 The total value is updated to 200 + 100 = 300.
 Knapsack remaining weight = 6 – 5 = 1 Kgs.
 Move to item D (value 200, weight 10)
48
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

 It cannot be fully added to the knapsack, but a fraction of 1 kg is added and the
knapsack’s current weight becomes 14 + 1 = 15 Kgs.
 1 kg value = 200/10 = 20
 The total value is updated to 300 + 20 = 320.
 Knapsack remaining weight = 1 – 1 = 0 Kg
 The knapsack is now full, and the total value is 320.

Optimal Merge Pattern: A Greedy Algorithm Approach

The Optimal Merge Pattern (OMP) problem deals with minimizing the total
computational cost of merging multiple sorted files (or data lists) into a single sorted
file. It is a classic Greedy Algorithm problem where the optimal solution is built step
by step by always choosing the best (minimum-cost) pair to merge at each stage.

Optimal merge pattern is a pattern that relates to the merging of two or more sorted
files in a single sorted file. This type of merging can be done by the two-way merging
method.
If we have two sorted files containing n and m records respectively then they could be
merged together, to obtain one sorted file in time O (n+m).

There are many ways in which pairwise merge can be done to get a single sorted file.
Different pairings require a different amount of computing [Link] main thing is to
pairwise merge the n sorted files so that the number of comparisons will be less.
The formula of external merging cost is:

Where, f (i) represents the number of records in each file and d (i) represents the depth.
Problem Definition
Given n files with sizes:
f1, f2, f3, ..., fn
Each time we merge two files, say A and B, the cost of merging is:
Cost = size(𝐴) + size(𝐵)

49
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

After merging, the new file (of size A+B) replaces the two original files, and the process
continues until only one file remains.
The objective is to minimize the total cost of all merges.

Pseudo code for optimal merge pattern

Algorithm Tree(n)
//list is a global list of n single node
{
For i=1 to i= n-1 do
{
// get a new tree node
Pt: new treenode;
// merge two trees with smallest length
(Pt = lchild) = least(list);
(Pt = rchild) = least(list);
(Pt =weight) = ((Pt = lchild) = weight) = ((Pt = rchild) = weight);
Insert (list , Pt);
}
// tree left in list
Return least(list);
}

Time Complexity
 Insertion and extraction from a min-heap take 𝑂(log⁡𝑛)time.
 For n files, there are n-1 merge operations.
Total Time Complexity = 𝑂(𝑛log⁡𝑛)
Applications
 Data compression (Huffman Coding)
 Optimal merge of sorted lists or database files
 External sorting (multi-way merge sort)

Optimal merge pattern example

Given a set of unsorted files: 5, 3, 2, 7, 9, 13
Solution :
Now, arrange these elements in ascending order: 2, 3, 5, 7, 9, 13
After this, pick two smallest numbers and repeat this until we left with only one number.

Now follow following steps:

50
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 1: Insert 2, 3

Step 2:

Step 3: Insert 5

Step 4: Insert 13

Step 5: Insert 7 and 9

Step 6:

51
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

So, The merging cost = 5 + 10 + 16 + 23 + 39 = 93

Formula for External Merge Cost
For an Optimal Merge Pattern (OMP) or External Merge Tree,
the total cost is calculated as:
2*4+3*4+3*5+7*2+9*2+13*2
Now add them all:
8 + 12 + 15 + 14 + 18 + 26 = 93

Examples 2 :
Let us consider the given files, f1, f2, f3, f4 and f5 with 20, 30, 10, 5 and 30 number of elements
respectively.
If merge operations are performed according to the provided sequence, then
M1 = merge f1 and f2 => 20 + 30 = 50
M2 = merge M1 and f3 => 50 + 10 = 60
M3 = merge M2 and f4 => 60 + 5 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Hence, the total number of operations is
50 + 60 + 65 + 95 = 270
Now, the question arises is there any better solution?
Sorting the numbers according to their size in an ascending order, we get the following sequence −
f4, f3, f1, f2, f5
Hence, merge operations can be performed on this sequence
M1 = merge f4 and f3 => 5 + 10 = 15
M2 = merge M1 and f1 => 15 + 20 = 35
M3 = merge M2 and f2 => 35 + 30 = 65
M4 = merge M3 and f5 => 65 + 30 = 95
Therefore, the total number of operations is
15 + 35 + 65 + 95 = 210
Obviously, this is better than the previous one.
52
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

In this context, we are now going to solve the problem using this algorithm.

Initial Set

Step 1

Step 2

Step 3

Step 4

Hence, the solution takes 15 + 35 + 60 + 95 = 205 number of comparisons.

53
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Job Sequencing with Deadlines:

The Job Sequencing with Deadlines problem aims to maximize total profit when given a set of
jobs, each with a deadline and profit, where only one job can be executed at a time.
It is an optimization problem commonly solved using a Greedy Algorithm approach.
The sequencing of jobs on a single processor with deadline constraints is called as Job Sequencing
with Deadlines.
Here-
 You are given a set of jobs.
 Each job has a defined deadline and some profit associated with it.
 The profit of a job is given only when that job is completed within its deadline.
 Only one processor is available for processing all the jobs.
 Processor takes one unit of time to complete a job.

Problem Statement
You are given n jobs, each having:
 Ji → Job ID
 di → Deadline (the latest time unit by which the job must be completed)
 pi → Profit earned if the job is completed before or on its deadline
Each job takes one unit of time, and only one job can be scheduled at a time.
Goal:
Schedule the jobs so that:
 Each job is completed before or on its deadline
 The total profit is maximum
Characteristics
 Each job takes unit time
 No job can be executed after its deadline
 If multiple jobs are available at the same time, pick the most profitable one
Approach to Solution-
 A feasible solution would be a subset of jobs where each job of the subset gets completed within
its deadline.
 Value of the feasible solution would be the sum of profit of all the jobs contained in the subset.
 An optimal solution of the problem would be a feasible solution which gives the maximum
profit.

Greedy Strategy
Sort all jobs in decreasing order of profit, and assign each job to the latest available slot before
its deadline.
The greedy algorithm described below always gives an optimal solution to the job sequencing
problem-
Step-01:
 Sort all the given jobs in decreasing order of their profit.
Step-02:

 Check the value of maximum deadline.

 Draw a Gantt chart where maximum time on Gantt chart is the value of maximum deadline.
54
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step-03:

 Pick up the jobs one by one.

 Put the job on Gantt chart as far as possible from 0 ensuring that the job gets completed
before its deadline.

Algorithm
Step-by-Step (Greedy Approach):
1. Sort all jobs in decreasing order of profit.
2. Find the maximum deadline (D).
3. Create an array slots[D] to keep track of free time slots (initialized to -1).
4. For each job (in sorted order):
o Find the latest available slot before its deadline.
o If the slot is free, schedule the job there.
5. Calculate the total profit and print the job sequence.
Pseudocode

JOB_SEQUENCING(jobs[], n):
sort(jobs) by decreasing profit
max_deadline = maximum of all [Link]
create slot[1..max_deadline] and initialize to -1
total_profit = 0
for i = 1 to n:
for j = min(max_deadline, jobs[i].deadline) downto 1:
if slot[j] is empty:
slot[j] = jobs[i].id
total_profit += jobs[i].profit
break

print "Job Sequence:", slot[]

print "Total Profit:", total_profit
PRACTICE PROBLEM BASED ON JOB SEQUENCING WITH DEADLINES-

Problem-

Given the jobs, their deadlines and associated profits as shown-

Jobs J1 J2 J3 J4 J5 J6

Deadlines 5 3 3 2 4 2

Profits 200 180 190 300 120 100

Answer the following questions-

1. Write the optimal schedule that gives maximum profit.

55
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

2. Are all the jobs completed in the optimal schedule?

3. What is the maximum earned profit?
Solution-
Step-01:
Sort all the given jobs in decreasing order of their profit-
Jobs J4 J1 J3 J2 J5 J6
Deadlines 2 5 3 3 4 2
Profits 300 200 190 180 120 100

Step-02:

Value of maximum deadline = 5.

So, draw a Gantt chart with maximum time on Gantt chart = 5 units as shown-

Now,
 We take each job one by one in the order they appear in Step-01.
 We place the job on Gantt chart as far as possible from 0.
Step-03:
We take job J4.
 Since its deadline is 2, so we place it in the first empty cell before deadline 2 as-

Step-04:
We take job J1.
 Since its deadline is 5, so we place it in the first empty cell before deadline 5 as-

Step-05:
We take job J3.
 Since its deadline is 3, so we place it in the first empty cell before deadline 3 as-

56
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step-06:

 We take job J2.

 Since its deadline is 3, so we place it in the first empty cell before deadline 3.
 Since the second and third cells are already filled, so we place job J2 in the first cell as-

Step-07:

 Now, we take job J5.

 Since its deadline is 4, so we place it in the first empty cell before deadline 4 as-

Now,
 The only job left is job J6 whose deadline is 2.
 All the slots before deadline 2 are already occupied.
 Thus, job J6 can not be completed.

Now, the given questions may be answered as-

Part-01:

The optimal schedule is-

J2 , J4 , J3 , J5 , J1
This is the required order in which the jobs must be completed in order to obtain the maximum
profit.

Part-02:

 All the jobs are not completed in optimal schedule.

 This is because job J6 could not be completed within its deadline.

Part-03:

Maximum earned profit

= Sum of profit of all the jobs in optimal schedule
= Profit of job J2 + Profit of job J4 + Profit of job J3 + Profit of job J5 + Profit of job J1
= 180 + 300 + 190 + 120 + 200
= 990 units

57
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Example 2 : Find the optimal solution for the instance n=4, (P1, P2, P3, P4) =(70,12,18,35), (d1, d2, d3,
d4)=(2,1,2,1) using Job Sequencing Algorithm.

Step 1: Sort all the given jobs in decreasing order based on their profit

The maximum value for the deadlines is

***We assume that each job takes unit time to complete.
Hence we will have 2 time slots and only 2 jobs can be completed within deadline.
Step 2: Let us take Job J1. If we look at job J1 it has a deadline 2. This means that we have to complete job
J1 on or before time slot 2 in order to earn its profit. Since its deadline is 2, so we place it in the first empty
cell before deadline 2 as shown in the figure given below:

Step 3: Let us take Job J4. If we look at job J4 it has a deadline 1. This means that we have to complete job
J4 on or before time slot 1 in order to earn its profit. Since its deadline is 1, so we place it in the first empty
cell before deadline 1 as shown in the figure given below:

The optimal schedule is- J4 , [Link] is the sequence in which the jobs must be completed in order to obtain
the maximum profit.
Maximum earned profit is 35+70=105
 Example 2: Find the optimal solution for the instance n=6, (P 1, P2, P3, P4 ,P5, P6)
=(200,180,190,300,120,100), (d1, d2, d3, d4, d5, d6)=(5,3,3,2,4,2) using Job Sequencing Algorithm.

Step 1: Sort all the given jobs in decreasing order based on their profit

***The maximum value for deadlines is

***We assume that each job takes unit time to complete.
Hence we will have 5 time slots and only 5 jobs can be completed within deadline.
Step 2: Let us take Job J4. If we look at job J4 it has a deadline 2. This means that we have to
complete job J4 on or before time slot 2 in order to earn its profit. Since its deadline is 2, so we
place it in the first empty cell before deadline 2 as shown in the figure given below:

58
Prepared By Kapil Raghuwanshi
 The ICFAI University Jaipur
Design and Analysis of Algorithm
First Semester: 2025–2026

Step 3: Let us take Job J1. If we look at job J1 it has a deadline 5. This means that we have to
complete job J1 on or before time slot 5 in order to earn its profit. Since its deadline is 5, so we
place it in the first empty cell before deadline 5 as shown in the figure given below:

Step 4: Let us take Job J3. If we look at job J3 it has a deadline 3. This means that we have to
complete job J3 on or before time slot 3 in order to earn its profit. Since its deadline is 3, so we
place it in the first empty cell before deadline 3 as shown in the figure given below:

Step 5: Let us take Job J2. If we look at job J2 it has a deadline 3. This means that we have to
complete job J2 on or before time slot 3 in order to earn its profit. Since its deadline is 3, so we
place it in the first empty cell before deadline 3 as shown in the figure given below:

Step 6: Let us take Job J5. If we look at job J5 it has a deadline 4. This means that we have to
complete job J5 on or before time slot 4 in order to earn its profit. Since its deadline is 4, so we
place it in the first empty cell before deadline 4 as shown in the figure given below:

The optimal schedule is- J2 , J4 J3 , J5 , J1 .This is the required order in which the jobs must be
completed in order to obtain the maximum profit.
Maximum earned profit is 180 + 300 + 190 + 120 + 200 = 990

59
Prepared By Kapil Raghuwanshi