DESIGN AND ANALYSIS OF ALGORITHMS NOTES

MODULE-3
3.1 Greedy Techniques:
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.

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.

A greedy algorithm is an algorithmic paradigm that follows the problem-solving heuristic of

making the locally optimal choice at each stage with the hope of finding a global optimum.
In other words, a greedy algorithm chooses the best possible option at each step, without
considering the consequences of that choice on future steps.

Characteristics of Greedy method:

The following are the characteristics of a greedy method:

o 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.
o A Greedy algorithm makes good local choices in the hope that the solution should be
either feasible or optimal.

Components of Greedy Algorithm:

The components that can be used in the greedy algorithm are:

o Candidate set: A solution that is created from the set is known as a candidate set.
o Selection function: This function is used to choose the candidate or subset which can
be added in the solution.
o Feasibility function: A function that is used to determine whether the candidate or
subset can be used to contribute to the solution or not.
o Objective function: A function is used to assign the value to the solution or the partial
solution.
o Solution function: This function is used to intimate whether the complete function has
been reached or not.

Applications of Greedy Algorithm:

o It is used in finding the shortest path.
 o It is used to find the minimum spanning tree using the prim's algorithm or the Kruskal's
algorithm.
o It is used in a job sequencing with a deadline.
o This algorithm is also used to solve the fractional knapsack problem.

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.

3.2 Prim’s Algorithm

Prim's Algorithm starts with an arbitrary node and incrementally builds a minimum spanning
tree by adding edges that connect the tree to the rest of the graph. Here's a step-by-step overview
of how the algorithm works:

 Initialization: Select an arbitrary node as the initial vertex for the minimum spanning
tree.
 Candidate Edge Selection: Identify all the edges that connect the current minimum
spanning tree to vertices not yet included in the tree. From these edges, choose the one
with the smallest weight.
 Add to Tree: Add the selected edge to the minimum spanning tree.
 Repeat: Continue the process by considering the newly added vertex as part of the
minimum spanning tree and finding the next candidate edge.
 Termination: Repeat steps 2-4 until all vertices are included in the minimum spanning
tree, resulting in a tree that spans all the original graph's nodes.

Illustration of the algorithm

Consider the following graph as an example for which we need to find the Minimum Spanning
Tree (MST).
Step 1: Firstly, we select an arbitrary vertex that acts as the starting vertex of the Minimum
Spanning Tree. Here we have selected vertex 0 as the starting vertex.

Step 2: All the edges connecting the incomplete MST and other vertices are the edges {0, 1}
and {0, 7}. Between these two the edge with minimum weight is {0, 1}. So include the edge
and vertex 1 in the MST.
Step 3: The edges connecting the incomplete MST to other vertices are {0, 7}, {1, 7} and {1,
2}. Among these edges the minimum weight is 8 which is of the edges {0, 7} and {1, 2}. Let
us here include the edge {0, 7} and the vertex 7 in the MST. [We could have also included
edge {1, 2} and vertex 2 in the MST].

Step 4: The edges that connect the incomplete MST with the fringe vertices are {1, 2}, {7, 6}
and {7, 8}. Add the edge {7, 6} and the vertex 6 in the MST as it has the least weight (i.e., 1).

Step 5: The connecting edges now are {7, 8}, {1, 2}, {6, 8} and {6, 5}. Include edge {6, 5}
and vertex 5 in the MST as the edge has the minimum weight (i.e., 2) among them.
Step 6: Among the current connecting edges, the edge {5, 2} has the minimum weight. So
include that edge and the vertex 2 in the MST.

Step 7: The connecting edges between the incomplete MST and the other edges are {2, 8}, {2,
3}, {5, 3} and {5, 4}. The edge with minimum weight is edge {2, 8} which has weight 2. So
include this edge and the vertex 8 in the MST.
Step 8: See here that the edges {7, 8} and {2, 3} both have same weight which are minimum.
But 7 is already part of MST. So we will consider the edge {2, 3} and include that edge and
vertex 3 in the MST.

