Analysis & Design
of Algorithms
Agenda
• Ch3: Dynamic Programming
o Fibonacci Sequence
o Rod Cutting
2
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.
3
Dynamic
Programming
• Dynamic programming
( like the divide-and-conquer method )solves
problems by combining the solutions to sub
problems.
• A dynamic-programming algorithm solves each
subsub problem just once and then saves its answer
in a table, thereby avoiding the work of
recomputing the answer every time it solves each
subsub problem.
4
Dynamic
Programming
5
Dynamic
Programming
• When developing a dynamic-programming
algorithm,
we follow a sequence of four steps:
1. Characterize the structure of an optimal solution.
2. Recursively defines the value of an optimal solution.
3. Compute the value of an optimal solution, typically
in a bottom-up fashion.
4. Construct an optimal solution from computed
information.
6
Fibonacci Sequence
• 0, 1, 1, 2, 3, 5, 8, 13, 21, …
• fib(1) = 1. f(7)
• fib(2) = 1. f(6) f(5)
• fib(N) = f(N-1) + f(N-2)
if N > 2. f(5) f(4) f(4) f(3)
fib(int n) { f(4) f(3)f(3) f(2)f(3) f(2) f(2) f(1)
if n == 1 or n ==2
return 1 … … … 1 f(2) f(1) 1 1 1
else
return fib(n-1) + fib(n-2)
} f(n) takes exponential time
to compute. [O(2n)].
7
Fibonacci Tree Traversal
Fib(6)
Fib(5) Fib(4)
Fib(4) Fib(3)
Fib(3) Fib(2)
Fib(2) Fib(1)
Fib(1)
Memoization
Memoizationis one way to deal with overlapping
subproblems (Top-Down)
After computing the solution to a subproblem, store in a
table
Subsequent calls just do a table lookup
Can modify recursive algorithm, to use memoziation:
Lets do this for the Fibonacci sequence
Fib(n) = Fib( n-1) + Fib( n-2)
Fib(2) = Fib(1) = 1
Fibonacci Sequence
arr[max]
Fib(int n)
{
if n == 1 or n ==2
return 1
if arr[n] is null
arr[n] = fib(n-1) + fib(n-2);
return arr[n];
}
Complexity: O(n)
Rod Cutting
• Maximal subarray is a relatively simple DP program
o At any step, finding the optimal solution requires an optimal solution to
only one subproblem.
• A more interesting problem is Rod Cutting
o Finding an optimal solution requires solutions to multiple subproblems.
• Problem: Find best way to cut a rod of length n
o Given: rod of length n
o Assume that each length rod has a price pi
o Find best set of cuts to get maximum price
• Each cut is integer length
• Can use any number of cuts, from 0 to n−1
• No cost for a cut
• Reward for No Cut = 0
11
Rod Cutting
n =4
12
Rod Cutting
• The 8 possible ways of cutting up a rod of length 4.
• Above each piece is the value of that piece,
according to the sample price chart.
• The optimal strategy is part (c) cutting the rod into
two pieces of length 2 which has total value10.
13
Recursive top-down solution
rn = max ( pi + rn-i ) , for all 1 ≤ i ≤ n
14
Recursive top-down solution
rn = max ( pi + rn-i ) , for all 1 ≤ i ≤ n
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
r2 = max ( p1+r1 , p2+r0 )
r1 = max ( p1+r0 )
15
Recursive top-down solution
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
r2 = max ( p1+r1 , p2+r0 )
r1 = max ( p1+r0 ) = max( 1 + 0 ) = 1
16
Recursive top-down solution
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
r2 = max ( p1+r1 , p2+r0 ) = max (1+1 , 5+0) = 5
r1 = max ( p1+r0 ) = max( 1 + 0 ) = 1
17
Recursive top-down solution
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
= max ( 1+5 , 5+1 , 8+0 ) = 8
r2 = max ( p1+r1 , p2+r0 ) = max (1+1 , 5+0) = 5
r1 = max ( p1+r0 ) = max( 1 + 0 ) = 1
18
Recursive top-down solution
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
= max (1+8 , 5+5 , 8+1 , 9+0 ) =10
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
= max ( 1+5 , 5+1 , 8+0 ) = 8
r2 = max ( p1+r1 , p2+r0 ) = max (1+1 , 5+0) = 5
r1 = max ( p1+r0 ) = max( 1 + 0 ) = 1
19
Recursive top-down solution
rn = max ( pi + rn-i ) , for all 1 ≤ i ≤ n
r4 = max ( p1+r3 , p2+r2 , p3+r1 , p4+r0 )
= max (1+8 , 5+5 , 8+1 , 9+0 ) = 10
r3 = max ( p1+r2 , p2+r1 , p3+r0 )
= max ( 1+5 , 5+1 , 8+0 ) = 8
r2 = max ( p1+r1 , p2+r0 ) = max (1+1 , 5+0) = 5
r1 = max ( p1+r0 ) = max( 1+0 ) = 1
20
Recursive top-down solution
Time Complexity: O(n2)
21
Recursive top-down solution
static int cutRod(int price[], int n)
{
if (n <= 0)
return 0;
int max_val = Integer.MIN_VALUE;
for (int i = 0; i < n; i++)
max_val = Math.max(max_val, price[i] + cutRod(price, n - i - 1));
return max_val;
}
22
Rod Cutting
• for i = 1,2, … ,10, by inspection, with the corresponding optimal
decompositions
• r1 = 1 from solution 1 = 1 (no cuts) ;
• r2 = 5 from solution 2 = 2 (no cuts) ;
• r3 = 8 from solution 3 = 3 (no cuts) ;
• r4 = 10 from solution 4 = 2 + 2 ;
• r5 = 13 from solution 5 = 2 + 3 ;
• r6 = 17 from solution 6 = 6 (no cuts) ;
• r7 = 18 from solution 7 = 1 + 6 or 7 = 2 + 2 + 3 ;
• r8 = 22 from solution 8 = 2 + 6 ;
23
Rod Cutting
24
Questions & Answers
