Welcome to AIKTC

AoA| Dynamic Programming Approach

Prof. Nusrat Jahan,

Department of Computer Engineering.
AIKTC – Anjuman-I-Islam’s Kalsekar Technical Campus.
Topic : Dynamic Programming Approach (Syllabus)
➢ General Method,
➢ Multistage graphs,
➢ Single source shortest path: Bellman Ford Algorithm
➢ All pair shortest path: Floyd Warshall Algorithm,
➢ Assembly-line scheduling Problem
➢ 0/1 knapsack Problem,
➢ Travelling Salesperson problem,
➢ Longest common subsequence

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Dynamic Programming
It is used to solve optimization problems.

1. Breaks down the complex problem into simpler subproblems

2. Find optimal solution to these subproblems.
3. Store the result of subproblems(memoization)
4. Reuse them so that same subproblem is not calculated more than once.
5. Finally calculates the result of complex problem.

Applicable to problems having properties of overlapping subproblems and optimal

substructure property.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic : Dynamic Programming

➢ Dynamic Programming is a technique in computer programming that helps to

efficiently solve a class of problems that have overlapping subproblems and optimal
substructure property.

➢ If any problem can be divided into subproblems, which in turn are divided into
smaller subproblems, and if there are overlapping among these subproblems, then
the solutions to these subproblems can be saved for future reference. In this way,
efficiency of the CPU can be enhanced. This method of solving a solution is referred
to as dynamic programming.

➢ Such problems involve repeatedly calculating the value of the same subproblems to
find the optimum solution.
A.I. Kalsekar Technical Campus, New Panvel.
Topic : Dynamic Programming Example
Let's find the fibonacci sequence upto 5th term.
For example, 0,1,1, 2, 3. Here, each number is the sum of the two preceding numbers.

We are calculating the fibonacci sequence up to the 5th term.

F(0) = 0
F(1) = 1
F(2) = F(1) + F(0)
F(3) = F(2) + F(1)
F(4) = F(3) + F(2)