Step 9: Only the vertex 4 remains to be included. The minimum weighted edge from the
incomplete MST to 4 is {3, 4}.
The final structure of the MST is as follows and the weight of the edges of the MST is (4 + 8
+ 1 + 2 + 4 + 2 + 7 + 9) = 37.

Note: If we had selected the edge {1, 2} in the third step then the MST would look like the
following.

Key Properties of Prim's Algorithm

Prim's Algorithm has several key properties:

 Greedy Strategy: The algorithm makes a series of locally optimal choices by selecting
the edge with the minimum weight at each step. This greedy approach ensures that the
final tree is an MST.
 Connectivity: The algorithm only works on connected graphs. If the input graph is not
connected, you would need to apply Prim's Algorithm separately to each connected
component.
  Efficiency: Prim's Algorithm is known for its efficiency, particularly when
implemented using data structures like priority queues or heaps. It has a time
complexity of O(V^2) for dense graphs but can be optimized to O(E + V log V) using
priority queues, where V represents the number of vertices and E represents the number
of edges in the graph.

Applications of Prim's Algorithm

Prim's Algorithm finds applications in various domains, including:

 Network Design: It is used to design efficient communication and transportation

networks while minimizing costs.
 Cluster Analysis: Prim's Algorithm can be employed in data clustering, where it helps
identify connected components or clusters.
 Robotics: In robotics, it can be utilized to plan paths for robots moving through a
connected environment with obstacles.
 Image Processing: Prim's Algorithm has applications in image segmentation and feature
extraction, treating the image as a weighted graph.
 Game Development: It can be used to generate mazes or game maps efficiently.

Conclusion: Prim's Algorithm is a versatile and efficient algorithm for finding minimum
spanning trees in connected, weighted graphs. Its greedy nature, simplicity, and numerous
practical applications make it an invaluable tool in computer science and various other fields.
By systematically selecting edges with the minimum weight, Prim's Algorithm provides an
optimal solution to the problem of connecting a set of nodes with the minimum total cost,
making it a fundamental algorithm in the realm of graph theory and optimization.

Working
The working of Prim's algorithm can be described by using the following steps:

Step 1: Determine an arbitrary vertex as the starting vertex of the MST.

Step 2: Follow steps 3 to 5 till there are vertices that are not included in the MST (known as
fringe vertex).

Step 3: Find edges connecting any tree vertex with the fringe vertices.

Step 4: Find the minimum among these edges.

Step 5: Add the chosen edge to the MST if it does not form any cycle.

Step 6: Return the MST and exit

3.3 Kruskal’s Algorithm

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main
target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the
graph. It follows the greedy approach that finds an optimum solution at every stage instead of focusing on a
global optimum.

How does Kruskal's algorithm work?

In Kruskal's algorithm, we start from edges with the lowest weight and keep adding the edges until
the goal is reached. The steps to implement Kruskal's algorithm are listed as follows -

o First, sort all the edges from low weight to high.

o Now, take the edge with the lowest weight and add it to the spanning tree. If the edge to be
added creates a cycle, then reject the edge.
o Continue to add the edges until we reach all vertices, and a minimum spanning tree is created.

The applications of Kruskal's algorithm are -

o Kruskal's algorithm can be used to layout electrical wiring among cities.

o It can be used to lay down LAN connections.

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 -

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.

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.

Algorithm

1. Step 1: Create a forest F in such a way that every vertex of the graph is a separate tree.
2. Step 2: Create a set E that contains all the edges of the graph.
3. Step 3: Repeat Steps 4 and 5 while E is NOT EMPTY and F is not spanning
4. Step 4: Remove an edge from E with minimum weight
5. Step 5: IF the edge obtained in Step 4 connects two different trees, then add it to the
6. forest F
7. (for combining two trees into one tree).
8. ELSE
9. Discard the edge
10. Step 6: END
Complexity of Kruskal's algorithm:

Now, let's see the time complexity of Kruskal's algorithm.

o TimeComplexity
The time complexity of Kruskal 's algorithm is O(E log E) or O(V log V), where E is the no. of
edges, and V is the no. of vertices.

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.

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.

3.4 Dijkstra’s Algorithm

Dijkstra's Algorithm is a Graph algorithm that finds the shortest path from a source vertex to all
other vertices in the Graph (single source shortest path). It is a type of Greedy Algorithm that only
works on Weighted Graphs having positive weights. The time complexity of Dijkstra's Algorithm
is O(V2) with the help of the adjacency matrix representation of the graph. This time complexity can be
reduced to O((V + E) log V) with the help of an adjacency list representation of the graph, where V is
the number of vertices and E is the number of edges in the graph.

The following are the basic concepts of Dijkstra's Algorithm:

1. Dijkstra's Algorithm begins at the node we select (the source node), and it examines the graph
to find the shortest path between that node and all the other nodes in the graph.
2. The Algorithm keeps records of the presently acknowledged shortest distance from each node
to the source node, and it updates these values if it finds any shorter path.
3. Once the Algorithm has retrieved the shortest path between the source and another node, that
node is marked as 'visited' and included in the path.
4. The procedure continues until all the nodes in the graph have been included in the path. In this
manner, we have a path connecting the source node to all other nodes, following the shortest
possible path to reach each node.
WORKING
A graph and source vertex are requirements for Dijkstra's Algorithm. This Algorithm is established
on Greedy Approach and thus finds the locally optimal choice (local minima in this case) at each step
of the Algorithm.

Each Vertex in this Algorithm will have two properties defined for it:

1. Visited Property
2. Path Property

Let us understand these properties in brief.

Visited Property:

1. The 'visited' property signifies whether or not the node has been visited.
2. We are using this property so that we do not revisit any node.
3. A node is marked visited only when the shortest path has been found.

Path Property:

1. The 'path' property stores the value of the current minimum path to the node.
2. The current minimum path implies the shortest way we have reached this node till now.
3. This property is revised when any neighbor of the node is visited.
4. This property is significant because it will store the final answer for each node.

Initially, we mark all the vertices, or nodes, unvisited as they have yet to be visited. The path to all the
nodes is also set to infinity apart from the source node. Moreover, the path to the source node is set to
zero (0).

We then select the source node and mark it as visited. After that, we access all the neighboring nodes
of the source node and perform relaxation on every node. Relaxation is the process of lowering the cost
of reaching a node with the help of another node.

In the process of relaxation, the path of each node is revised to the minimum value amongst the node's
current path, the sum of the path to the previous node, and the path from the previous node to the current
node.

Let us suppose that p[n] is the value of the current path for node n, p[m] is the value of the path up to
the previously visited node m, and w is the weight of the edge between the current node and previously
visited one (edge weight between n and m).

In the mathematical sense, relaxation can be exemplified as:

p[n] = minimum(p[n], p[m] + w)

We then mark an unvisited node with the least path as visited in every subsequent step and update its
neighbor's paths.

We repeat this procedure until all the nodes in the graph are marked visited.
Whenever we add a node to the visited set, the path to all its neighboring nodes also changes
accordingly.

If any node is left unreachable (disconnected component), its path remains 'infinity'. In case the source
itself is a separate component, then the path to all other nodes remains 'infinity'.

Understanding Dijkstra's Algorithm with an Example

The following is the step that we will follow to implement Dijkstra's Algorithm:

Step 1: First, we will mark the source node with a current distance of 0 and set the rest of the nodes to
INFINITY.

Step 2: We will then set the unvisited node with the smallest current distance as the current node,
suppose X.

Step 3: For each neighbor N of the current node X: We will then add the current distance of X with the
weight of the edge joining X-N. If it is smaller than the current distance of N, set it as the new current
distance of N.

Step 4: We will then mark the current node X as visited.

Step 5: We will repeat the process from 'Step 2' if there is any node unvisited left in the graph.

