Amity School of Engineering & Technology

Divide & Conquer Method vs Dynamic

Programming
Divide & Conquer Method Dynamic Programming

[Link] deals (involves) three steps [Link] involves the sequence of

at each level of recursion: four steps: Characterize the
Divide the problem into a structure of optimal solutions.
number of sub problems. Recursively defines the values
Conquer the sub problems by of optimal solutions.
solving them recursively. Compute the value of optimal
Combine the solution to the sub solutions in a Bottom-up
problems into the solution for minimum.
original sub problems. Construct an Optimal Solution
from computed information.

2. It is Recursive. 2. It is non Recursive.

 Amity School of Engineering & Technology
Divide & Conquer Method Dynamic Programming

3. It does more work on sub 3. It solves sub problems

problems and hence has only once and then stores in
more time consumption. the table.

4. It is a top-down approach. 4. It is a Bottom-up

approach.
5. In this sub problems are 5. In this sub problems are
independent of each other. interdependent.

6. For example: Merge Sort 6. For example: Matrix

& Binary Search etc. Multiplication.
 Amity School of Engineering & Technology

Dynamic Programming
• Dynamic Programming is the most powerful
design technique for solving optimization
problems.
• Dynamic Programming is used when the sub
problems are not independent, e.g. when
they share the same sub problems. In this
case, divide and conquer may do more work
than necessary, because it solves the same
sub problem multiple times.
 Amity School of Engineering & Technology

• Dynamic Programming solves each

subproblems just once and stores the result in a
table so that it can be repeatedly retrieved if
needed again.
• Dynamic Programming is a Bottom-up
approach- we solve all possible small problems
and then combine to obtain solutions for bigger
problems.
• Dynamic Programming is a paradigm of
algorithm design in which an optimization
problem is solved by a combination of achieving
sub-problem solutions and appearing to the
"principle of optimality".
 Amity School of Engineering & Technology

Elements of Dynamic Programming

• Substructure: Decompose the
given problem into smaller sub
problems. Express the solution of
the original problem in terms of
the solution for smaller problems.
 Amity School of Engineering & Technology

• Table Structure: After solving the

sub-problems, store the results to the
sub problems in a table. This is done
because subproblem solutions are
reused many times, and we do not
want to repeatedly solve the same
problem over and over again.
 Amity School of Engineering & Technology

• Bottom-up Computation: Using table,

combine the solution of smaller sub
problems to solve larger sub problems and
eventually arrives at a solution to complete
problem.
 Amity School of Engineering & Technology

Note: Bottom-up means:-

• Start with smallest subproblems.
• Combining their solutions obtain
the solution to sub-problems of
increasing size.
• Until solving at the solution of the
original problem.
 Amity School of Engineering & Technology

Development of Dynamic Programming

Algorithm
It can be broken into four steps:
• Characterize the structure of an optimal
solution.
• Recursively defined the value of the
optimal solution. Like Divide and Conquer,
divide the problem into two or more
optimal parts recursively. This helps to
determine what the solution will look like.
 Amity School of Engineering & Technology

• Compute the value of the optimal

solution from the bottom up (starting
with the smallest subproblems)
• Construct the optimal solution for the
entire problem form the computed
values of smaller subproblems.
 Amity School of Engineering & Technology

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.
 Amity School of Engineering & Technology

Find the optimal solution for the 0/1

knapsack problem making use of dynamic
programming approach. Consider-
n=4
C= 8kg
P= (1,2,5,6)
W= (2,3, 4, 5)
 Amity School of Engineering & Technology
0/1 Knapsack Problem Using Dynamic
Programming-
Step-01:

• Draw a table say ‘T’ with (n+1) number of

rows and (C+1) number of columns.
• Fill all the boxes of 0th row and 0th column
with zeroes as shown-
Amity School of Engineering & Technology
 Amity School of Engineering & Technology

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.
 Amity School of Engineering & Technology

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.
 Amity School of Engineering & Technology
Problem-2
Find the optimal solution for the 0/1 knapsack
problem making use of dynamic programming
approach. Consider-
n=4
C= 5 kg
(w1, w2, w3, w4) = (2, 3, 4, 5)
(b1, b2, b3, b4) = (3, 4, 5, 6)
Amity School of Engineering & Technology
Amity School of Engineering & Technology
 Amity School of Engineering & Technology
Problem-3
Find the optimal solution for the 0/1
knapsack problem making use of dynamic
programming approach. Consider-
n=5
C= 11 kg
(w1, w2, w3, w4,w5) = (1,2,5,6,7)
(p1,p2,p3,p4,p5) = (1,6,18,22,28)
 Amity School of Engineering & Technology
