AURORA DEEMED TO BE

UNIVERSITY
DEPARTMENT OF
COMPUTER SCIENCE AND ENGINEERING

Design and Analysis of Algorithms

U.G. - [Link]. CSE (AIML)
Academic Year : 2025-26
Junior Year
Term - I
Module - IV
Dr. K. CHANDRASHEKAR
8/4/2025 ASSOCIATE PROFESSOR, CSE 1
AURORA UNIVERSITY
 Module – IV
Dynamic Programming
 General Method

 Applications

 Multistage Graphs

All Pairs Shortest Path Problem

Optimal Binary Search Trees

8/4/2025 2
 Dynamic Programming
Dynamic Programming is an algorithm design method

that can be used when the solution to a problem may

be viewed as the result of a sequence of decisions

8/4/2025 3
 Introduction
● Invented by US Mathematician Richard Bellman in 1950
● Typically applied to optimization problems

● Like the divide-and-conquer method, dynamic

programming solves problems by combining the solutions
of sub problems

● Moreover, the Dynamic Programming algorithm solves

each sub-problem just once and then saves its answer in a
table, thereby avoiding the work of re-computing the
answer every time
8/4/2025 4
 Principle of Optimality
● In an Optimal sequence of decisions, each

subsequence must also be optimal i.e., whatever the

initial state & decisions are, the remaining decisions

must constitute an optimal decision sequence

● Dynamic programming obtain the solution using

“Principle of optimality”
8/4/2025 5
Approaches of Dynamic Programming

8/4/2025 6
 General Method

8/4/2025 7
 General Method
• Two (02) main properties of a problem suggest that the

given problem can be solved using Dynamic Programming

• These properties are

1. Overlapping Sub-Problems

2. Optimal Sub-Structure

8/4/2025 8
 Overlapping Sub-Problems
• Similar to Divide-and-Conquer approach,
Dynamic Programming also combines solutions to sub-problems
• It is mainly used where the solution of one sub-problem is needed
repeatedly
• The computed solutions are stored in a table, so that these don’t have to
be re-computed
• Hence, this technique is needed where overlapping sub-problem exists
• For example, binary search does not have overlapping sub-problem and
hence dynamic programming is not appropriate for binary search
• Whereas recursive program of Fibonacci numbers have many
overlapping sub-problems and hence dynamic programming is
appropriate
8/4/2025
for Fibonacci sequence 9
 Optimal Sub-Structure
• A given problem has optimal sub-structure property, if

the optimal solution of the given problem can be

obtained using optimal solutions of its sub-problems

• The standard All Pair Shortest Path algorithms like

Floyd-Warshall and Bellman-Ford are typical examples

of Dynamic Programming due to the optimal sub-

structures
8/4/2025 10
Steps of Dynamic Programming Approach

Dynamic Programming algorithm is designed using the

following four (04) steps:
• Characterize the structure of an optimal solution
• Recursively define the value of an optimal solution
• Compute the value of an optimal solution, typically in
a bottom-up fashion
• Construct an optimal solution from the computed
information
8/4/2025 11
 Solving DP Problems

8/4/2025 12
 Applications

8/4/2025 13
 Applications of Dynamic Programming Approach

 Multi-stage Graphs

 All Pairs Shortest Path Problem

 Optimal Binary Search Trees (OBST)

8/4/2025 14
 Multi-stage Graphs

8/4/2025 15
 Multi-stage Graphs
• To find a shortest path in a multi-stage graph
3 2 7

1 4
S A B 5
T

5 6

• Applying the Greedy Method,

the shortest path from S to T :

1+2+5=8

8/4/2025 16
 Shortest Path in Multi-stage Graphs
4
A D
1 18
11 9

2 5 13
S B E T
16 2

5
C 2
F

• The greedy method can not be applied to this case:

(S, A, D, T) 1 + 4 + 18 = 23

• The real shortest path is:

(S, C, F, T) 5+2+2=9
8/4/2025 17
 Dynamic Programming Approach