Hence, we have the sequence 0,1,1, 2, 3. Here, we have used the results of the previous
steps as shown below. This is called a dynamic programming approach.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Int fib(n)
{
If(n<0)
Error;
If (n== 0)
Return 0;
If (n== 1)
Return 1;
If(n>1)
Return fib(n-1)+ fib(n-2)

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Major components in Dynamic programming

The Following are components of dynamic programming:

1.Recursion - To solve the problems recursively.
2.Memoization – To store the precomputation of subproblems to use further.

DP = RECURSION + MEMOIZATION

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Applications of DP

Examples of DP:

1. 0-1 Knapsack problem

2. Traveling salesman problem
3. Chain Matrix multiplication
4. Assembly-line scheduling
5. String algorithms – Longest common subsequence.
6. Optimized graph algorithms and many more.

A.I. Kalsekar Technical Campus, New Panvel.

Multistage graph
Topic : What is a multistage graph?

➢ A multistage graph G=(V, E) is a directed and weighted graph in which vertices

are divided into stages (the first stage and last stage of which will have a single
vertex to represent the starting vertex or ending vertex).

➢ In between the starting and ending vertex, there will vertices in different stages
that connect the starting and ending vertex.

➢ The main aim of this graph is to find the minimum cost path between starting and
ending vertex.

➢ Consider the following example graph to further understand the multistage

graph:
A.I. Kalsekar Technical Campus, New Panvel.
Topic : Example 1
In this graph, the cost of an edge
is represented as c(i, j). We have
to find the minimum cost path
from vertex 1 to vertex 12. We
will be using this below formula
to find the shortest cost path
from the source to the
destination:

cost(i,j)=minimum{c(j,l)+cost(i+1,l)}

A.I. Kalsekar Technical Campus, New Panvel.

Solution :

A.I. Kalsekar Technical Campus, New Panvel.

Stage :5

A.I. Kalsekar Technical Campus, New Panvel.

Stage :4

A.I. Kalsekar Technical Campus, New Panvel.

 Stage : 3
Vertex 6 is connected to vertices 9 and 10:
Cost[6] = min{ c[6, 10] + Cost[10], c[6, 9] + Cost[9] }
= min{5 + 2, 6 + 4} = min{7, 10} = 7
p[6] = 10

Vertex 7 is connected to vertices 9 and 10:

Cost[7] = min{ c[7, 10] + Cost[10], c[7, 9] + Cost[9] }
= min{3 + 2, 4 + 4} = min{5, 8} = 5
p[7] = 10

Vertex 8 is connected to vertex 10 and 11:

Cost[8] = min{ c[8, 11] + Cost[11], c[8, 10] + Cost[10] }
= min{6 + 5, 5 + 2} = min{11, 7} = 7
p[8] = 10 cost(i, j)=minimum{c(j, l)+cost(i+1,l)}

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Stage :2
Vertex 2 is connected to vertices6, 7 and 8:
Cost[2] = min{ c[2, 6] + Cost[6], c[2, 7] + Cost[7], c[2, 8] + Cost[8] }
= min{4 + 7, 2 + 5, 1 + 7} = min{11, 7, 8} = 7
p[2] = 7
Vertex 3 is connected to vertices 6and 7:
Cost[3] = min{ c[3, 6] + Cost[6], c[3, 7] + Cost[7] }
= min{2 + 7, 7 + 5} = min{9, 12} = 9
p[3] = 6
Vertex 4 is connected to vertex 8:
Cost[4] = c[4, 8] + Cost[8] = 11 + 7 = 18
p[4] = 8
Vertex 5 is connected to vertices 7 and 8:
Cost[5] = min{ c[5, 7] + Cost[7], c[5, 8] + Cost[8] }
= min{11 + 5, 8 + 7} = min{16, 15} = 15
p[5] = 8

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

 Stage :1
Vertex 1 is connected to vertices 2, 3, 4 and 5:
Cost[1] = min{ c[1, 2] + Cost[2], c[1, 3] + Cost[3], c[1, 4] + Cost[4], c[1, 5] + Cost[5]}
= min{ 9 + 7, 7 + 9, 3 + 18, 2 + 15 }
= min { 16, 16, 21, 17 } = 16 p[1] = 2/3

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Algorithm for Multistage Graph
Algorithm MULTI_STAGE(G, k, n, p) // Description: Solve multi-stage problem using dynamic programming
// Input:
k: Number of stages in graph G = (V, E)
c[i, j]:Cost of edge (i, j)

// Output: p[1:k]:Minimum cost path

cost[n] ← 0
for j ← n – 1 to 1 do //Let r be a vertex such that (j, r) in E and c[j, r] + cost[r] is minimum
cost[j]= min{ c[j, r] + cost[r] }
d[j] ← r //stores the next vertex in the optimal path from vertex j.
end
//Find minimum cost path
p[1] ← 1
p[k] ← n
for j ← 2 to k - 1 do
p[j] ← d[p[j - 1]]
end
A.I. Kalsekar Technical Campus, New Panvel.
Topic : Complexity Analysis of Multistage Graph

Time complexity of multistage graph using dynamic programming would be

O(V + |E|).

A.I. Kalsekar Technical Campus, New Panvel.

Example 2

Consider the following example graph to further understand the multistage graph:
 Topic :

In the above graph, cost of an edge is represented as c(i, j).

We need to find the minimum cost path from vertex 1 to vertex 12.

Using the below formula we can find the shortest cost path from source to destination:

cost(i,j)=min c(j,l)+cost(i+1,l)

A.I. Kalsekar Technical Campus, New Panvel.

 Step: 1

Step 1: uses the forwarded approach (cost(5,12) = 0 ).

Here, 5 represents the stage number and 12 represents a node in that
stage. Since there are no outgoing edges from vertex 12, the cost is 0.

Step 2:

cost(4,9)=c(9,12)=6
cost(4,10)=c(10,12)=4
cost(4,11)=c(11,12)= 2

A.I. Kalsekar Technical Campus, New Panvel.

 Step: 3

cost(3,5)=min{c(5,9)+cost(4,9),c(5,10)+cost(4,10)}
min{5+6,2+4}
min{11,6}=6
cost(3,7)=min{c(7,9)+cost(4,9),c(7,10)+cost(4,10),c(7,11)+cost(4,11)}
cost(3,5)=6
min{7+6,5+4,3+2}
min{13,9,5}=5
cost(3,7)=5
cost(3,6)=min{c(6,10)+cost(4,10),c(6,11)+cost(4,11)}
min{4+4,8+2}
min{8,10}=8
cost(3,6)=8

cost(3,8)=c(8,11)+cost(4,11)=7+2=9 cost(3,8)=9

A.I. Kalsekar Technical Campus, New Panvel.

Step 4 :
cost(2,2)=min{c(2,5)+cost(3,5),c(2,6)+cost(3,6),c(2,7)+cost(3,7)}
min{3+6,5+8,6+5}
min{9,13,11}=9
cost(2,2)=9

cost(2,3)=min{c(3,6)+cost(3,6),c(3,7)+cost(3,7),c(3,8)+cost(3,8)}
min{4+8,5+5,7+9}
min{12,10,16}=10
cost(2,3)=10

cost(2,4)=min{c(4,7)+cost(3,7),c(4,8)+cost(3,8)}
min{2+5,7+9}
min{7,16}=7
cost(2,4)=7

A.I. Kalsekar Technical Campus, New Panvel.

 Step : 5

cost(1,1)=min{c(1,2)+cost(2,2),c(1,3)+cost(2,3),c(1,4)+cost(2,4)}
min{9+9,7+10,5+7}
min {18,17,12}=12
cost(1,1)=12

From the above calculations we get:

Here, d represents which vertex has given minimum cost to above

vertex
A.I. Kalsekar Technical Campus, New Panvel.
Topic :

Therefore:

d[1,1]=4
d[2,4]=7
d[3,7]=11
d[4,11]=12

Shortest path 1--4--7--11--12

A.I. Kalsekar Technical Campus, New Panvel.

Shortest Path Problem
Topic : Shortest Path Problem
• Shortest path problem is a problem of finding the shortest path(s) between vertices of a given graph.
• Shortest path between two vertices is a path that has the least cost as compared to all other existing
paths.

Shortest Path Algorithms-

Shortest path algorithms are a family of algorithms used for solving the shortest path problem.

Applications-

Shortest path algorithms have a wide range of applications such as in-

•Google Maps
•Road Networks

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Types of Shortest Path Problem

Various types of shortest path problem are-

1.Single-pair shortest path problem

2.Single-source shortest path problem
3.Single-destination shortest path problem
4.All pairs shortest path problem

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Single-Pair Shortest Path Problem-

•It is a shortest path problem where the shortest path between a given pair of vertices is
computed.
•A* Search Algorithm is a famous algorithm used for solving single-pair shortest path
problem.

Single-Source Shortest Path Problem-

•It is a shortest path problem where the shortest path from a given source vertex to all
other remaining vertices is computed.
•Dijkstra’s Algorithm and Bellman Ford Algorithm are the famous algorithms used for solving
single-source shortest path problem.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Single-Destination Shortest Path Problem-

•It is a shortest path problem where the shortest path from all the vertices to a single destination
vertex is computed.
•By reversing the direction of each edge in the graph, this problem reduces to single-source shortest
path problem.
•Dijkstra’s Algorithm is a famous algorithm adapted for solving single-destination shortest path
problem.

All Pairs Shortest Path Problem-

•It is a shortest path problem where the shortest path between every pair of vertices is computed.
•Floyd-Warshall Algorithm and Johnson’s Algorithm are the famous algorithms used for solving All
pairs shortest path problem.
A.I. Kalsekar Technical Campus, New Panvel.
Single source shortest path: Bellman Ford Algorithm
 Topic : Bellman Ford 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.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example1

Rule of this algorithm

1.We will go on relaxing all the edges

(n - 1) times where,
n = number of vertices

Relaxing means:

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

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

A.I. Kalsekar Technical Campus, New Panvel.

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

A.I. Kalsekar Technical Campus, New Panvel.

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

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Consider the edge (A, C). Denote vertex Consider the edge (A, D). Denote vertex 'A' as
'A' as 'u' and vertex 'C' as 'v'. Now use 'u' and vertex 'D' as 'v'. Now use the relaxing
the relaxing formula: formula:
d(u) = 0 d(u) = 0
d(v) = ∞ d(v) = ∞
c(u , v) = 4 c(u , v) = 5
d(v) = d(u) + c(u , v) Since (0 + 5) is less than ∞, so update
Since (0 + 4) is less than ∞, so update 1.d(v) = d(u) + c(u , v)
d(v) = 0 + 4 = 4 d(v) = 0 + 5 = 5
Therefore, the distance of vertex C is 4. Therefore, the distance of vertex D is 5.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
Consider the edge (B, E). Denote vertex 'B' as Consider the edge (C, E). Denote vertex
'u' and vertex 'E' as 'v'. Now use the relaxing 'C' as 'u' and vertex 'E' as 'v'. Now use the
formula: relaxing formula:
d(u) = 6 d(u) = 4
d(v) = ∞ d(v) = 5
c(u , v) = -1 c(u , v) = 3
Since (6 - 1) is less than ∞, so update Since (4 + 3) is greater than 5, so there
1.d(v) = d(u) + c(u , v) will be no updation. The value at vertex E
d(v) = 6 - 1= 5 is 5.
Therefore, the distance of vertex E is 5.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
Consider the edge (D, C). Denote vertex 'D' as 'u' Consider the edge (D, F). Denote vertex
and vertex 'C' as 'v'. Now use the relaxing 'D' as 'u' and vertex 'F' as 'v'. Now use the
formula: relaxing formula:
d(u) = 5 d(u) = 5
d(v) = 4 d(v) = ∞
c(u , v) = -2 c(u , v) = -1
Since (5 -2) is less than 4, so update Since (5 -1) is less than ∞, so update
1.d(v) = d(u) + c(u , v) 1.d(v) = d(u) + c(u , v)
d(v) = 5 - 2 = 3 d(v) = 5 - 1 = 4
Therefore, the distance of vertex C is 3. Therefore, the distance of vertex F is 4.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
Consider the edge (E, F). Denote
Consider the edge (C, B). Denote vertex 'C' as
vertex 'E' as 'u' and vertex 'F' as 'v'.
'u' and vertex 'B' as 'v'. Now use the relaxing
Now use the relaxing formula:
formula:
d(u) = 5
d(u) = 3
d(v) = ∞
d(v) = 6
c(u , v) = 3
c(u , v) = -2
Since (5 + 3) is greater than 4, so there
Since (3 - 2) is less than 6, so update
would be no updation on the distance
1.d(v) = d(u) + c(u , v)
value of vertex F.
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.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Second iteration
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.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

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

The following are the distances of vertices:

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

A.I. Kalsekar Technical Campus, New Panvel.

 Topic : Example 2

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example 3 of Bellman-Ford Algorithm

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
•Choose path value 0 for the source vertex and infinity for all other vertices.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

▪ If the new calculated path length

is less than the previous path
length, go to the source vertex's
neighboring Edge and relax the
path length of the adjacent Vertex.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
• This procedure must be repeated V-1
times, where V is the number of vertices
in total. This happened because, in the
worst-case scenario, any vertex's path
length can be changed N times to an
even shorter path length.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
•As a result, after V-1 iterations, you
find your new path lengths and can
determine in case the graph has a
negative cycle or not.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example 4

A.I. Kalsekar Technical Campus, New Panvel.

Topic : solution

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Drawbacks of Bellman ford algorithm

The bellman ford algorithm does not produce a correct answer if the sum of the edges
of a cycle is negative.
Let's understand this property through an example. Consider the below graph.

Edges can be written as:

(1, 3), (1, 2), (2, 4), (3, 2), (4, 3)

A.I. Kalsekar Technical Campus, New Panvel.

Bellman Ford Pseudocode

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[]

Topic : Bellman Ford's Complexity

Time Complexity

Best Case Complexity O(E)

Average Case Complexity O(VE)

Worst Case Complexity O(VE) or O(n3)

A.I. Kalsekar Technical Campus, New Panvel.

All pair shortest path: Floyd Warshall Algorithm
Topic : All pair shortest path: Floyd Warshall Algorithm
• Floyd Warshall Algorithm is a famous algorithm.
• It is used to solve All Pairs Shortest Path Problem.
• It computes the shortest path between every pair of vertices of the given graph.
• Floyd Warshall Algorithm is an example of dynamic programming approach.
• The all pair shortest path algorithm is also known as Floyd-Warshall algorithm
is used to find all pair shortest path from a given weighted graph.
• As a result of this algorithm, it will generate a matrix, which will represent the
minimum distance from any node to all other nodes in the graph.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example

Consider the following directed weighted graph-

Using Floyd Warshall Algorithm, find the shortest path distance between every pair of
vertices.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Solution-

Step-01:

• Remove all the self loops from the graph.

• In the given graph, there are neither self edges nor parallel edges.

Step-02:

• Write the initial distance matrix.

• It represents the distance between every pair of vertices in the form of given weights.
• For diagonal elements (representing self-loops), distance value = 0.
• For vertices having a direct edge between them, distance value = weight of that edge.
• For vertices having no direct edge between them, distance value = ∞.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Initial distance matrix for the given graph is-

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step-03: Using Floyd Warshall Algorithm, write the following 4 matrices-

The last matrix D4 represents the shortest path distance

between every pair of vertices.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example 2

find the shortest path between all the pairs of

vertices.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Fill each cell with the distance between

ith and jth vertex

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Calculate the distance from the source vertex to destination vertex through this
vertex k

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Calculate the distance from the source vertex to destination vertex through this
vertex 2

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Calculate the distance from the source vertex to destination vertex through
this vertex 3

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Calculate the distance from the source vertex to destination vertex through
this vertex 4

A4 gives the shortest path between each pair of vertices

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Floyd Warshall Algorithm

1. n = no of vertices
2. A = matrix of dimension n*n
3. for k = 1 to n
4. for i = 1 to n
5. for j = 1 to n
6. 𝐴𝑘 [i, j] = min (𝐴𝑘−1 [i, j], 𝐴𝑘−1 [i, k] + 𝐴𝑘−1 [k, j])
7. return A

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Floyd Warshall Algorithm Complexity

• Time Complexity
There are three loops. Each loop has constant complexities. So, the time
complexity of the Floyd-Warshall algorithm is O(𝑛3 ).

A.I. Kalsekar Technical Campus, New Panvel.

Assembly-line scheduling Problem
 Topic : Assembly-line scheduling
➢ Assembly line scheduling is a manufacturing problem.
➢ In automobile industries assembly lines are used to transfer parts from one station to another station.
➢ Manufacturing of large items like car, trucks etc. generally undergoes through multiple stations,
where each station is responsible for assembling particular part only. Entire product be ready after it
goes through predefined n stations in sequence.
➢ Manufacturing of car may be done through several stages like engine fitting, coloring, light fitting,
fixing of controlling system, gates, seats and many other things.
➢ The particular task is carried out at the station dedicated to that task only.
➢ Based on the requirement there may be more than one assembly line.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Assembly-line scheduling Problem
➢ Assembly line scheduling is a problem in operations management that involves determining
the optimal sequence of tasks or operations on an assembly line to minimize production costs
or maximize efficiency.
➢ This problem can be solved using various data structures and algorithms.
➢ One common approach is dynamic programming, which involves breaking the problem down
into smaller sub-problems and solving them recursively.

• In case of two assembly lines if the load at station j at assembly 1 is very high, then
components are transfer to station of assembly line 2 the converse is also true. This technique
helps to speed ups the manufacturing process.
• The time to transfer partial product from one station to next station on the same assembly line
is negligible. During rush factory may transfer partially completed auto from one assembly
line to another, complete the manufacturing as quickly as possible.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : The below figure presents the problem in a clear picture:

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Terminologies are

• Sij = Station j on assembly line i.

• aij = Time needed to assemble the partial component at station j on assembly line i.
• tij = Time required to transfer component from one assembly to other from station j
to (j + 1).
• ei = Entry time on assembly line i.
• xi = Exit time from assembly line i.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example

We have two assembly

lines, and let's
suppose we decided
to choose the
highlighted path. The
time taken will be:

8+12+5+4+3+2+9+12+
8+9+2 = 74 units.

We have to choose the path which will have the minimum time.
A.I. Kalsekar Technical Campus, New Panvel.
Topic : Algorithm for Assembly Line Scheduling
Algorithm ASSEMBLY_LINE_SCHEDULING(n, e, a, t, x)
// n is number of stations on both assembly
// e is array of entry time on assembly
// a is array of assembly time on given station
// t is array of the time required to change assembly line
//x is array of exit time from assembly

f1[1] ← e1 + a1,1
f2[1] ← e2 + a2,1

for j ← 2 to n do

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :

• The above algorithm will just tell us the Algorithm PRINT_STATIONS(l, n)

minimum time required to take away the
product from station n. i ← 1*
print "line " i ", station " n
• It does not tell anything about the
sequence of stations on assembly. for j ← n downto 2 do

• We can find the station sequence by tracing i ← Li[ j ]

the solution using the following algorithm.
print "line " i ",station " j – 1
end

A.I. Kalsekar Technical Campus, New Panvel.

Example
Same Example : Step by step

A.I. Kalsekar Technical Campus, New Panvel.

Solution :
fi[1] = ei + ai1 , for i = 1, 2

Here, i indicates assembly line, i.e. 1 or 2,

f1 [1] = e1 + a11 = 2 + 7 = 9

f2 [1] = e2 + a21 = 4 + 8 = 12

For j > 1, where j indicates station numbers.

f1 [j] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2, j – 1 + a1j )