The Given Graph

1. We will use the above graph as the input, with node A as the source.
2. First, we will mark all the nodes as unvisited.
3. We will set the path to 0 at node A and INFINITY for all the other nodes.
4. We will now mark source node A as visited and access its neighboring nodes.
Note: We have only accessed the neighboring nodes, not visited them.
 5. We will now update the path to node B by 4 with the help of relaxation because the path to
node A is 0 and the path from node A to B is 4, and the minimum((0 + 4), INFINITY) is 4.
6. We will also update the path to node C by 5 with the help of relaxation because the path to
node A is 0 and the path from node A to C is 5, and the minimum((0 + 5), INFINITY) is 5.
Both the neighbors of node A are now relaxed; therefore, we can move ahead.
7. We will now select the next unvisited node with the least path and visit it. Hence, we will visit
node B and perform relaxation on its unvisited neighbors. After performing relaxation, the path
to node C will remain 5, whereas the path to node E will become 11, and the path to
node D will become 13.
8. We will now visit node E and perform relaxation on its neighboring nodes B, D, and F. Since
only node F is unvisited, it will be relaxed. Thus, the path to node B will remain as it is, i.e., 4,
the path to node D will also remain 13, and the path to node F will become 14 (8 + 6).
9. Now we will visit node D, and only node F will be relaxed. However, the path to node F will
remain unchanged, i.e., 14.
10. Since only node F is remaining, we will visit it but not perform any relaxation as all its
neighboring nodes are already visited.
11. Once all the nodes of the graphs are visited, the program will end.

Hence, the final paths we concluded are:

1. A=0
2. B = 4 (A -> B)
3. C = 5 (A -> C)
4. D = 4 + 9 = 13 (A -> B -> D)
5. E = 5 + 3 = 8 (A -> C -> E)
6. F = 5 + 3 + 6 = 14 (A -> C -> E -> F)

3.5 Bellman Ford’s Algorithm

Bellman ford algorithm is a single-source shortest path algorithm. This algorithm is

used to find the shortest distance from the single vertex to all the other vertices of a
weighted graph. There are various other algorithms used to find the shortest path like
Dijkstra algorithm, etc. If the weighted graph contains the negative weight values, then
the Dijkstra algorithm does not confirm whether it produces the correct answer or not.
In contrast to Dijkstra algorithm, bellman ford algorithm guarantees the correct answer
even if the weighted graph contains the negative weight values.

Rule of this algorithm

1. We will go on relaxing all the edges (n - 1) times where,

2. n = number of vertices
Consider the below graph:

As we can observe in the above graph that some of the weights are negative. The
above graph contains 6 vertices so we will go on relaxing till the 5 vertices. Here, we
 will relax all the edges 5 times. The loop will iterate 5 times to get the correct answer.
If the loop is iterated more than 5 times then also the answer will be the same, i.e.,
there would be no change in the distance between the vertices.

Relaxing means:

1. If (d(u) + c(u , v) < d(v))

2. d(v) = d(u) + c(u , v)
To find the shortest path of the above graph, the first step is note down all the edges
which are given below:

(A, B), (A, C), (A, D), (B, E), (C, E), (D, C), (D, F), (E, F), (C, B)

Let's consider the source vertex as 'A'; therefore, the distance value at vertex A is 0 and
the distance value at all the other vertices as infinity shown as below:

Since the graph has six vertices so it will have five iterations.

First iteration

Consider the edge (A, B). Denote vertex 'A' as 'u' and vertex 'B' as 'v'. Now use the
relaxing formula:

d(u) = 0

d(v) = ∞

c(u , v) = 6

Since (0 + 6) is less than ∞, so update

1. d(v) = d(u) + c(u , v)
d(v) = 0 + 6 = 6

Therefore, the distance of vertex B is 6.

Consider the edge (A, C). Denote vertex 'A' as 'u' and vertex 'C' as 'v'. Now use the
relaxing formula:

d(u) = 0

d(v) = ∞

c(u , v) = 4

Since (0 + 4) is less than ∞, so update

1. d(v) = d(u) + c(u , v)

d(v) = 0 + 4 = 4

Therefore, the distance of vertex C is 4.

Consider the edge (A, D). Denote vertex 'A' as 'u' and vertex 'D' as 'v'. Now use the
relaxing formula:

d(u) = 0

d(v) = ∞

c(u , v) = 5

Since (0 + 5) is less than ∞, so update

1. d(v) = d(u) + c(u , v)

d(v) = 0 + 5 = 5

Therefore, the distance of vertex D is 5.

Consider the edge (B, E). Denote vertex 'B' as 'u' and vertex 'E' as 'v'. Now use the
relaxing formula:

d(u) = 6

d(v) = ∞

c(u , v) = -1
 Since (6 - 1) is less than ∞, so update

1. d(v) = d(u) + c(u , v)

d(v) = 6 - 1= 5

Therefore, the distance of vertex E is 5.

Consider the edge (C, E). Denote vertex 'C' as 'u' and vertex 'E' as 'v'. Now use the
relaxing formula:

d(u) = 4

d(v) = 5

c(u , v) = 3

Since (4 + 3) is greater than 5, so there will be no updation. The value at vertex E is 5.

Consider the edge (D, C). Denote vertex 'D' as 'u' and vertex 'C' as 'v'. Now use the
relaxing formula:

d(u) = 5

d(v) = 4

c(u , v) = -2

Since (5 -2) is less than 4, so update

1. d(v) = d(u) + c(u , v)

d(v) = 5 - 2 = 3

Therefore, the distance of vertex C is 3.

Consider the edge (D, F). Denote vertex 'D' as 'u' and vertex 'F' as 'v'. Now use the
relaxing formula:

d(u) = 5

d(v) = ∞

c(u , v) = -1

Since (5 -1) is less than ∞, so update

1. d(v) = d(u) + c(u , v)

 d(v) = 5 - 1 = 4

Therefore, the distance of vertex F is 4.

Consider the edge (E, F). Denote vertex 'E' as 'u' and vertex 'F' as 'v'. Now use the
relaxing formula:

d(u) = 5

d(v) = ∞

c(u , v) = 3

Since (5 + 3) is greater than 4, so there would be no updation on the distance value of

vertex F.

Consider the edge (C, B). Denote vertex 'C' as 'u' and vertex 'B' as 'v'. Now use the
relaxing formula:

d(u) = 3

d(v) = 6

c(u , v) = -2

Since (3 - 2) is less than 6, so update

1. d(v) = d(u) + c(u , v)

d(v) = 3 - 2 = 1

Therefore, the distance of vertex B is 1.

Now the first iteration is completed. We move to the second iteration.

Second iteration:

In the second iteration, we again check all the edges. The first edge is (A, B). Since (0
+ 6) is greater than 1 so there would be no updation in the vertex B.

The next edge is (A, C). Since (0 + 4) is greater than 3 so there would be no updation
in the vertex C.

The next edge is (A, D). Since (0 + 5) equals to 5 so there would be no updation in the
vertex D.

The next edge is (B, E). Since (1 - 1) equals to 0 which is less than 5 so update:
 d(v) = d(u) + c(u, v)

d(E) = d(B) +c(B , E)

=1-1=0

The next edge is (C, E). Since (3 + 3) equals to 6 which is greater than 5 so there would
be no updation in the vertex E.

The next edge is (D, C). Since (5 - 2) equals to 3 so there would be no updation in the
vertex C.

The next edge is (D, F). Since (5 - 1) equals to 4 so there would be no updation in the
vertex F.

The next edge is (E, F). Since (5 + 3) equals to 8 which is greater than 4 so there would
be no updation in the vertex F.