Answer

• Max profit-40
• (0,0,1,1,0)
 Amity School of Engineering & Technology

Problem 4
Consider the problem having weights and
profits are:
Weights: {3, 4, 6, 5}
Profits: {2, 3, 1, 4}
The weight of the knapsack is 8 kg
 Amity School of Engineering & Technology

Matrix Chain Multiplication

• Given a sequence of matrices, find the most
efficient way to multiply these matrices
together. The problem is not actually to
perform the multiplications, but merely to
decide in which order to perform the
multiplications.
• We have many options to multiply a chain of
matrices because matrix multiplication is
associative. In other words, no matter how
we parenthesize the product, the result will
be the same. For example, if we had four
matrices A, B, C, and D, we would have:
• (ABC)D = (AB)(CD) = A(BCD) = ....
 Amity School of Engineering & Technology

• The matrices have size 4 x 10, 10 x 3, 3 x

12, 12 x 20, 20 x 7. We need to compute
M [i,j], 0 ≤ i, j≤ 5. We know M [i, i] = 0 for
all i.
Amity School of Engineering & Technology
 Amity School of Engineering & Technology
Calculation of Product of 2 matrices:
• 1. m (1,2) = m1 x m2 = 4 x 10 x 10 x 3 = 4
x 10 x 3 = 120
• 2. m (2, 3) = m2 x m3 = 10 x 3 x 3 x 12 =
10 x 3 x 12 = 360
• 3. m (3, 4) = m3 x m4 = 3 x 12 x 12 x 20 =
3 x 12 x 20 = 720
• 4. m (4,5) = m4 x m5 = 12 x 20 x 20 x 7 =
12 x 20 x 7 = 1680
Amity School of Engineering & Technology
 Amity School of Engineering & Technology
Now product of 3 matrices
 Amity School of Engineering & Technology
Now Product of 4 matrices:
 Amity School of Engineering & Technology
Now Product of 5 matrices:
 Amity School of Engineering & Technology

• So Answer is=
((M1 x M2 )x((M3 x M4 )x M5))
 Amity School of Engineering & Technology

Chain Matrix Multiplication

• A1(3x4) x A2 (4x2) X A3(2x5)x
A4(5x6)
 Amity School of Engineering & Technology
Problem

• A1(5x4) x A2 (4x6) X A3(6x2)x

A4(2x7)
 Amity School of Engineering & Technology
Answer

• ((A1)x(A2 xA3))xA4
 Amity School of Engineering & Technology

• A1(4x2) x A2 (2x3) X A3(3x4)x

A4(4x5)
 Amity School of Engineering & Technology

All pair shortest path( Floyd-

Warshall algorithm)
The Floyd Warshall Algorithm is for solving
the All Pairs Shortest Path problem. The
problem is to find shortest distances
between every pair of vertices in a given
edge weighted directed Graph.
 Amity School of Engineering & Technology

Algorithm
FLOYD - WARSHALL (W)
n ← rows [W].
D0 ← W
for k ← 1 to n
do for i ← 1 to n
do for j ← 1 to n
do dij(k) ← min (dij(k-1),dik(k-1)+dkj(k-1) )
return D(n)
 Amity School of Engineering & Technology

Problem

• Using Floyd Warshall Algorithm, find the

shortest path distance between every pair
of vertices.
 Amity School of Engineering & Technology

Step-01:

• Remove all the self loops and parallel

edges (keeping the lowest weight edge)
from the graph.
• In the given graph, there are neither self
edges nor parallel edges.
 Amity School of Engineering & Technology

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 = ∞.
 Amity School of Engineering & Technology

• Initial distance matrix for the given graph

is-
 Amity School of Engineering & Technology

Step-03:
Using Floyd Warshall Algorithm, write the following 4 matrices-
 Amity School of Engineering & Technology

The last matrix D4 represents the shortest path

distance between every pair of vertices.
 Amity School of Engineering & Technology
Problem
 Amity School of Engineering & Technology
Problem
 Amity School of Engineering & Technology
Problem
 Amity School of Engineering & Technology
Problem
 Amity School of Engineering & Technology

Longest Common Subsequence

• The longest common subsequence problem
is finding the longest sequence which exists
in both the given strings.
Subsequence
• Let us consider a sequence S = <s1, s2, s3,
s4, …,sn>.
• A sequence Z = <z1, z2, z3, z4, …,zm> over S
is called a subsequence of S, if and only if it
can be derived from S by deletion of some
elements.
 Amity School of Engineering & Technology