f2 [1] = min (f1 [j – 1] + t1, j – 1 + a2j , f2[j – 1] + a2j )

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
For j = 2 : For j = 3 :

f1 [2] = min (f1 [1] + a12, f2 [1] + t21 + a12) f1 [3] = min (f1 [2] + a13 , f2 [2] + t22 + a13)

= min (9 + 9, 12 + 2 + 9) = min (18 + 3, 16 + 1 + 3)

= 18 = 20

f2 [2] = min (f1 [1] + t11 + a22 , f2 [1] + a22) f2 [3] = min (f1 [2] + t12 + a23 , f2 [2] + a23)

= min (9 + 2 + 5, 12 + 5) = min (18 + 3 + 6, 16 + 6)

= 16 = 22

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
For j = 4 : For j = 5 :

f1 (4) = min (f1 [3] + a14, f2 [3] + t23 + a14) f1 (5) = min (f1 [4] + a15, f2 [4] + t24 + a15)

= min (20 + 4, 22 + 2 + 4) = min (24 + 8, 25 + 2 + 8)

= 24 = 32

f2 (4) = min (f1 [3] + t13 + a24, f2 [3] + a24) f2 (5) = min (f1 [4] + t14 + a25, f2 [4] + a25)

= min (20 + 1 + 4, 22 + 4) = min (24 + 3 + 5, 25 + 5)

