Scribd
Upload
93 views

Final Ppts Daa Unit III Dynamic Programming

Dynamic programming is an algorithmic technique that breaks down a complex problem into subproblems. It solves each subproblem only once and stores the results for future use, avoiding recomputing the same subproblems. It is applicable when problems exhibit overlapping subproblems and optimal substructure. Some common problems solved using dynamic programming include knapsack, longest common subsequence, matrix chain multiplication, and travelling salesman. Dynamic programming follows the principle of optimality - the optimal solution to a problem depends on the optimal solution of its subproblems.

Uploaded by

djalok190109
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
93 views

Final Ppts Daa Unit III Dynamic Programming

Dynamic programming is an algorithmic technique that breaks down a complex problem into subproblems. It solves each subproblem only once and stores the results for future use, avoiding recomputing the same subproblems. It is applicable when problems exhibit overlapping subproblems and optimal substructure. Some common problems solved using dynamic programming include knapsack, longest common subsequence, matrix chain multiplication, and travelling salesman. Dynamic programming follows the principle of optimality - the optimal solution to a problem depends on the optimal solution of its subproblems.

Uploaded by

djalok190109
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 36

Unit-III

Abstract
Algorithms

Sub-DAA Class-TE Comp


Dynamic Programming
• Principal: Dynamic Programming is an algorithmic paradigm
that solves a given complex problem by breaking it into sub
problems and stores the results of sub problems to avoid
computing the same results again.
• Following are the two main properties of a problem that
suggest that the given problem can be solved using Dynamic
programming.
• 1) Overlapping Sub problems
• 2) Optimal Substructure

Sub-DAA Class-TE Comp


1) Overlapping Subproblems: Dynamic Programming is mainly
used when solutions of same subproblems are needed again and
again. In dynamic programming, computed solutions to
subproblems are stored in a table so that these don’t have to
recomputed.
2) Optimal Substructure: A given problems has Optimal
Substructure Property if optimal solution of the given problem
can be obtained by using optimal solutions of its subproblems.
The principle of optimality:-
Dynamic programming is a technique for finding an optimal
solution.
The principle of optimality applies if the optimal solution to a
problem always contains optimal solutions to all subproblems

Sub-DAA Class-TE Comp


Control Abstraction or Algorithm of Dynamic
Programming

Sub-DAA Class-TE Comp


Difference Between Divide & Conquer and Dynamic Programming

Sub-DAA Class-TE Comp


Difference Between Greedy Method and Dynamic
Programming

Sub-DAA Class-TE Comp


Application of Dynamic
Programming
 Matrix Chain Multiplication

 Longest Common Subsequence

 Travelling Salesman Problem

 Knapsack Problem

 OBST

 Multistage Graph.

Sub-DAA Class-TE Comp


TRAVELLING SALESPERSON PROBLEM

 Formula:-
 g (i, s) = min {cij + g (J, s – {J})}
 Time Complexity:-
 O (n 2n).
Sub-DAA Class-TE Comp
TRAVELLING SALESPERSON PROBLEM

Solution:-

Sub-DAA Class-TE Comp


Sub-DAA Class-TE Comp
Sub-DAA Class-TE Comp
Optimal Binary Search
Trees(OBST)
Formula:-
1) w(i,i)=q(i)
2) c(i,i)=0
3) r(i,i)=0
4) w(i,j)=p(j)+q(j)+w(i,j-1)
5) C(i,j)= min {c(i,k-1)+c(k,j)}+w(i,j) ….. i<k<=j
6) r(i,j)=k
7) r(i,i+1)=i+1
Sub-DAA Class-TE Comp
OBST Example

Sub-DAA Class-TE Comp


OBST Example
Solution:-
This computation is carried out row-wise from row 0 to row 4. Initially, W (i, i) = Q
(i) and C (i, i) = 0 and R (i, i) = 0, 0 < i < 4.
Start with i = 0; so j = 1; as i < k ≤ j, so the possible value for k = 1
W (0, 1) = P (1) + Q (1) + W (0, 0) = 3 + 3 + 2 = 8
C (0, 1) = W (0, 1) + min {C (0, 0) + C (1, 1)} = 8
R (0, 1) = 1 (value of 'K' that is minimum in the above equation).
Next with i = 1; so j = 2; as i < k ≤ j, so the possible value for k = 2
W (1, 2) = P (2) + Q (2) + W (1, 1) = 3 + 1 + 3 = 7
C (1, 2) = W (1, 2) + min {C (1, 1) + C (2, 2)} = 7
R (1, 2) = 2
Next with i = 2; so j = 3; as i < k ≤ j, so the possible value for k = 3