Common Subsequence
Suppose, X and Y are two sequences over a
finite set of elements. We can say that Z is a
common subsequence of X and Y, if Z is a
subsequence of both X and Y.
Longest Common Subsequence:-
• If a set of sequences are given, the
longest common subsequence problem is
to find a common subsequence of all the
sequences that is of maximal length.
 Amity School of Engineering & Technology

Steps
The following steps are followed for finding
the longest common subsequence in string
X and Y.
1. Create a table of
dimension n+1*m+1 where n and m are the
lengths of X and Y respectively. The first row
and the first column are filled with zeros.
 Amity School of Engineering & Technology

2. Fill each cell of the table using the following

logic
• If the character corresponding to the current
row and current column are matching, then fill
the current cell by adding one to the diagonal
element. Point an arrow to the diagonal cell.
• Else take the maximum value from the
previous column and previous row element
for filling the current cell. Point an arrow to
the cell with maximum value.
If they are equal, point to any of them.
 Amity School of Engineering & Technology

3. Step 2 is repeated until the table is filled.

4. The value in the last row and the last
column is the length of the longest common
subsequence.
[Link] order to find the longest common
subsequence, start from the last element
and follow the direction of the arrow. The
elements corresponding to diagonal arrow
form the longest common subsequence.
 Amity School of Engineering & Technology

Example
X = BACDB
Y = BDCB
 Amity School of Engineering & Technology

Answer
• Length- 3
• BDB or BCB
 Amity School of Engineering & Technology

Problem
X = ACADB
Y = CBDA
 Amity School of Engineering & Technology

Answer
• Length-2
• CA or CB or CD
 Amity School of Engineering & Technology

Problem
• X=1 2 3 4 1
• Y=3 4 1 2 1 3
 Amity School of Engineering & Technology

Answer
• Length-3
• 1 2 3 or 1 2 1 or 3 4 1
 Amity School of Engineering & Technology

Travelling Salesman Problem

• 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?
 Amity School of Engineering & Technology

• Travelling salesman problem is the most

notorious computational problem. We can
use brute-force approach to evaluate every
possible tour and select the best one.
For n number of vertices in a graph, there
are (n - 1)! number of possibilities.
• Instead of brute-force using dynamic
programming approach, the solution can be
obtained in lesser time, though there is no
polynomial time algorithm.
 Amity School of Engineering & Technology

• For a subset of cities S Є {1, 2, 3, ... , n} that

includes 1, and j Є S, let C(S, j) be the length of
the shortest path visiting each node in S exactly
once, starting at 1 and ending at j.
• When |S| > 1, we define C(S, 1) = ∝ since the path
cannot start and end at 1.
• Now, let express C(S, j) in terms of smaller sub-
problems. We need to start at 1 and end at j. We
should select the next city in such a way that
C(S,j)=minC(S−{j},i)+d(i,j)wherei∈Sandi≠jc(S,j)
=minC(s−{j},i)+d(i,j)wherei∈Sandi≠j
 Amity School of Engineering & Technology
Example
 Amity School of Engineering & Technology

For S = Φ
• Cost(2,Φ,1)=d(2,1)=5
• Cost(3,Φ,1)=d(3,1)= 6
• Cost(4,Φ,1)=d(4,1)=8
 Amity School of Engineering & Technology

For S = 1
• Cost(2,{3},1)=d[2,3]+Cost(3,Φ,1)=9+6=15
• Cost(2,{4},1)=d[2,4]+Cost(4,Φ,1)=10+8=18
• Cost(3,{2},1)=d[3,2]+Cost(2,Φ,1)=13+5=18
• Cost(3,{4},1)=d[3,4]+Cost(4,Φ,1)=12+8=20
• Cost(4,{3},1)=d[4,3]+Cost(3,Φ,1)=9+6=15
• Cost(4,{2},1)=d[4,2]+Cost(2,Φ,1)=8+5=13
 Amity School of Engineering & Technology
• S=2
• Cost(2,{3,4},1)
=d[2,3]+Cost(3,{4},1)=9+20=29
=d[2,4]+Cost(4,{3},1)=10+15=25
• Cost(3,{2,4},1)
=d[3,2]+Cost(2,{4},1)=13+18=31
=d[3,4]+Cost(4,{2},1)=12+13=25=25
• Cost(4,{2,3},1)
=d[4,2]+Cost(2,{3},1)=8+15=23
=d[4,3]+Cost(3,{2},1)=9+18=27
 Amity School of Engineering & Technology

For S = 3
• Cost(1,{2,3,4},1)
=d[1,2]+Cost(2,{3,4},1)=10+25=35
=d[1,3]+Cost(3,{2,4},1)=15+25=40
=d[1,4]+Cost(4,{2,3},1)=20+23=43
So, The minimum cost path is 35.