= 25 = 30

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
For j = 6 : f* = min (f1 (n) + x1, f2 (n) + x2)

f1 (6) = min (f1 [5] + a16, f2 [5] + t25 + a16) where n = number of stations = 6

= min (32 + 4, 30 + 1 + 4) x1 and x2 are exit time from line 1 and line 2
respectively.
= 35
x1 = 3, x2 = 2
f2 (6) = min (f1 [5] + t15 + a26, f2 [5] + a26)
f* = min (f1 [6] + x1, f2 [6] + x2)
= min (32 + 4 + 7, 30 + 7)
= min (35 + 3, 37 + 2)
= 37 = 38

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Hence we can summarize f1[j] and

f2[j] as follows

Compute fastest path :

A.I. Kalsekar Technical Campus, New Panvel.

Example 2: Find optimal assembly line schedule for given data.

A.I. Kalsekar Technical Campus, New Panvel.

Solution:

fi [j] = ei + ai,1; Initial condition (j = 1, i=1, 2)

f1 [j] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2 j – 1) + a1j)

f2 [j] = min (f1 [j – 1] + t1 j – 1) + a2j, f2 [j – 1] + a2j )

f* = min (f1 [n] + x1, f2 [n]+x2 )

f1 [1] = e1 + a11 = 4 + 2 = 6

f2 [1] = e2 + a21 = 2 + 6 = 8

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

f1 [2] = min (f1[j – 1] + a1j, f2 [j – 1] + t2j – 1+ a1j )

= min (f1 [1] + a12, f2 [1] + t21 + a12)

f2 [2] = min (f1 [j – 1] + tj – 1 + a2j, f2 [j – 1] + a2j)
= min (6 + 8, 8 + 3 + 8)
= min (f1[1] + t11 + a22, f2 [1] + a22 )
= min (14, 19)
= min (6 + 3 + 11, 8 + 11)
= 14
= min(20, 19)

= 19

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

f1 [3] = min (f1[j – 1] + a1j, f2 [j – 1] + t2j – 1) + a1j )

= min (f1[2] + a13, f2 [2] + t22 + a13 )

f2 [3] = min (f1[j – 1] + tj – 1 + a2j, f2 [j – 1] + a2j )
= min (14 + 9, 19 + 4 + 9)
= min (f1[2] + t12 + a23, f2 [2] + a23)
= min (23, 32)
= min (14 + 1 + 2, 19 + 2)
= 23
= min (17, 21)

