Summarize the following text to main points and sub-points and make detailed explain for them:

CS311 
Algorithm Design and 
Analysis
LECTURE 6 : DYNAMIC PROGRAMMING
Contents
▪Fibonacci Numbers problem
▪Dynamic programming Definition
▪Rod-cutting problem
▪Top-down approach (Memoization)
▪Bottom-up approach
▪Dynamic programming steps
▪Elements of Dynamic Programming
▪Matrix Chain Multiplication Problem
▪Longest Common Subsequence problem
ALGORITHM DESIGN AND ANALYSIS
2
Fibonacci Numbers
▪  The Fibonacci numbers are the elements of the 
     sequence: 
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...... 
in his example of Breeding Rabbits.
▪  Computing the nth Fibonacci number recursively:
➢ F(n) = F(n-1) + F(n-2)
➢ F(0) = 0
➢ F(1) = 1
        
ALGORITHM DESIGN AND ANALYSIS
3
int Fib(int n)   
{
  if (n <= 1)
    return 1;
  else
    return Fib(n - 1) + Fib(n - 2);
}
Fibonacci Numbers
Fib(5)
    +
Fib(4)
    +
Fib(3)
    +
Fib(3)
    +
Fib(2)
    +
Fib(2)
    +
Fib(1)
    
Fib(2)
    +
Fib(1)
    
Fib(1)
    
Fib(0)
    
Fib(1)
    
Fib(0)
    
Fib(1)
    
Fib(0)
    
Dynamic programming
▪ Dynamic programming is typically applied to optimization problems.  In such problem 
there can be many solutions.  Each solution has a value, and we wish to find a solution 
with the optimal value. 
▪ Like the divide-and-conquer method, it solves problems by combining the solutions to 
subproblems. 
▪ Unlike divide and conquer, sub-problems are not independent. Sub-problems may share 
sub-sub-problems,
ALGORITHM DESIGN AND ANALYSIS
5
Dynamic programming
▪ Each subproblem is solved only once, saving its solution.
▪ During the computation, if we need the solution to a subproblem, we simply look it up 
rather than recomputing it.
▪ Two dynamic programming approaches:
➢Top-down approach (Memoization)
➢Bottom-up approach.
ALGORITHM DESIGN AND ANALYSIS
6
Fibonacci Numbers using dynamic programming
ALGORITHM DESIGN AND ANALYSIS
7
–
Computing the nth Fibonacci number using a bottom-up approach:
– F(0) = 0   ,  F(1) = 1 
– F(2) = 1+0 = 1
–   …  
– F(n) = F(n-1) + F(n-2)
• Efficiency:
– Time – O(n) 
 
 
- Space – O(n)
Dynamic programming vs Divide & Conquer
ALGORITHM DESIGN AND ANALYSIS
8
Rod-cutting problem
Problem: Given a rod of length n inches and a table of prices pi (i is in the range 1, 2, 
…, n), determine the maximum revenue rn obtained by cutting the rod and selling the 
pieces. If no cutting gives the best price, we don’t cut at all. 
Note that: there is no cost for cutting.
ALGORITHM DESIGN AND ANALYSIS
9
Rod-cutting problem
Given a rod of 4 inches,  we have 8 possible ways of cutting the rod.
We can cut the rod of length n in 2n-1 different ways.
ALGORITHM DESIGN AND ANALYSIS
10
Rod-cutting problem
ALGORITHM DESIGN AND ANALYSIS
11
For our sample problem, we can determine the optimal revenue figures ri, for i =1, 2, 3……10 
by inspection, with the corresponding optimal decompositions:
Rod-cutting problem
The optimal revenue from a rod of length n, rn
Where pn id the price with no cut at all, r1 + rn-1 is a cut so that we have rods of length 1 
and n-1.
ALGORITHM DESIGN AND ANALYSIS
12
Rod-cutting problem
General formula: 
Where pi is the price of rod of length i, rn-1 is the revenue from rod of length n-1.
            Recursive approach 
For n=4:
r4 = max (p1 + r3 ,
                   p2 + r2 , 
                   p3 + r1 ,
                   p4 + r0)
ALGORITHM DESIGN AND ANALYSIS
13
Recursive implementation
T(0) = 1
ALGORITHM DESIGN AND ANALYSIS
14
Recursive implementation
The running time of the recursive algorithm is exponential in n.
T(n) = 2n 
ALGORITHM DESIGN AND ANALYSIS
15
Top-down approach (Memoization)
ALGORITHM DESIGN AND ANALYSIS
16
Initializes a new array with -∞
Recursive vs Memoized Dynamic Programming
ALGORITHM DESIGN AND ANALYSIS
17
 
Θ(2n)  
 
 
 
 
 
 
 
 
 
Θ(n2)  
Bottom-up approach
Note that: subproblem i is smaller than subproblem j, so the problems are solved in the order 
0, 1, 2, 3,……n 
            T(n) = Θ(n2)