Forward Approach ( Backward Reasoning )
4
A D 1 A
1 18 d (A , T )
11 9

2 5 13 2 d (B , T )
S B E T S B T
16 2

5 d (C , T )
5
C 2
F C

• d (S, T) = min{ 1 + d (A, T), 2 + d (B, T), 5 + d (C, T)}

 d (A,T) = min{ 4 + d (D, T), 11 + d (E, T) }

= min{4 + 18, 11 + 13} = 22

4
A D
d(D, T)

11
E T
d(E, T)
8/4/2025 18
• d (B, T) = min { 9 + d (D, T), 5 + d (E, T), 16 + d(F, T)}

= min { 9 + 18, 5 + 13, 16 + 2} = 18

4
A D 9 D
1 18 d(D, T)
11 9

5 d(E, T)
S
2
B
5
E
13
T B E T
16 2
d(F, T)
16
5 F
C 2
F

• d (C, T) = min { 2 + d (F, T) } = 2 + 2 = 4

• d (S, T) = min { 1 + d (A, T), 2 + d (B, T), 5 + d (C, T) }

= min { 1 + 22, 2 + 18, 5 + 4} = 9

• The above way of reasoning is called backward reasoning

8/4/2025 19
 Backward Approach ( Forward Reasoning )
• d (S, A) = 1 A
4
D
1 18
11 9
d (S, B) = 2
2 5 13
S B E T
d (S, C) = 5 16 2

5
C 2
F

• d (S, D) = min {d (S, A) + d (A, D), d (S, B) + d (B, D)}

= min { 1 + 4, 2 + 9 } = 5

d (S, E) = min {d (S, A) + d (A, E), d (S, B) + d (B, E)}

= min { 1 + 11, 2 + 5 } = 7

d (S, F) = min {d (S, B) + d (B, F), d (S, C) + d (C,F)}

8/4/2025 20
= min { 2 + 16, 5 + 2 } = 7
 • d (S, T) = min { d (S, D) + d (D, T),

d (S, E) + d (E, T),

d (S, F) + d(F, T) }

= min { 5 + 18, 7 + 13, 7 + 2 }

=9
4
A D
1 18
11 9

2 5 13
S B E T
16 2

5
C 2
F
8/4/2025 21
 All Pairs Shortest Path Problem

8/4/2025 22
 All Pairs Shortest Path Problem
● The all pair shortest path algorithm, also known as

Floyd - Warshall algorithm, is used to find all pair

shortest path problems 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

23
8/4/2025
 All Pairs Shortest Path Problem
● Floyd - Warshall Algorithm is an algorithm for finding

the shortest path between all the pairs of vertices in a

weighted graph

● This algorithm works for both the directed and

undirected weighted graphs

● But, it does not work for the graphs with negative

cycles

24
8/4/2025
 All Pairs Shortest Path Problem
Follow the steps below to find the shortest path between
all the pairs of vertices:
1. Create a matrix A0 of dimension n*n where ‘n’ is the
number of vertices
2. The row and the column are indexed
as i and j respectively, where ‘i’ and ‘j’ are the
vertices of the graph
3. Each cell A [i ] [j] is filled with the distance from
the ith vertex to the jth vertex
4. If there is no path from ith vertex to jth vertex, the cell
is left as infinity
25
8/4/2025
 All Pairs Shortest Path Problem
5. Now, create a matrix A1 using matrix A0
i) The elements in the first column and the first row
are left as they are
ii) The remaining cells are filled in the following way :
Let ‘k’ be the intermediate vertex in the shortest path
from source to destination
In this step, k is the first vertex. A[i][j] is filled with
( A[i][k] + A[k][j]) if ( A[i][j] > A[i][k] + A[k][j] )
6. Repeat the process for all the vertices
26
8/4/2025
 Floyd's Algorithm using n+1 D matrices