= 17

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

f1 [4] = min (f1 [j – 1] + a1j, f2 [j – 1] + t2j – 1 + a1j )

= min (f1 [3] + a14, f2 [3] + t23 + a14)

f2 [4] = min (f1 [j – 1] + tj – 1 + a2j, f2 [j – 1] + a2j)
= min (23 + 3 , 17 + 1 + 3)
= min(f1 [3] + t13 + a24, f2 [3] + a24)
= min (26, 21)
= min (23 + 2 + 2, 17 + 2)
= 21
= min(27, 19)

= 19

A.I. Kalsekar Technical Campus, New Panvel.

Hence we can summarize f1[j] and f2[j] as follows :

j=1 j=2 j= 3 j=4 j=5 j=6

Compute fastest path :
f1[j] 6 14 23 21 24 25
f2[j] 8 17 19 26 29 30

f* = min (f1 [n] + x1, f2 [n] + x2)

f* = min (25 + 3, 30 + 7)

= min (28, 37)

= 28

A.I. Kalsekar Technical Campus, New Panvel.

 Trace back the path :

• l* = 1, so we have to select last station S1,6 on line 1.

Now we will look at l1[6], which is 1, so we will
select previous station on line 1 that is station
S1, 5.
• Now we will look at l1, 5 which is 2 so we will change
line to 2 and previous station that is S2, 4.
• Next observe l2[4], its 2 so we have to remain on
same line and select station S2, 3.
• Now observe l2[3], which is 1, so move on station
S1,2 on line 1.
• Now observe l1[3], which is 1, so remain on same
line.
A.I. Kalsekar Technical Campus, New Panvel.
Final path is shown in following figure:

A.I. Kalsekar Technical Campus, New Panvel.

0/1 knapsack Problem
Topic : 0/1 Knapsack Problem

In 0/1 Knapsack Problem,

➢ As the name suggests, items are indivisible here.
➢ We can not take the fraction of any item.
➢ We have to either take an item completely or leave it completely.
➢ It is solved using dynamic programming approach.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic : 0/1 Knapsack Problem Using Dynamic Programming

Consider-
➢ Knapsack weight capacity = w
➢ Number of items each having some weight and value = n

0/1 knapsack problem is solved using dynamic programming in the following

steps-

Step-01:

➢ Draw a table say ‘T’ with (n+1) number of rows and (w+1) number of
columns.

➢ Fill all the boxes of 0th row and 0th column with zeroes as shown-

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Step-02:

Start filling the table row wise top to bottom from left to right.
Use the following formula-
T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }

Here, T(i , j) = maximum value of the selected items if we can take items 1 to i and have weight
restrictions of j.

•This step leads to completely filling the table.

•Then, value of the last box represents the maximum possible value that can be put into the
knapsack.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Step-03:

To identify the items that must be put into the knapsack to obtain that maximum
profit,
➢ Consider the last column of the table.
➢ Start scanning the entries from bottom to top.
➢ On encountering an entry whose value is not same as the value stored in the
entry immediately above it, mark the row label of that entry.
➢ After all the entries are scanned, the marked labels represent the items that
must be put into the knapsack.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : We can find the items that give optimum result using the following algorithm
Algorithm TRACE_KNAPSACK(w, v, M) while ( j> 0 ) do
// w is array of weight of n items if (V[i, j] == V[i – 1, j]) then
// v is array of value of n items i←i–1
// M is the knapsack capacity else
V[i, j] ← V[i, j] – vi
SW ← { } j ← j – w[i]
SP ← { } SW ← SW +w[i]
i←n SP ← SP +v[i]
j←M end
end

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Time Complexity-

➢ Each entry of the table requires constant time θ(1) for its computation.
➢ It takes θ(nw) time to fill (n+1)(w+1) table entries.
➢ It takes θ(n) time for tracing the solution since tracing process traces the n rows.
➢ Thus, overall θ(nw) time is taken to solve 0/1 knapsack problem using dynamic
programming.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example 1
For the given set of items and knapsack capacity = 5 kg, find the optimal solution for the
0/1 knapsack problem making use of dynamic programming approach.

Item Weight Value

1 2 3
2 3 4
3 4 5
4 5 6

OR

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
Find the optimal solution for the 0/1 knapsack problem making use of dynamic programming approach.
Consider-
n=4
w = 5 kg
(w1, w2, w3, w4) = (2, 3, 4, 5)
(b1, b2, b3, b4) = (3, 4, 5, 6) OR

Item Weight (kg) Value ($)

A thief enters a house for robbing it. He can carry a maximal
weight of 5 kg into his bag. There are 4 items in the house Mirror 2 3
with the following weights and values. What items should Silver nugget 3 4
thief take if he either takes the item completely or leaves it
completely? Painting 4 5
Vase 5 6

A.I. Kalsekar Technical Campus, New Panvel.

 Topic : Solution
Given-
T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }
•Knapsack capacity (w) = 5 kg
•Number of items (n) = 4

Step-01:

• Draw a table say ‘T’ with (n+1) = 4 + 1 = 5

number of rows
• and (w+1) = 5 + 1 = 6 number of columns.
• Fill all the boxes of 0th row and 0th column with 0.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step-02:

Start filling the table row wise top to bottom from left to right using the formula-
Finding T(1,1)-
T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }
We have,
•i = 1, j = 1
•(value)i = (value)1 = 3
•(weight)i = (weight)1 = 2

Substituting the values, we get-

T(1,1) = max { T(1-1 , 1) , 3 + T(1-1 , 1-2) }
T(1,1) = max { T(0,1) , 3 + T(0,-1) }
T(1,1) = T(0,1) { Ignore T(0,-1) }
T(1,1) = 0

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Finding T(1,2)- Finding T(1,3)-

We have, We have,
•i = 1 •i = 1
•j = 2 •j = 3
•(value)i = (value)1 = 3 •(value)i = (value)1 = 3
•(weight)i = (weight)1 = 2 •(weight)i = (weight)1 = 2

Substituting the values, we get- Substituting the values, we get-