The next edge is (C, B). Since (3 - 2) equals to 1` so there would be no updation in the
vertex B.

Third iteration

We will perform the same steps as we did in the previous iterations. We will observe
that there will be no updation in the distance of vertices.

1. The following are the distances of vertices:

2. A: 0
3. B: 1
4. C: 3
5. D: 5
6. E: 0
7. F: 3
Time Complexity

The time complexity of Bellman ford algorithm would be O(E|V| - 1).

function bellmanFord(G, S)
for each vertex V in G
distance[V] <- infinite
previous[V] <- NULL
distance[S] <- 0

for each vertex V in G

for each edge (U,V) in G
tempDistance <- distance[U] + edge_weight(U, V)
if tempDistance < distance[V]
distance[V] <- tempDistance
previous[V] <- U

for each edge (U,V) in G

If distance[U] + edge_weight(U, V) < distance[V}
Error: Negative Cycle Exists

return distance[], previous[]

3.6 Huffman Trees

 Data can be encoded efficiently using Huffman Codes.

 It is a widely used and beneficial technique for compressing data.
 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.

For example:

a0

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 code word that starts with an encoded data is unambiguous.

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.

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).
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:

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:
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:

Character Frequency/count Code

a 4 01

b 7 11
 c 3 101

d 2 100

e 4 00

3.7 Knapsack problem

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.

The weights (Wi) and profit values (Pi) of the items to be added in the knapsack are taken as an input
for the fractional knapsack algorithm and the subset of the items added in the knapsack without
exceeding the limit and with maximum profit is achieved as the output.

Algorithm
 Consider all the items with their weights and profits mentioned respectively.

 Calculate Pi/Wi of all the items and sort the items in descending order based on their Pi/Wi values.
 Without exceeding the limit, add the items into the knapsack.

 If the knapsack can still store some weight, but the weights of other items exceed the limit, the
fractional part of the next time can be added.

 Hence, giving it the name fractional knapsack problem.

Examples
 For the given set of items and the knapsack capacity of 10 kg, find the subset of the items to be added
in the knapsack such that the profit is maximum.

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 12 8
Solution

Step 1

Given, n = 5

Wi = {3, 3, 2, 5, 1}
Pi = {10, 15, 10, 12, 8}

Calculate Pi/Wi for all the items

Items 1 2 3 4 5

Weights (in kg) 3 3 2 5 1

Profits 10 15 10 20 8

P i/Wi 3.3 5 5 4 8

Step 2

Arrange all the items in descending order based on Pi/Wi

Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

P i/Wi 8 5 5 4 3.3

Step 3

Without exceeding the knapsack capacity, insert the items in the knapsack with maximum profit.

Knapsack = {5, 2, 3}

However, the knapsack can still hold 4 kg weight, but the next item having 5 kg weight will exceed
the capacity. Therefore, only 4 kg weight of the 5 kg will be added in the knapsack.
 Items 5 2 3 4 1

Weights (in kg) 1 3 2 5 3

Profits 8 15 10 20 10

Knapsack 1 1 1 4/5 0

Hence, the knapsack holds the weights = [(1 * 1) + (1 * 3) + (1 * 2) + (4/5 * 5)] = 10, with maximum
profit of [(1 * 8) + (1 * 15) + (1 * 10) + (4/5 * 20)] = 37.

Dynamic Programming Paradigm:

Dynamic programming is a name, coined by Richard Bellman in 1955. Dynamic programming, as
greedy method, is a powerful algorithm design technique that can be used when the solution to the
problem may be viewed as the result of a sequence of decisions. In the greedy method we make
irrevocable decisions one at a time, using a greedy criterion. However, in dynamic programming we
examine the decision sequence to see whether an optimal decision sequence contains optimal decision
sub sequence. When optimal decision sequences contain optimal decision sub sequences, we can
establish recurrence equations, called dynamic-programming recurrence equations, that enable us to
solve the problem in an efficient way. Dynamic programming is based on the principle of optimality
(also coined by Bellman). The principle of optimality states that no matter whatever the initial state and
initial decision are, the remaining decision sequence must constitute an optimal decision sequence with
regard to the state resulting from the first decision. The principle implies that an optimal decision
sequence is comprised of optimal decision sub sequences. Since the principle of optimality may not
hold for some formulations of some problems, it is necessary to verify that it does hold for the problem
being solved. Dynamic programming cannot be applied when this principle does not hold.

The steps in a dynamic programming solution are:

Verify that the principle of optimality holds

Set up the dynamic-programming recurrence equations

Solve the dynamic-programming recurrence equations for the value of the optimal solution.

Perform a trace back step in which the solution itself is constructed.

3.8 Floyd-Warshall Algorithm

The Floyd-Warshall algorithm is a graph algorithm that is deployed to find the shortest path between
all the vertices present in a weighted graph. This algorithm is different from other shortest path
algorithms; to describe it simply, this algorithm uses each vertex in the graph as a pivot to check if it
provides the shortest way to travel from one point to another.
Floyd-Warshall algorithm works on both directed and undirected weighted graphs unless these graphs
do not contain any negative cycles in them. By negative cycles, it is meant that the sum of all the edges
in the graph must not lead to a negative number.

Since, the algorithm deals with overlapping sub-problems the path found by the vertices acting as pivot
are stored for solving the next steps it uses the dynamic programming approach.

Floyd-Warshall algorithm is one of the methods in All-pairs shortest path algorithms and it is solved
using the Adjacency Matrix representation of graphs.

Consider a graph, G = {V, E} where V is the set of all vertices present in the graph and E is the set of
all the edges in the graph. The graph, G, is represented in the form of an adjacency matrix, A, that
contains all the weights of every edge connecting two vertices.

Algorithm

Step 1 − Construct an adjacency matrix A with all the costs of edges present in the graph. If there is no
path between two vertices, mark the value as ∞.

Step 2 − Derive another adjacency matrix A1 from A keeping the first row and first column of the
original adjacency matrix intact in A1. And for the remaining values, say A1[i,j],
if A[i,j]>A[i,k]+A[k,j] then replace A1[i,j] with A[i,k]+A[k,j]. Otherwise, do not change the values.
Here, in this step, k = 1 (first vertex acting as pivot).

Step 3 − Repeat Step 2 for all the vertices in the graph by changing the k value for every pivot vertex
until the final matrix is achieved.

Step 4 − The final adjacency matrix obtained is the final solution with all the shortest paths.

Pseudocode
Floyd-Warshall(w, n){ // w: weights, n: number of vertices
for i = 1 to n do // initialize, D (0) = [wij]
for j = 1 to n do{
d[i, j] = w[i, j];
}
for k = 1 to n do // Compute D (k) from D (k-1)
for i = 1 to n do
for j = 1 to n do
if (d[i, k] + d[k, j] < d[i, j]){
d[i, j] = d[i, k] + d[k, j];
}
return d[1..n, 1..n];
}
3.9 Matrix Chain Multiplication Problem
Matrix chain multiplication algorithm is only applied to find the minimum cost way to multiply a
sequence of matrices. Therefore, the input taken by the algorithm is the sequence of matrices while
the output achieved is the lowest cost parenthesization.
ALGORITHM-
MATRIX-CHAIN-MULTIPLICATION(p)
n = [Link] 1
let m[1n, 1n] and s[1n 1, 2n] be new matrices
for i = 1 to n
m[i, i] = 0
for l = 2 to n // l is the chain length
for i = 1 to n - l + 1
j=i+l-1
m[i, j] = ∞
for k = i to j – 1
q = m[i, k] + m[k + 1, j] + pi-1pkpj
if q < m[i, j]
m[i, j] = q
s[i, j] = k
return m and s
PRINT-OPTIMAL-OUTPUT(s, i, j )
if i == j
print Ai
else print (
PRINT-OPTIMAL-OUTPUT(s, i, s[i, j])
PRINT-OPTIMAL-OUTPUT(s, s[i, j] + 1, j)
print )
Time Complexity of matrix chain multiplication is : O(n^3)

3.10 Longest Common Subsequence Problem

A subsequence of a given sequence is just the given sequence with some elements left out.
Given two sequences X and Y, we say that the sequence Z is a common sequence of X and Y if Z is a
subsequence of both X and Y.
In the longest common sub sequence problem, we are given two sequences X = (x1, x2,....xm) and
Y =(y1, y2, yn) and wish to find a maximum length common sub sequence of X and Y. LCS Problem
can be solved using dynamic programming.
LCS-LENGTH (X, Y)
1. m ← length [X]
2. n ← length [Y]
3. for i ← 1 to m
4. do c [i,0] ← 0
5. for j ← 0 to m
6. do c [0,j] ← 0
7. for i ← 1 to m
8. do for j ← 1 to n
9. do if xi= yj
10. then c [i,j] ← c [i-1,j-1] + 1
11. b [i,j] ← "↖"
12. else if c[i-1,j] ≥ c[i,j-1]
13. then c [i,j] ← c [i-1,j]
14. b [i,j] ← "↑"
15. else c [i,j] ← c [i,j-1]
16. b [i,j] ← "← "
17. return c and b.
PRINT-LCS (b, x, i, j)
1. if i=0 or j=0
2. then return
3. if b [i,j] = ' ↖ '
4. then PRINT-LCS (b,x,i-1,j-1)
5. print x_i
6. else if b [i,j] = ' ↑ '
7. then PRINT-LCS (b,X,i-1,j)
8. else PRINT-LCS (b,X,i,j-1)

3.11 0/1 Knapsack Problem

A thief is robbing a store and can carry a maximal weight of W into his knapsack. There are n items
and weight of ith item is wi and the profit of selecting this item is pi. What items should the thief take?

Let i be the highest-numbered item in an optimal solution S for W dollars. Then S = S {i} is an
optimal solution for W wi dollars and the value to the solution S is Vi plus the value of the sub-
problem.

We can express this fact in the following formula: define c[i, w] to be the solution for items 1,2, ,
i and the maximum weight w.
 The algorithm takes the following inputs

 The maximum weight W

 The number of items n
 The two sequences v = <v1, v2, , vn> and w = <w1, w2, , wn>

The set of items to take can be deduced from the table, starting at c[n, w] and tracing backwards
where the optimal values came from.

If c[i, w] = c[i-1, w], then item i is not part of the solution, and we continue tracing with c[i-1, w].
Otherwise, item i is part of the solution, and we continue tracing with c [i-1, w-W].

Dynamic-0-1-knapsack (v, w, n, W)
for w = 0 to W do
c[0, w] = 0
for i = 1 to n do
c[i, 0] = 0
for w = 1 to W do
if wi =w then
if vi + c[i-1, w-wi] then
c[i, w] = vi + c[i-1, w-wi]
else c[i, w] = c[i-1, w]
else c[i, w] = c[i-1, w]

3.11 Maximum Network Flow Problem.

The Maximum Flow problem is about finding the maximum flow through a directed graph, from one
place in the graph to another.

More specifically, the flow comes from a source vertex s, and ends up in a sink vertex t, and each
edge in the graph is defined with a flow and a capacity, where the capacity is the maximum flow that
edge can have.

It is defined as the maximum amount of flow that the network would allow to flow from source to
sink. Multiple algorithms exist in solving the maximum flow problem. Two major algorithms to solve
these kind of problems are Ford-Fulkerson algorithm and Dinic's Algorithm. They are explained
below.

Ford-Fulkerson Algorithm:
It was developed by L. R. Ford, Jr. and D. R. Fulkerson in 1956. A pseudocode for this algorithm is
given below,

Inputs required are network graph , source node and sink node .
function: FordFulkerson(Graph G,Node S,Node T):
Initialise flow in all edges to 0
while (there exists an augmenting path(P) between S and T in residual network graph):
Augment flow between S to T along the path P
Update residual network graph
return