ALGORITHM DESIGN AND ANALYSIS
18
Reconstructing a Solution
▪ The three algorithms we gave return the total value of the optimal solution, but it does 
not return the solution itself. 
▪ We would like our algorithm to return the list of the sizes of the pieces in an optimal 
solution.
▪ We need a simple modification of the procedure that prints a solution. 
▪ It is usually the case with dynamic programming that we can reconstruct an optimal 
solution by slightly modifying the algorithm
ALGORITHM DESIGN AND ANALYSIS
19
Reconstructing a Solution
s[j] records the size of the first piece in an optimal solution to the subproblem of size j. 
ALGORITHM DESIGN AND ANALYSIS
20
Reconstructing a Solution
In our rod-cutting example, the call EXTENDED-BOTTOM-UP-CUT-ROD(p,10) 
would return the following arrays:
So the following procedure prints out an optimal solution:
 
 
 
 
 
 
 
ALGORITHM DESIGN AND ANALYSIS
21
➢Print-Cut-Rod-Solution(p, 10) 
     prints 10
➢Print-Cut-Rod-Solution(p, 9) 
prints 3 and 6
Dynamic programming steps
When developing a dynamic-programming algorithm, we follow a sequence of four steps:
1. Characterize the structure of an optimal solution. (slide 12)
2. Deduce from it a recurrence relation for the value of an optimal solution. (slide 13)
3. Compute the value of an optimal solution, typically using Top-down approach (slide 16)
     or using Bottom-up approach. (slide 18) 
4. If you need an optimal solution (not just its value), then construct an optimal solution 
from computed information. (slide 20)
ALGORITHM DESIGN AND ANALYSIS
22
Elements of Dynamic Programming
When should we look for a dynamic programming solution to a problem?
Two key ingredients that an optimization problem must have :
1. Optimal substructure: a problem exhibits optimal substructure if an optimal solution to 
the problem contains within it optimal solutions to subproblems.
2. Overlapping subproblems: When a recursive algorithm revisits the same problem 
repeatedly, we say that the optimization problem has overlapping subproblems.
In other words: The number of unique subproblems < The number of the total subproblems.
ALGORITHM DESIGN AND ANALYSIS
23
Matrix Chain Multiplication Problem
Problem: We are given a sequence (chain) ‹ A1,A2, …. , An › of n matrices to be 
multiplied, and we wish to compute the product A1 × A2 × A3 × · · · × An that minimizes 
the number of scalar multiplications.
ALGORITHM DESIGN AND ANALYSIS
24
Number of Multiplications = 4 * 6 * 3 = 72
Matrix Chain Multiplication Problem
In what order should we multiply the matrices  A1  A2  An ?
Parenthesize the product to get the order in which matrices are multiplied.
E.g.: A1  A2  A3 
= ((A1  A2)  A3)
  
 
   OR    = (A1  (A2  A3))
Which one of these orderings should we choose?
The order in which we multiply the matrices has a significant impact on the cost of 
evaluating the product.
ALGORITHM DESIGN AND ANALYSIS
25
Example
A1: 10 x 100     ,    A2: 100 x 5      ,     A3: 5 x 50
Solution 1 : ((A1  A2)  A3): 
  A1  A2 = 10 x 100 x 5 = 5,000 multiplications 
  
 
 
                ((A1  A2)  A3) = 10 x 5 x 50 = 2,500 multiplications 
         Total: 7,500 scalar multiplications
 Solution 2 : (A1  (A2  A3)): 
 A2  A3 = 100 x 5 x 50 = 25,000 
  
 
 
               (A1  (A2  A3)) = 10 x 100 x 50 = 50,000
         Total: 75,000 scalar multiplications
10 X 5
100 X 50
ALGORITHM DESIGN AND ANALYSIS
26
Matrix Chain Parenthesization Problem
▪ We write: Aij for the product Ai × Ai+1 × · · · × Aj 
▪ There is a final matrix multiplication: A1k × A(k+1)n , for some 1 ≤ k ≤ n − 1. 
▪ we obtain the recurrence:
How many Parenthesizations P(n) are there when n=4?
 
ALGORITHM DESIGN AND ANALYSIS
27
Matrix Chain Parenthesization Problem
A Bound on the number of Parenthesizations:
➢   The number of parenthesizations grows as :                     
➢   The brute force method :  4n => Exponential 
➢   A better way: use the dynamic-programming method to determine how to optimally 
parenthesize a matrix chain. 
ALGORITHM DESIGN AND ANALYSIS
28
Optimal Substructure
▪  Given a chain of matrices A1, A2, …, An, where Ai has dimensions pi-1x pi, 
 
 
A1     ×    A2          Ai   ×    Ai+1        An 
 
         p0 x p1    p1 x p2     pi-1 x pi    pi x pi+1     pn-1 x pn
▪  The optimal solution can be defined in terms of optimal sub-problems.
▪  Suppose that an optimal parenthesization of Ai…j splits the product into:
(Ai…k) and (Ak+1…j)   where       i  k < j
▪  We want to find at which k we can return the fewest number of multiplications.
ALGORITHM DESIGN AND ANALYSIS
29
Recursive Solution
▪  Let m[i, j] = the minimum number of multiplications needed to compute Ai…j
▪  Assume that the optimal parenthesization splits the product Ai  Aj at k: 
Ai…j  = Ai…k Ak+1…j         for i  k < j
m[i, j] =   
ALGORITHM DESIGN AND ANALYSIS
30
m[i, k] 
+       m[k+1, j]       +       pi-1pkpj
min # of multiplications 
to compute Ai…k
# of multiplications 
to compute Ai…kAk…j
min # of multiplications 
to compute Ak+1…j
m[i, k]
m[k+1,j]
pi-1pkpj
Recursive Solution
Example :  
 
 
  

Summary :