T(1,2) = max { T(1-1 , 2) , 3 + T(1-1 , 2-2) } T(1,3) = max { T(1-1 , 3) , 3 + T(1-1 , 3-2) }
T(1,2) = max { T(0,2) , 3 + T(0,0) } T(1,3) = max { T(0,3) , 3 + T(0,1) }
T(1,2) = max {0 , 3+0} T(1,3) = max {0 , 3+0}
T(1,2) = 3 T(1,3) = 3

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Finding T(1,4)- Finding T(1,5)-

We have, We have,
•i = 1 •i = 1
•j = 4 •j = 5
•(value)i = (value)1 = 3 •(value)i = (value)1 = 3
•(weight)i = (weight)1 = 2 •(weight)i = (weight)1 = 2

Substituting the values, we get- Substituting the values, we get-

T(1,4) = max { T(1-1 , 4) , 3 + T(1-1 , 4-2) } T(1,5) = max { T(1-1 , 5) , 3 + T(1-1 , 5-2) }
T(1,4) = max { T(0,4) , 3 + T(0,2) } T(1,5) = max { T(0,5) , 3 + T(0,3) }
T(1,4) = max {0 , 3+0} T(1,5) = max {0 , 3+0}
T(1,4) = 3 T(1,5) = 3
A.I. Kalsekar Technical Campus, New Panvel.
Topic :
Finding T(2,1)- Finding T(2,2)-

We have, We have,
•i = 2 •i = 2
•j = 1 •j = 2
•(value)i = (value)2 = 4 •(value)i = (value)2 = 4
•(weight)i = (weight)2 = 3 •(weight)i = (weight)2 = 3

Substituting the values, we get- Substituting the values, we get-

T(2,1) = max { T(2-1 , 1) , 4 + T(2-1 , 1-3) } T(2,2) = max { T(2-1 , 2) , 4 + T(2-1 , 2-3) }
T(2,1) = max { T(1,1) , 4 + T(1,-2) } T(2,2) = max { T(1,2) , 4 + T(1,-1) }
T(2,1) = T(1,1) { Ignore T(1,-2) } T(2,2) = T(1,2) { Ignore T(1,-1) }
T(2,1) = 0 T(2,2) = 3
A.I. Kalsekar Technical Campus, New Panvel.
Topic :
Finding T(2,3)- Finding T(2,4)-

We have, We have,
•i = 2 •i = 2
•j = 3 •j = 4
•(value)i = (value)2 = 4 •(value)i = (value)2 = 4
•(weight)i = (weight)2 = 3 •(weight)i = (weight)2 = 3

Substituting the values, we get- Substituting the values, we get-

T(2,3) = max { T(2-1 , 3) , 4 + T(2-1 , 3-3) } T(2,4) = max { T(2-1 , 4) , 4 + T(2-1 , 4-3) }
T(2,3) = max { T(1,3) , 4 + T(1,0) } T(2,4) = max { T(1,4) , 4 + T(1,1) }
T(2,3) = max { 3 , 4+0 } T(2,4) = max { 3 , 4+0 }
T(2,3) = 4 T(2,4) = 4
A.I. Kalsekar Technical Campus, New Panvel.
Topic :
Finding T(2,5)-

We have,
•i = 2
•j = 5
•(value)i = (value)2 = 4
•(weight)i = (weight)2 = 3

Substituting the values, we get-

T(2,5) = max { T(2-1 , 5) , 4 + T(2-1 , 5-3) }
T(2,5) = max { T(1,5) , 4 + T(1,2) }
T(2,5) = max { 3 , 4+3 }
T(2,5) = 7
A.I. Kalsekar Technical Campus, New Panvel.
 Topic :
Similarly, compute all the entries.
After all the entries are computed and filled in the table, we get the following table-

T (i , j) = max { T ( i-1 , j ) , valuei + T( i-1 , j – weighti ) }

➢ The last entry represents the maximum possible

value that can be put into the knapsack.
➢ So, maximum possible value that can be put into
the knapsack = 7.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Find selected items for M = 5

Step 1 : Initially, i = n = 4, j = M = 5 V[i, j] = V[4, 5] = 7

V[i – 1, j] = V[3, 5] = 7

V[i, j] = V[i – 1, j], so don’t select ith item and check for
the previous item.

so i = i – 1 = 4 – 1 = 3

Solution Set S = { }

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step 2 : i = 3, j = 5
V[i, j] = V[3, 5] = 7

V[i – 1, j] = V[2, 5] = 7

V[i, j] = V[i – 1, j], so don’t select ith item and check

for the previous item.

so i = i – 1 = 3 – 1 = 2

Solution Set S = { }

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step 3 : i = 2, j = 5 V[i, j] = V[2, 5] = 7

V[i – 1, j] = V[1, 5] = 3

V[i, j] ≠ V[i – 1, j], so add item Ii = I2 in solution set.

Reduce problem size j by wi

j = j – wi = j – w2 = 5 – 3 = 2

i=i–1=2–1=1

Solution Set S = {I2}

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step 4 : i = 1, j = 2 V[1, j] = V[1, 2] = 3

V[i – 1, j] = V[0, 2] = 0

V[i, j] ≠ V[i – 1, j], so add item Ii = I1 in solution set.

Reduce problem size j by wi

j = j – wi = j – w1 = 2 – 2 = 0

Solution Set S = {I1, I2}

Problem size has reached to 0, so final solution is

S = {I1, I2} Earned profit = P1 + P2 = 7

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :

Identifying Items To Be Put Into Knapsack-

Following Step-03,
•We mark the rows labelled “1” and “2”.
•Thus, items that must be put into the knapsack to obtain the maximum value 7 are-
Item-1 and Item-2

A.I. Kalsekar Technical Campus, New Panvel.

Travelling Salesperson problem
Topic : Travelling Salesperson problem
➢ Traveling salesman problem is stated as, “Given a set of n cities and distance between
each pair of cities, find the minimum length path such that it covers each city exactly
once and terminates the tour at starting city.”

A.I. Kalsekar Technical Campus, New Panvel.

Topic : What is Travelling Salesperson problem

➢ In the TSP, given a set of cities and the

distance between each pair of cities, a
salesman needs to choose the shortest
path to visit every city exactly once and
return to the city from where he started.

➢ Let’s take an example to understand the

TSP in more detail:

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

➢ Here, the nodes represent cities, and the values in each edge denote the distance
between one city to another. Let’s assume a salesman starts the journey from the
city A.

➢ According to TSP, the salesman needs to travel all the cities exactly once and get
back to the city A by choosing the shortest path.

