Scribd
Upload
113 views21 pages

FADML 05 PPC Dynamic Programming PDF

This document discusses algorithm design using dynamic programming. It provides an overview of algorithm design techniques including divide and conquer, greedy algorithms, and dynamic programming. It then focuses on dynamic programming, explaining its core methods and how it can be applied to problems like Fibonacci sequences, matrix chain multiplication, string matching, longest common subsequence, and edit distance. Dynamic programming problems are formulated recursively and then solved using a bottom-up dynamic programming approach by filling out tables in an iterative manner to find optimal solutions. This allows for exponential recursive solutions to be solved in polynomial time by avoiding repeated work.

Uploaded by

arpan singh
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
113 views21 pages

FADML 05 PPC Dynamic Programming PDF

This document discusses algorithm design using dynamic programming. It provides an overview of algorithm design techniques including divide and conquer, greedy algorithms, and dynamic programming. It then focuses on dynamic programming, explaining its core methods and how it can be applied to problems like Fibonacci sequences, matrix chain multiplication, string matching, longest common subsequence, and edit distance. Dynamic programming problems are formulated recursively and then solved using a bottom-up dynamic programming approach by filling out tables in an iterative manner to find optimal solutions. This allows for exponential recursive solutions to be solved in polynomial time by avoiding repeated work.

Uploaded by

arpan singh
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/ 21

ALGORITHM DESIGN USING DYNAMIC

PROGRAMMING METHOD

Partha P Chakrabarti
Indian Institute of Technology Kharagpur
Overview of Algorithm Design
1. Initial Solution 1. Core Methods
a. Recursive Definition – A set of Solutions
a. Divide and Conquer
b. Inductive Proof of Correctness
c. Analysis Using Recurrence Relations b. Greedy Algorithms
2. Exploration of Possibilities c. Dynamic Programming
a. Decomposition or Unfolding of the Recursion Tree d. Branch-and-Bound
b. Examination of Structures formed e. Analysis using Recurrences
c. Re-composition Properties f. Advanced Data Structuring
3. Choice of Solution & Complexity Analysis 2. Important Problems to be addressed
a. Balancing the Split, Choosing Paths
b. Identical Sub-problems a. Sorting and Searching
4. Data Structures & Complexity Analysis b. Strings and Patterns
a. Remembering Past Computation for Future c. Trees and Graphs
b. Space Complexity d. Combinatorial Optimization
5. Final Algorithm & Complexity Analysis 3. Complexity & Advanced Topics
a. Traversal of the Recursion Tree
a. Time and Space Complexity
b. Pruning
b. Lower Bounds
6. Implementation
a. Available Memory, Time, Quality of Solution, etc c. Polynomial Time, NP-Hard
d. Parallelizability, Randomization
Basics of Dynamic Programming Method
Revising Fibonacci-like Structures
Fibonacci-like Structures (cntd.)
MATRIX CHAIN MULTIPLICATION Problem
(M1 X (M2 X (M3 X M4))) = ((M1 x M2) X (M3 X M4)) = (((M1 x M2) X M3) X M4) =
(M1 X (M2 X M3) ) X M4)
BUT THE NUMBER OF MULTIPLICATIONS TO GET THE ANSWER DIFFER !!

Let A be a [p by q] Matrix and B be a [q by r] Matrix. The number of multiplications needed to


compute A X B = p*q*r

Thus if M1 be a [10 by 30] Matrix, M2 be a [30 by 5] Matrix and M3 be a [5 by 60] Matrix

Then the number of computations for

(M1 X M2) X M3 = 10*30*5 for P = (M1 X M2) and 10*5*60 for P X M3. Total = 4500

M1 X (M2 X M3) = 30*5*60 for Q = (M2 X M3) and 10*30*60 for M1 X Q. Total = 27000
6
Matrix Chain Multiplication: Recursive Definition
MATRIX CHAIN MULTIPLICATION: RECURSIVE STRUCTURE
MIN NODE
(M1 :M4)
REC NODE (Fn)

(M1 :M4) (M1 :M4) (M1 :M4)

(M1 :M1) (M2 :M4) (M1 :M2) (M1 :M3) (M4 :M4)

(M2 :M4) (M2 :M4) (M1 :M3) (M1 :M3)

(M2 :M2) (M3 :M4) (M2 :M3) (M1 :M2) (M3 :M3)

(M1 X (M2 X (M3 X M4))) = ((M1 x M2) X (M3 X M4)) = (((M1 x M2) X M3) X M4) = (M1 X (M2 X M3) ) X M4)
M1 [10 by 30], M2 [30 by 5], M3 [5 by 60], M4 [60 by 4]
8
Matrix Chain Multiplication: Top-Down Evaluation
Matrix Chain Multiplication: Iterative Evaluation
String Matching Problems
Exact Pattern Matching in a String
Longest Common Subsequence (LCS)
LCS: Recursive Formulation
LCS: Dynamic Programming
LCS: Dynamic Programming Implementation
Edit Distance
Edit Distance: Formulation
Edit Distance using Dynamic Programming
Variations
Thank you
Any Questions?

You might also like