SRI RAMAKRISHNA ENGINEERING

COLLEGE
[Educational Service : SNR Sons Charitable Trust]
[Autonomous Institution, Reaccredited by NAAC with ‘A+’ Grade]
[Approved by AICTE and Permanently Affiliated to Anna University, Chennai]
[ISO 9001:2015 Certified and all Eligible Programmes Accredited by NBA]
VATTAMALAIPALAYAM, N.G.G.O. COLONY POST, COIMBATORE – 641 022.

partment of Artificial Intelligence and Data Scie

epartment

20IT254 – DESIGN AND ANALYSIS OF ALGORITHMS

Dynamic Programming

Presentation by
[Link] Sankari
AP/ AI&DS
 20IT254 – DESIGN AND ANALYSIS OF
ALGORITHMS
Module II : GREEDY ALGORITHM AND DYNAMIC
PROGRAMMING
9

Greedy Algorithm – General Characteristics – Shortest Path -

Knapsack problem – Task Scheduling Problem – Huffman Code
– Dynamic Programming: Calculating Binomial coefficient –
Knapsack problem – Chained matrix multiplication problem.

2
Dynamic Programming

3
 Definition
• technique for solving a complex problem by first breaking into
a collection of simpler subproblems, solving each subproblem
just once, and then storing their solutions to avoid repetitive
computations.

4
 Dynamic Programming
Greedy method and Dynamic Programming both used for optimization problem

Both are different strategy but the purpose is same

In greedy method, try to follow pre-defined procedure to get optimum results
 E.g:- shortest path – Dijstraks algorithm – always select shortest path vertex
and continuing relaxing the vertex to get the shortest path
In dynamic programming, try to find out all possible solutions then
pick optimal solution
It is little bit time consuming compared to greedy method

5
 Dynamic Programming
 For any problem there may many solution and pick best one.

 Mostly dynamic programming, are solved by using recursive formula though not
use recursion of programming but the formulas are recursive. If want, use recursion
also but mostly it solves using iteration.

 Dynamic Programming follows principles of Optimality