➢ Here the shortest path means the sum of the distance between each city travelled by
the salesman, and it should be less than any other path.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Dynamic Programming Approach for Solving TSP

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Problem Statement
A traveler needs to visit all the cities from a list, where distances between all the cities are known and each city
should be visited just once. What is the shortest possible route that he visits each city exactly once and returns to
the origin city?

Solution:
1. Let us consider a graph G = (V, E), where V is a set of cities and E is a set of weighted edges. An edge e(u, v)
represents that vertices u and v are connected. Distance between vertex u and v is d(u, v), which should be non-
negative.
2. We have started in the city i and need to visit all the S cities once and returns to the same starting city i. So, we
need to know which is the shortest path to visit all the city.
3. Suppose we have started in city 1 and after visiting some cities now we are in the city k. since this will determine
which cities are most convenient to visit next. We also need to know all the cities visited so far, so that we don’t
repeat any of them.

A.I. Kalsekar Technical Campus, New Panvel.

 Topic : Solution

1. Let us define a term g(i, S) be the cost of the minimum cost path visiting each city in
set S exactly once, starting at 1 and ending at i.
2. We start with all subsets of size 2 and calculate g(i, S) for all subsets where S is the
subset, then we calculate g(i, S) for all subsets S of size 3 and so on. Note that 1 must
be present in every subset.
3. We need to start at 1 and end at k. We should select the next city in such a way that

g{i,S} = min{Cik + g{k, S-{k}}} where k Є S

i is a Starting point of a tour and S a subset of cities. Using this formula we are going to
solve a problem.

A.I. Kalsekar Technical Campus, New Panvel.

Topic : Example
Distance Matrix

A.I. Kalsekar Technical Campus, New Panvel.

Topic :Solution
g(2, Φ ) = C21 = 5 Set {3} :
Set {4} :
g(3, Φ ) = C31 = 6
g(4, Φ ) = C41 = 8 g(2,{3}) = c23 + g(3, Φ )
g(2,{4}) = c24 + g(4, Φ )
= c23 + c31
= c24 + c41
=9+6
K = 1 , consider set of one element : = 10 + 8
= 15
= 18
Set {2}: g(4,{3}) = c43 + g(3, Φ )
g(3,{4}) = c34 + g(4, Φ )
g(3,{2}) = c32 + g(2, Φ ) = c43 + c31
= c34 + c41
= c32 + c21 = 9+ 6
= 12 + 8
= 13 + 5 = 15
= 20
= 18
g(4,{2}) = c42 + g(2, Φ )
= c42 + c21
= 8+ 5
= 13

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
K = 2 , consider set of two element :

Set {3,4} :
Set {2,3} :
g {2,{3,4}} = min {c23 + g(3,{4}) , c24 + g(4,{3})}
= min { 9 + 20 , 10 + 15} g(4,{2,3}) = min {c42 + g(2,{3}), c43 + g(3,{2})}
= min { 29, 25} = min { 8 + 15 , 9 + 18}
= 25 = min { 23, 27}
= 23

Set {2,4} :

g {3,{2,4}} = min {c32 + g(2,{4}), c34 + g(4,{2})}

= min { 13+ 18, 12 + 13}
= min { 31, 25}
= 25

A.I. Kalsekar Technical Campus, New Panvel.

 Topic :
Length of an optimal tour,

g { 1, {2,3,4}} = min{ c12 + g(2,{3,4}), c13 + g(3,{2,4}), c14 + g(4,{2,3})}

= min { (25 + 10 ) , (25 + 15) , (23 + 20) }
= min { ( 35), (40), (43)}
= 35

The minimum cost path is 35.

The optimal tour route is, 1 -> 2 -> 4 -> 3 -> 1 .

A.I. Kalsekar Technical Campus, New Panvel.

Longest common subsequence
Topic : Longest Common Subsequence (LCS)
• Given two strings, S1 and S2, the task is to find the length of the longest subsequence present in both of
the strings.

• Examples:

Input: S1 = “AGGTAB”, S2 = “GXTXAYB”

Output: 4
Explanation: The longest subsequence which is present in both strings is “GTAB”.

• Input: S1 = “ABCDGH”, S2 = “AEDFHR”

Output: 3
Explanation: The longest subsequence which is present in both strings is “ADH”.

A.I. Kalsekar Technical Campus, New Panvel.

Longest Common Subsequence Problem:

▪ Let A = < a1, a2, a3 …an> and B = < b1, b2, b3 …bm> be two strings over an alphabets. Then B
is subsequence of A, if B can be generated by striking out some elements from A.

• By subsequence, we mean that the values must occur in the order of the sequence, but they
need not be consecutive.

• If A = < X, Y, X, X, Z, Y, X > and B = < X, X, Y, X > then by deleting A[2], A[4] and A[5]
from A, we can derive B. So B is the subsequence of A.

• The common subsequence of A and B is the subsequence that can be generated by

striking some characters from A and B both.

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
• If A = {a, b, a, c, b, c, b} and
B = {a, b, c, b, b, a, c},

then the sequence {a, c}, {a, b, c}, {a, c, c}, {a, b, c,
b} etc. are common subsequences of A and B, but
{a, b, c, b, a} is not.

A.I. Kalsekar Technical Campus, New Panvel.

Mathematical Formulation:

• Let us consider two strings Am and Bn of length m and n respectively.

• If the last character of both strings is the same i.e. am = bn, then the length of LCS
is incremented by one, and the length of both strings is reduced by one.
• The new problem is now to find LCS of strings Am-1 and Bn-1.

• If am ≠ bn, we shall consider two sub-problems.

Apply LCS on strings Am-1 and B

Apply LCS on strings A and Bn-1

• Select the result which gives the longest subsequence.

A.I. Kalsekar Technical Campus, New Panvel.

Algorithm for Longest Common Subsequence

Algorithm LONGEST_COMMON_SUBSEQUENCE(X, Y) for i ← 1 to m do

// X is string of length n for j ← 1 to n do
// Y is string of length m if Xi = = Yj then
LCS[i, j] ← LCS[i – 1, j – 1] + 1
for i ← 1 to m do else
LCS [i, 0] ← 0 if LCS[i – 1, j] ≥ LCS[i, j – 1] then
end LCS[i, j] ← LCS[i – 1, j]
else
for j ← 0 to n LCS[i, j] ← LCS[i, j – 1]
do end
LCS [0, j] ← 0 end
end end
end
return LCS

A.I. Kalsekar Technical Campus, New Panvel.

