Chapter 8 introduction to The Design & Dynamic Programming Analysis of Algorithms 2ND EDITION Anany Levitin PEARSON Addison Wesley Copyright @ 2007 Pearson Addison-Wesley. All rights reserved
Chapter 8 Dynamic Programming Copyright © 2007 Pearson Addison-Wesley. All rights reserved
Dynamic Programming Dynamic Programming is a general algorithm design technique for solving problems defined by or formulated as recurrences with overlapping subinstances Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by cs °“ Programming” here means" planning” Main idea: set up a recurrence relating a solution to a larger instance to solutions of some smaller instances solve smaller instances once record solutions in a table extract solution to the initial instance from that table Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-1 Dynamic Programming Dynamic Programming is a general algorithm design technique for solving problems defined by or formulated as recurrences with overlapping subinstances • Invented by American mathematician Richard Bellman in the 1950s to solve optimization problems and later assimilated by CS • “Programming” here means “planning” • Main idea: - set up a recurrence relating a solution to a larger instance to solutions of some smaller instances - solve smaller instances once - record solutions in a table - extract solution to the initial instance from that table
Example: Fibonacci numbers Recall definition of fibonacci numbers: F(n)=F(n-1)+F(n=2) F(0)=0 F()=1 Computing the nth Fibonacci number recursively(top-down): F(n-2 F(2)+P(n-3)F(3)+F(n-4 Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-2
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-2 Example: Fibonacci numbers • Recall definition of Fibonacci numbers: F(n) = F(n-1) + F(n-2) F(0) = 0 F(1) = 1 • Computing the nth Fibonacci number recursively (top-down): F(n) F(n-1) + F(n-2) F(n-2) + F(n-3) F(n-3) + F(n-4)
Example: Fibonacci numbers(cont) Computing the nth Fibonacci number using bottom-up iteration and recording results F(0)=0 F(1) F(2)=1+0=1 F(n-2) F(n-1)= F(n)=F(n-1)+F(n-2) 01 F(n-2)F(n-1)F(n) Efficiency: time n What if we solve space n it recursively? Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-3 Example: Fibonacci numbers (cont.) Computing the n th Fibonacci number using bottom-up iteration and recording results: F(0) = 0 F(1) = 1 F(2) = 1+0 = 1 … F(n-2) = F(n-1) = F(n) = F(n-1) + F(n-2) Efficiency: - time - space 0 1 1 . . . F(n-2) F(n-1) F(n) n n What if we solve it recursively?
Examples of DP algorithms Computing a binomial coefficient Longest common subsequence Warshall's algorithm for transitive closure Floyd's algorithm for all-pairs shortest paths Constructing an optimal binary search tree Some instances of difficult discrete optimization problems: traveling salesman knapsack Copyright@ 2007 Pearson Addison-Wesley. All rights reserved. A Levitin "Intoduction b the Design& Analysis of Algorithms, 2nd ed, Ch 8 8-4
Copyright © 2007 Pearson Addison-Wesley. All rights reserved. A. Levitin “Introduction to the Design & Analysis of Algorithms,” 2 nd ed., Ch. 8 8-4 Examples of DP algorithms • Computing a binomial coefficient • Longest common subsequence • Warshall’s algorithm for transitive closure • Floyd’s algorithm for all-pairs shortest paths • Constructing an optimal binary search tree • Some instances of difficult discrete optimization problems: - traveling salesman - knapsack