Sub-DAA Class-TE Comp


W (2, 3) = P (3) + Q (3) + W (2, 2) = 1 + 1 + 1 = 3
C (2, 3) = W (2, 3) + min {C (2, 2) + C (3, 3)} = 3 + [(0 + 0)] = 3
R (2, 3) = 3

Next with i = 3; so j = 4; as i < k ≤ j, so the possible value for k = 4

W (3, 4) = P (4) + Q (4) + W (3, 3) = 1 + 1 + 1 = 3


C (3, 4) = W (3, 4) + min {[C (3, 3) + C (4, 4)]} = 3 + [(0 + 0)] = 3
R (3, 4) = 4

Start with i = 0; so j = 2; as i < k ≤ J, so the possible values for k = 1 and 2.

W (0, 2) = P (2) + Q (2) + W (0, 1) = 3 + 1 + 8 = 12


C (0, 2) = W (0, 2) + min {(C (0, 0) + C (1, 2)), (C (0, 1) + C (2, 2))}
= 12 + min {(0 + 7, 8 + 0)} = 19
R (0, 2) = 1

Next, with i = 1; so j = 3; as i < k ≤ j, so the possible value for k = 2 and 3.

W (1, 3) = P (3) + Q (3) + W (1, 2) = 1 + 1+ 7 = 9


C (1, 3) = W (1, 3) + min {[C (1, 1) + C (2, 3)], [C (1, 2) + C (3, 3)]}
= W (1, 3) + min {(0 + 3), (7 + 0)} = 9 + 3 = 12
R (1, 3) = 2
Sub-DAA Class-TE Comp
Next, with i = 2; so j = 4; as i < k ≤ j, so the possible value for k = 3 and 4.
W (2, 4) = P (4) + Q (4) + W (2, 3) = 1 + 1 + 3 = 5
C (2, 4) = W (2, 4) + min {[C (2, 2) + C (3, 4)], [C (2, 3) + C (4, 4)]
= 5 + min {(0 + 3), (3 + 0)} = 5 + 3 = 8
R (2, 4) = 3
Start with i = 0; so j = 3; as i < k ≤ j, so the possible values for k = 1, 2 and 3.
W (0, 3) = P (3) + Q (3) + W (0, 2) = 1 + 1 + 12 = 14
C (0, 3) = W (0, 3) + min {[C (0, 0) + C (1, 3)], [C (0, 1) + C (2, 3)],[C (0, 2) + C (3, 3)]}
= 14 + min {(0 + 12), (8 + 3), (19 + 0)} = 14 + 11 = 25
R (0, 3) = 2
Start with i = 1; so j = 4; as i < k ≤ j, so the possible values for k = 2, 3 and 4.
W (1, 4) = P (4) + Q (4) + W (1, 3) = 1 + 1 + 9 = 11
C (1, 4) = W (1, 4) + min {[C (1, 1) + C (2, 4)], [C (1, 2) + C (3, 4)],[C (1, 3) + C (4, 4)]}
= 11 + min {(0 + 8), (7 + 3), (12 + 0)} = 11 + 8 = 19
R (1, 4) = 2

Sub-DAA Class-TE Comp


Start with i = 0; so j = 4; as i < k ≤ j, so the possible values for k = 1, 2, 3 and 4.
W (0, 4) = P (4) + Q (4) + W (0, 3) = 1 + 1 + 14 = 16
C (0, 4) = W (0, 4) + min {[C (0, 0) + C (1, 4)], [C (0, 1) + C (2, 4)],[C (0, 2) + C (3, 4)], [C (0, 3) + C (4, 4)]}

= 16 + min [0 + 19, 8 + 8, 19+3, 25+0] = 16 + 16 = 32


R (0, 4) = 2

Sub-DAA Class-TE Comp


0/1 – KNAPSACK PROBLEM
METHODE-1

Sub-DAA Class-TE Comp


Sub-DAA Class-TE Comp
OR
0/1 – KNAPSACK PROBLEM
FOR METHODE-1

Sub-DAA Class-TE Comp

You might also like