Example : Given two sequences of characters, P=<MLNOM> Q=<MNOM>. Obtain the longest
common subsequence.

Solution: Given two strings are P = <MLNOM> and Q = <MNOM>

The optimal substructure of LCS problem using dynamic programming is given as :

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Initially, the table looks like,

Let’s compute the remaining cell values row by row :

Computation for row 1 :

LCS [1, 1] ⇒ i = 1, j = 1, Pi = M, Qj = M

Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1]

LCS [1, 1] = 1 + LCS[0, 0] = 1 + 0 = 1

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
LCS [1, 2] ⇒ i = 1, j = 2, Pi = M, Qj = N

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [1, 2] = max (LCS [0, 2], LCS [1, 1]) = max (0, 1) = 1 LCS [1, 4] ⇒ i = 1, j = 4, Pi = M, Qj = M

Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1]

LCS [1, 3] ⇒ i = 1, j = 3, Pi = M, Qj = O LCS [1, 4] = 1 + LCS[0, 3] = 1 + 0 = 1

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [1, 3] = max(LCS[0, 3], LCS[1, 2]) = max(0, 1) = 1

A.I. Kalsekar Technical Campus, New Panvel.

 Computation for row 2 :

LCS [2, 1] ⇒ i = 2, j = 1, Pi = L, Qj = M LCS [2, 3] ⇒ i = 2, j = 3, Pi = L, Qj = O

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [2, 1] = max (LCS [1, 1], LCS [2, 0]) = max (1, 0) = 1 LCS [2, 3] = max(LCS[1, 3], LCS[2, 2]) = max(1, 1) = 1

LCS [2, 2] ⇒ i = 2, j = 2, Pi = L, Qj = N LCS [2, 4] ⇒ i = 2, j = 4, Pi = L, Qj = M

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [2, 2] = max (LCS [1, 2], LCS [2, 1]) = max (1, 1) = 1 LCS [2, 4] = max (LCS [1, 4], LCS [2, 3]) = max (1, 1) = 1

A.I. Kalsekar Technical Campus, New Panvel.

 Computation for row 3 :

LCS [3, 1] ⇒ i = 3, j = 1, Pi = N, Qj = M LCS [3, 3] ⇒ i = 3, j = 3, Pi = N, Qj = O

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [3, 1] = max (LCS [2, 1], LCS [3, 0]) = max (1, 0) = 1 LCS [3, 3] = max(LCS[2, 3], LCS[3, 2]) = max(1, 2) = 2

LCS [3, 2] ⇒ i = 3, j = 2, Pi = N, Qj = N LCS [3, 4] ⇒ i = 3, j = 4, Pi = N, Qj = M

Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1] Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [3, 2] = 1 + LCS[2, 1] = 1 + 1 = 2 LCS [3, 4] = max (LCS [2, 4], LCS [3, 3]) = max (1, 2) = 2

A.I. Kalsekar Technical Campus, New Panvel.

Computation for row 4 :

LCS [4, 1] ⇒ i = 4, j = 1, Pi = O, Qj = M LCS [4, 3] ⇒ i = 4, j = 3, Pi = O, Qj = O

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1]

LCS [4, 1] = max (LCS [3, 1], LCS [4, 0]) = max (1, 0) = 1 LCS [4, 3] = 1 + LCS[3, 2] = 1 + 2 = 3

LCS [4, 2] ⇒ i = 4, j = 2, Pi = O, Qj = N LCS [4, 4] ⇒ i = 4, j = 4, Pi = O, Qj = M

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])

LCS [4, 2] = max (LCS [3, 2], LCS [4, 1]) = max (2, 1) = 2 LCS [4, 4] = max (LCS [3, 4], LCS [4, 3]) = max (2, 3) = 3

A.I. Kalsekar Technical Campus, New Panvel.

 Computation for row 5 :

LCS [5, 3] ⇒ i = 5, j = 3, Pi = M, Qj = O
LCS [5, 1] ⇒ i = 5, j = 1, Pi = M, Qj = M
Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1])
Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1]
LCS [5, 3] = max (LCS [4, 3], LCS [5, 2]) = max (3, 2) = 3
LCS [5, 1] = 1 + LCS[4, 0] = 1 + 0 = 1

LCS [5, 2] ⇒ i = 5, j = 2, Pi = M, Qj = N LCS [5, 4] ⇒ i = 5, j = 4, Pi = M, Qj = M

Pi ≠ Qj ⇒ LCS [i, j] = max (LCS [i – 1 , j], LCS [i, j – 1]) Pi = Qj ⇒ LCS [i, j] = 1 + LCS[i – 1, j – 1]

LCS [5, 2] = max (LCS [4, 2], LCS [5, 1]) = max (2, 1) = 2 LCS [5, 4] = 1 + LCS[5, 3] = 1 + 3 = 4

A.I. Kalsekar Technical Campus, New Panvel.

So finally, table would be,

Longest common subsequence for given

strings is of length 4. Let us find LCS of P and
Q:

Step 1: i = 5, j = 4, Pi = M, Qj = M

Pi = Qi, so add Pi to solution set. And move

diagonally back.

Solution set S = {M }

A.I. Kalsekar Technical Campus, New Panvel.

Topic :
Step 2: i = 4, j = 3, Pi = O, Qj = O Step 4: i = 2, j = 1, Pi = L, Qj = M
Pi = Qi, so add Pi to solution set. And move Pi ≠ Qj, and LCS[i, j] is derived from LCS[i –
diagonally back.
1, j]. So move in vertical direction.
Solution set S = { M, O }
Solution set S = { M, O, N }

Step 3: i = 3, j = 2, Pi = N, Qj = N Step 5: i = 1, j = 1, Pi = M, Qj = M

Pi = Qi, so add Pi to solution set. And move Pi = Qi, so add Pi to solution set. And
diagonally back. move diagonally back.

Solution set S = { M, O, N } Solution set S = { M, O, N, M }

A.I. Kalsekar Technical Campus, New Panvel.

Topic :

Moving diagonally back i and j become zero. So stop. We have collected

characters from the last position of the string. So reverse the solution set,
which is the LCS of P and Q.

So, LCS = MNOM

A.I. Kalsekar Technical Campus, New Panvel.

 Keep Learning, Keep Growing…

Your feedback is valuable to us, so please keep giving it.

You can reach us at

www.aiktc.ac.in
and can contact at
@aiktc.ac.in

A.I. Kalsekar Technical Campus, New Panvel.