Floyd // Computes shortest distance between all pairs of nodes
// and saves P to enable finding shortest paths
1. D0  W // initialize D array to W [ ]
2. P  0 // initialize P array to [0]
3. for k  1 to n
4. do for i  1 to n
5. do for j  1 to n
6. if (Dk-1[ i, j ] > Dk-1 [ i, k ] + Dk-1 [ k, j ] )
7. then Dk[ i, j ]  Dk-1 [ i, k ] + Dk-1 [ k, j ]
8. P[ i, j ]  k;
9. else Dk[ i, j ]  Dk-1 [ i, j ]

8/4/2025 27
 Example - 1
Given the graph and the weight matrix
1 2 3
1 0 4 5
W= D0 =
2 2 0 
1 5
3  -3 0
4 2 3
1 2 3
-3 1 0 0 0
2
P= 2 0 0 0
3 0 0 0

8/4/2025 28
 1 1 2 3
5 D0 =
1 0 4 5
4 3 k=1
2 2 
2 0 Vertex 1 can be
-3
2 3  -3 0 intermediate node
1 2 3
1 0 4 5
D1[2,3] = min( D0[2,3], D0[2,1]+D0[1,3] )
D1 = 2 2 0 7 = min (, 7)
3  -3 0 =7

1 2 3
1 0 0 0 D1[3,2] = min( D0[3,2], D0[3,1]+D0[1,2] )
= min (-3,)
P= 2 0 0 1
= -3
3 0 0 0

8/4/2025 29
 1 2 3
1 5 D1 = 1
0 4 5
4 3 2 2 0 7 k=2
2
Vertex 2 can be
2
-3 3  -3 0
intermediate node
1 2 3
1 0 4 5
D2[1,3] = min( D1[1,3], D1[1,2]+D1[2,3] )
D2 = 2 2 0 7 = min (5, 4+7)
3 -1 -3 0 =5

1 2 3
1 0 0 0 D2[3,1] = min( D1[3,1], D1[3,2]+D1[2,1] )
= min (, -3+2)
P= 2 0 0 1
= -1
3 2 0 0

8/4/2025 30
 1 1 2 3
5 D2 =
1 0 4 5
4 3
2 2 2 0 7 k=3
2
-3 Vertex 3 can be
3 -1 -3 0
intermediate node
1 2 3
1 0 2 5
D3[1,2] = min(D2[1,2], D2[1,3]+D2[3,2] )
D3 = 2 2 0 7 = min (4, 5+(-3))
3 -1 -3 0 =2

1 2 3
1 0 3 0 D3[2,1] = min(D2[2,1], D2[2,3]+D2[3,1] )
= min (2, 7+ (-1))
P= 2 0 0 1
=2
3 2 0 0

8/4/2025 31
 Example - 2

Given the weight matrix and the graph

1 2 3 4 5 1
1 0 1  1 5 3 v1 v2
9
2 9 0 3 2  5
1 3
2
3   0 4  v5
3
4   2 0 3 v4 42 v3

5 3    0

Practice at Home
8/4/2025 32
Complexity of Floyd Warshall Algorithm
Time Complexity

Since, there are three loops and each loop has constant complexities

Hence, the time complexity of the Floyd-Warshall algorithm is O ( n3 )

Space Complexity

Since, it uses weighted matrix for storing the values

Hence, the space complexity of the Floyd - Warshall algorithm is O ( n2 )

33
8/4/2025
Applications of Floyd Warshall Algorithm

 To find the shortest path in a directed graph

 To find the transitive closure of directed graphs

 To find the Inversion of real matrices

34
8/4/2025
 Optimal Binary Search Trees

8/4/2025 35
 Optimal Binary Search Trees
o An optimal binary search tree is a BST, which has minimal
expected cost of locating each node
o In many applications, the cost of searching is important
o Hence, it is required that the overall cost of searching should
be as minimum as possible
o The search time of BST is more than the Balanced Binary
Search Tree, as the Balanced Binary Search tree has less
number of levels than the BST
o There is one way which can further reduce the cost than the
Balanced BST, which is Optimal Binary Search Tree 36
8/4/2025
 OBST Algorithm