(principles of Optimality -The problem can be solved by taking sequence of

decisions to get a optimal solution)
(In greedy method decision take at one time (follow procedure)
(In Dynamic, every stage take decision )

6
 Dynamic Programming
 it is also used to solve optimization problems.

 But unlike greedy approach, dynamic programming always

ensures optimal / best solution

 The idea is to simply store the results of subproblems, so that

we do not have to re-compute them when needed later.

 This simple optimization reduces time complexities from

exponential to polynomial

7
 Properties - Dynamic
Programming
1. Optimal Substructure

A problem is said to have an optimal substructure if

we can formulate a recurrence relation for it.

8
 Properties - Dynamic
Programming
2. Overlapping
Subproblem

A problem is said to have an overlapping subproblem if the subproblems

reoccur when implementing a solution to the larger problem.

9
 Fibonacci Series
Each number in this series is equal to the sum of
previous numbers before it

10
Fibonacci Series – Optimal
Substructure
recurrence relation – optimal substructure

11
 Fibonacci Series – Overlapping
Subproblem
subproblems
recur

12
Ways to handle Overlapping
problem

13
Ways to handle Overlapping
problem

14
 Approaches of dynamic
programming

Memorization : Top down

Tabulation : Bottom up

15
Algorithm - Fibonacci

Recursive function of
Fibonacci term

Algorithm for Fibonacci

term (Recursive)

16
Normal
This is the tracing
tree of fib(5).
Total calls: 15

Recurrence
Equation :
T(n)= 2T(n-1)+1
O(2n)

17
 Memoization : Top down

To reduce O(2n)
Use array

Initially filled with -1

because nothing is known

Memoization

Convert exponentional to Only 6 calls , so fib(n)= n+1 calls

polynomial O(n)

18
 Tabulation : Bottom up

Use iterative method.

Th
i
ap s bo Using
p t
(fil roac tom- Loop
l
va from h. up
lue sm
) alle
r

19
 Divide and Conquer Dynamic Programming
Divide and conquer is the top down
Dynamic programming is bottom up approach.
approach.

Divide and conquer prefers recursion. Dynamic programming prefers iteration.

In divide and conquer, sub problems are Sub problems of dynamic programming are dependent
independent. and overlapping.

Solutions of sub problems are not stored. Solutions of sub problems are stored in the table.

Lots of repetition of work. No repetition at work at all.

It splits input at a specific point. It splits input at each and every possible point.

Less efficient due to rework. More efficient due to the saving of solution.

Sometimes, a solution using dynamic programming is

Solution using divide and conquer is simple.
complex and tricky.

Only one decision sequence is generated. Many decision sequences may be generated.

20
 Dynamic Programming Greedy Approach
It guarantees an optimal solution. It does not guarantee an optimal solution.
Sub problems in dynamic programming are
Sub problems in greedy algorithm do not overlap.
overlapping.
It does more work due to splitting of problem at It does little work due to splitting problem at specific
every possible point. points only.
It considers the future choices while selects the Only considers the current choice without looking
current choice. about future.
Construct the solution from the set of feasible
There is no specialized set of feasible choices.
solutions.
Select choice which is globally optimum. Select choice which is locally optimum.
Employ memorization. There is no concept of memorization.
Examples:
Examples: Binary Knapsack problem
Make a change problem Fractional knapsack problem
Knapsack problem Job scheduling problem
Assembly line scheduling Activity selection problem
Multistage graph Huffman Coding
Matrix chain multiplication Optimal storage on tapes
Optimal merge pattern

21
Calculating Binomial
coefficient

22
 Binomial Coefficient
A binomial coefficient refers to the way in which a number of objects may be
grouped in various different ways, without regard for order.

Consider the following example:

Example 1:Out of a group of three students (numbered 1-3), a professor may choose
any two of them to present a particular topic that they have gone over during the
school semester. This duo can involve a pairing of student 1 and 2, student 1 and 3, or
student 2 and 3. The order does not matter with regards to any one particular
grouping, which is to say the group labeled "Student 1 and 2", is no different from the
group labeled "Student 2 and 1".

23
 Binomial Notation
There are four distinct ways of writing binomial coefficient notation.

n is equal to the number of total distinct items, and k refers to the number of
particular items chosen from that total pool.

Example: If there are 10 locations on a map to choose from, and I commit to

visiting only 3 of them, then n would equal 10, and k would equal 3.

24
 Binomial Coefficients
It is defined as follows:

Example The number of possible ways to choose 2 objects from a

set of 5 objects is equal to

25
26
Example

27
28
29
30
 k
0 1 2 3 4 5 6
n

0 1

1 1 1

C(2,1) = C(2-1,1-1)+C(2-
2 1 2 1
1,1)
= C(1,0)+C(1,1)
3 1 1 = 1+1
=2
4 1 1
This tabular
5 1 1 representation of
binomial coefficients is
also known as Pascal’s
6 1 1 triangle.

31
32
Problem
Write a function that takes two parameters n and k and returns the
value of Binomial Coefficient C(n, k). For example, your function
should return 6 for n = 4 and k = 2, and it should return 10 for n =
5 and k = 2.

33
Algorithm

34
Analysis of Algorithm of calculating binomial
co-efficient

O(n)

O(k)

O(nk)

35
 DYNAMMIC
PROGRAMMING :
KNAPSACK PROBLEM

36
INTRODUCTION
Try possible solution and pick the optimal one
REAL TIME APPLICATION
Microwave
Grinder
Formula : Max ∑piwi

37
 What is the 0/1 Knapsack
Problem?
A bag (knapsack) with limited capacity
Several items with:
◦ Profit (value) PiP_iPi​
◦ Weight WiW_iWi​

Goal: maximize total profit without exceeding capacity.

0/1 means:
Either take the item (1)
Or leave it (0)
(No fractions allowed.)

38
 EXAMPLE – 0/1 Knapsack
M =8 P={1,2,5,6} -------- Profit
V[i,w] = max{V[i-1,w], V[i-1, w-w[i] +
N=4 W={2,3,4,5} --------- Weight P[i]}
Total solutions = 24 V[1,2] = max{V[0,2], V[0,2-1]+30}
For n objects = 2n Time complexity = =max{0,0+30} = 30
O(2n) -- too much of time
V[4,7] = max{V[3,7], V[3,7-5]+6}
Tabulation Method =max{7,1+6} = 7
0 1 2 3 4 5 6 7 8
V[4,8] = max{V[3,8], V[3,8-5]+6}
pi wi 0 0 0 0 0 0 0 0 0 0
=max{7,2+6} = 8
3 2 1 0 0 3 1 1 1 1 1 1
0 0 X1 x2 (2-2) x3 x4(8-6) =2
3 2
5 0 0 1 2 2 3 3 3 3
4 3 0 1 0 1 --------- max
0 0 0 1 2 5 5 6 7 7 profit
5 4
7 0 0 1 2 5 6 6 7 8
0
39
Given Data (From Slide) DP Formula :
Capacity M=8 V[i,w]=max(V[i−1,w],V[i−1,w−Wi​]
Number of items N=4 +Pi​)

Profits P=[1,2,5,6] For item i and capacity w:

Weights W=[2,3,4,5] We choose the maximum of:

Total Possible Solutions 1. Do not take item
Each item has 2 choices (take / not V[i−1,w]
take):
2. Take item
2 =2 =16
n 4

V[i−1,w−Wi​]+Pi​
Time complexity: O(2 )n

So we use Dynamic Programming.

40
Algorithm

41
Analysis of Knapsack Problem

O(n)

O(m)

O(n*m)

42
 Chained matrix
multiplication problem

43
 Matrix Chain multiplication is a dynamic Programming technique used
to find the most efficient way to multiply a given sequence of matrices.
The goal is to minimize the total number of scalar multiplications needed to
compute the product
Steps:
1. Problem Definition
[Link] Substructure
[Link] Case-M[i,i]=1
[Link]
Formula: M[i,j] = min{ M[i,k]+M[k+1,j] + pi-1*pk*pj

44
Problem
Consider
Matrix A Matrix B Matrix C

x =

5x4 4x3 5 x 3 = 15 elements

= 15 x 4 – because row and column
has 4 multiplication
= 60 multiplications
Condition : Number of Rows = Number of Columns
cost

45
Problem
A1 A2 A3 A4
5x 4x 6x 2x7
4 6 2

1. Need to multiply any two matrices

2. Need to choose matrices such that the cost is minimum
In Chained Matrix Multiplication
Necessity : To know how to multiply them

46
Solving without Dynamic
Programming
Some Possibilities,
((A1.A2))A3)A4
3
A4
multiplications

A3
On generalising,
T(n) = 2nCn/n+1
A1 A2 Eg : T(3) = 5

(A1*A2) *(A3*A4)

3
multiplications

A1 A2 A3 A4

47
Solving with Dynamic
Programming
M 1 2 3 4
A1 A2 A3 A4
1 0 12
5x 4x 6x 2x7 0
4 6 2
2 0 4
Initially considering two matrices 8
3 0 84
For A1, M(1,1)=0 similarly for M(2,2) M(3,3) & M(4,4)
4 0
S 1 2 3 4
For A1 * A2 = M(1,2) = 5 x 4 * 4 x 6 = 5x4x6 = 120
1 1
For A2 * A3 = M(2,3) = 4 x 6 * 6 x 2 = 4x6x2 = 48
2 2
For A3 * A4 = M(3,4) = 6 x 2 * 2 x 7 = 6x2x7 = 84 3 3
4

48
 Solving with Dynamic
Programming
M 1 2 3 4
A1 A2 A3 A4
1 0 12 8
5x 4x 6x 2x7 0 8
4 6 2
2 0 4
Now considering three matrices 8
3 0 84
For A1,A2&A3 => M(1,3)
4 0
S 1 2 3 4
2 possibilities
1 1 1
1. A1*(A2*A3) => M(1,1)+M (2,3) = 0+4888
2 2
(5x4) *((4x6)*(6*2)) =>5 x4x2= 40 Minimum
3
value is taken
2. (A1*A2)*A3 =>M(1,2)+M(3,3) = 120 +0 4
180
((5x4) *(4x6))*(6*2)) =>5x6x2 = 60

49
 Solving with Dynamic
Programming
M 1 2 3 4
A1 A2 A3 A4
1 0 12 88
5x 4x 6x 2x7 0
4 6 2
2 0 48 10
Next 4
3 0 84
For A2,A3&A4 => M(2,4)
4 0
2 possibilities S 1 2 3 4

1. A2*(A3*A4) => M(2,2)+M (3,4) = 0+84252 1 1 1

2 2 3
(4x6) *((6*2)*(2*7)) =>4x6x7=168 Minimum
value is taken 3 3
2. (A2*A3)*A4 =>M(2,3)+M(4,4) = 48+0
104 4
((4x6)*(6x2))*(2*7)) =>4x2x7 =56

50
 Solving with Dynamic
Programming
M 1 2 3 4
A1 A2 A3 A4
1 0 12 88 15
5x 4x 6x 2x7 0 8
4 6 2
2 0 48 10
Next using formula 4
For A1,A2,A3&A4 => M(1,4) 3 0 84
M(1,4) = min{ M(1,1)+M(2,4) + 5x4x7, 4 0
S 1 2 3 4
M(1,2)+M(3,4) +5x6x7,
1 1 1 3
M(1,3)+M(4,4) +5x2x7}
2 2 3
=min{0+104+140, 120+84+210, 88+0+70}
3 3
=min{184,404,158}
4
= 158

51
Representation
M[i,j] = min{ M[i,k]+M[k+1,j] + pi-1*pk*pj

S 1 2 3 4 M 1 2 3 4
1 1 1 3 1 0 12 88 15
0 8
2 2 3
2 0 48 10
3 3
4
4 3 0 84
From this, 4 0

(A1 * A2 * A3) * A4
(A1*(A2*A3)) * A4
A1 A2 A3 A4

52
Algorithm

53
Analysis of Chained Matrix

O(n)

O(n)

O(n)

O(n3)

54
55