37
8/4/2025
 Importance of OBST Algorithm
o Search time of an element in a BST is O(n)

o Search time of an element in a Balanced-BST search time is O(log n)

o The search time can be further improved in Optimal Cost Binary

Search Tree, placing the most frequently used data in the root and

closer to the root element, while placing the least frequently used

data near leaves and in leaves

38
8/4/2025
 Example
Consider the following example:

Note: No. of Binary Trees formed using ‘n’ nodes is

(2nCn)/(n+1) * n!
No. of Binary Search Trees (Unlabeled Binary Trees)
formed using ‘n’ nodes is (2nCn)/(n+1)
39
8/4/2025
 The following are 5 various possible Binary Search
Trees of the above data and also the overall cost for
searching for each BST

The cost is computed by multiplying each node’s

frequency with the level of the tree and then add them
to compute the overall cost of BST
40
8/4/2025 Note : Here we are assuming that the tree starts from level 1
o The 4th BST cost is less than the cost of the 2nd BST and

its cost is the least among all, though 2nd BST is balanced

and the 4th BST is not balanced

o Hence, it is the Optimal Binary Search Tree for the given

data 41
8/4/2025
o Note that if the number of nodes are less, then we can find optimal

BST by checking all possible arrangements

o But if the nodes are greater than 3 like 4,5,6….. then respectively

14,42,132….., different BSTs are possible

o Checking all arrangements to find optimal cost may lead to

extra overhead

o Hence, we need another approach to solve the problem of optimal BST

using dynamic programming approach

42
8/4/2025
 Formulae to be used for OBST

43
8/4/2025
 Procedure to be applied for OBST
1. Construct a table with ‘ i ’ values at the column

ranging from 0 to n and ‘ j-i ’ values at the row

ranging from 0 to n
2. Compute w (i , j), c (i, j) and r (i, j) for all the

combinations
3. For ‘n’ nodes, proceed with r (0, n)
Construct a tree with r (i, j) = k to r (i, k-1) and r (k, j)
4. Repeat the process until we get r (i, i) = r (j, j) = 0
for all the nodes 44
8/4/2025
 Example
Let n = 4, Using algorithm OBST
compute c (i, j) 0 ≤ i ≤ j ≤ 4 for the identifier set
(a1, a2, a3, a4) = (do, if, int, while)
with p (1 : 4) = (3, 3, 1, 1) and q (0 : 4) = (2, 3, 1, 1, 1)

Initially, we have
w (i, i) = q(i)
c (i, i) = 0
r (i, i) = 0
45
8/4/2025
 Formulae to be used for OBST

46
8/4/2025
 Procedure to be applied for OBST

47
8/4/2025
 Optimal Binary Search Tree

48
8/4/2025
 Bibliography
“Fundamentals of Computer Algorithms”, Ellis Horowitz, Sartaj Sahni, Sanguthevar

Rajasekaran, Second Edition, Universities Press, 2008, ISBN: 978-8173716126.

“Algorithm Design: Foundations, Analysis, and Internet Examples”, Michael T.

Goodrich, Roberto Tamassia, , Second Edition, John Wiley, 2009, ISBN: 978-

8126509867.

“Introduction to Algorithms”, Thomas H Cormen, Charles E. Lieserson, Ronald L

Rivest and Clifford Stein, Fourth Edition, MITPress, 2022, ISBN: 978-0262046305.

“Algorithm Design”, Jon Kleinberg and ÉvaTardos, First Edition, Pearson, 2005,

ISBN: 978-0321295354.

“Algorithms – A Creative Approach”, Udi Manber, First Edition, Addison-Wesley,

1989, ISBN: 978-0201120370.

8/4/2025 49
 ALL THE BEST - DEAR STUDENTS
HOPE FOR GOOD ACADEMIC RESULTS

Dr. K. CHANDRASHEKAR
8/4/2025 ASSOCIATE PROFESSOR, CSE 50
AURORA UNIVERSITY