05: Dynamic programming

CS 473u - Algorithms - Spring 2005

February 6, 2005

1 Basic Idea - Partition Number

Definition 1.1 partition number: For a positive integer n, p(n) is the number of different
ways to represent n as a decreasing sum of positive integers.
6=6
6=5+1
6=4+2 6=4+1+1
6=3+3 6=3+2+1 6+3+1+1+1
6=2+2+2 6=2+2+1+1 6=2+1+1+1+1
6=1+1+1+1+1+1
Question: How to compute p(n)?

PartitionsI(num, d)//d-max digit

if (num ≤ 1) or (d = 1)
return 1
if d > num
d ← num
res ← 0
for i ← d downto 1
res+ =PartitionsI(num − i,i)
return res
Partitions(n)
return PartitionsI(n, n)

Question: What is the running time of Partitions(n)?

Running time of Partitions(n) is Θ(p(n)).

Easy to verify: √
n/4
3 ≤ p(n) ≤ nn
[Exercise: Prove those bounds (or better).]
In fact, Hardy and Ramanujan (1918) showed:

1
 √
eπ 2n/3
p(n) ≈ √
4n 3
Question: Is there a faster algorithm?

Question: Why is this algorithm so slowwwwwwwwwwwwwwwwww?

Answer:
Partitions(num, max digit) is called a lot of times with the same
parameters.

Idea: Cache results:

PartitionsI C(num, d)
if (num ≤ 1) or (max digit = 1)
return 1
if d > num
d ← num
if hnum, max digiti in cache
return cache(hnum, max digiti)
res ← 0
for i ← d downto 1
res+ =PartitionSI C(num − i,i)
cache(hnum, max digiti) ← res
return res
PartitionS C(n)
return PartitionsI C(n, n)

We implement cache using hash table.

Question: What is the running time of MPartitions C?
Question: How many entries are stored in the cache?
Question: What is the running time of MPartitions C?
Argument:

1. If a call to MPartitionsI C takes (by itself) more than constant time, then we
perform a store in the cache.

2. Number of store operations in the cache is O(n2 ).

3. We charge the work in the loop to the resulting store. The work in the loop is O(n).

4. Running time of MPartitions C(n) is O(n3 ).

Observation: Analysis is sloppy. Might be possible to do better.

Observation: Basic speedup idea is very generic...

2
1.1 Memoization:
Take a recursive function and cache the results as the computations goes on. Before trying
to compute a value, check if it was already computed and if it is already in the cache. If so,
return result from the cache.
If it is not in the cache, compute it and store it in the cache.
When does it work: When there is a lot of inefficiency in the computation of the recursive
function because we perform the same call again and again.
When it does NOT work:

1. When the number of different recursive function calls (i.e., the different values of the
parameters in the recursive call) is “large”.

2. When the function has side effects.

Question: Can we do better than caching?

More pain more gain:
In a lot of cases we can analyse the recursive calls, and store them directly in an array. This
technique is dynamic programming . We can sometime save space and improve running
time in dynamic programming over Memoization.

2 Dynamic programing made easy

1. Solve the problem using recursion - easy (?).

2. Modify the recursive program so that it caches the results.

3. Dynamic programming: Modify the cache into mutli-dim array.,

3 Fibonacci numbers
FibR(n)
if n ≤ 1
return 1
return F ibR(n − 1) + F ibR(n − 2)

Q: Running time of F ibR(n)?

O(Fn ) where Fn is the nth Fibonacci number.

" √ !n √ !n #
1 1+ 5 1− 5
Fn = √ + = Θ(φn )
5 2 2
√
1+ 5
φ=
2

3
 FibDP(n)
if n ≤ 1
return 1
if F [n] initialized
return F [n]
F [n] ⇐= F ibDP (n − 1) + F ibDP (n − 2)
return F [n]

Q: Running time of F ibDP (n)?

A:O(n)- linear.
Observe that we can fill the table in the other direction, and reduce space to O(1):

FibI(n)
prev ← 0, curr ← 1
for i = 1 to n
next ← curr + prev
prev ← curr
curr ← next
return curr

Running time of F ibI identical to the running time of F ibDP .

Q: Can we do better?
A: Yes.
    
y 0 1 x
=
x+y 1 1 y

      2    n−3  
fn−1 0 1 fn−2 0 1 fn−3 0 1 f2
= = =
fn 1 1 fn−1 1 1 fn−2 1 1 f1
 n−3
0 1
Thus, computing the nth Fibonacci number can be done by computing .
1 1
How to this quickly?
a*b*c=(a*b)*c=a*(b*c)

FastExp(a,n)
if n = 0 then return 1
if n = 1 then return a
if n is even then
return (F astExp(a, n/2))2
else

2
return a ∗ F astExp a, n−1
2

4
What is the running time of FastExp?
A:O(log n).
Thus, we can compute in fn is O(log n) time!
But... fn has ≈ log10 1.68...n = Θ(n) digits?
We assumed that the time to handle a number if O(1) which is not true in practice if the
numbers are large. Be careful with this assumption...

4 Edit Distance
Question 4.1 Given two strings A and B how many edit operations do I have to make to
turn A into B?
Example:
A =“har-peled”
B =“sharp eyed”
sharp eyed
Distance: 4

Operations:

1. Insert character.

2. Delete character.

3. Replace.

Price of each operation is one. How to compute the edit-distance (min # of edit operations
needed?
List the edit operations from left to right. Thus, edit distance is just an alignment
problem:
h a r - p e l e d
s h a r p <space> e y e d
1 0 0 0 1 0 1 0 1 0 0
Edit price: 4.
l l e
Insert: delete: replace ignore:
s y e
Idea: Let us look on the last character and decide which of the categories it falls into:

5
 ed(A[1..m], B[1..n])
if m = 0 return n
if n = 0 return m
pinsert = ed(A[1..m], B[1..(n − 1)]) + 1
pdelete = ed(A[1..(m − 1)], B[1..n]) + 1
pr/i = ed( A[1..(m
h − 1)], B[1..(n
i − 1)] )
+ A[m] 6= B[n]


return min pinsert , pdelete , preplace/ignore

Running time of ed(...)? Clearly exponential... At least 3n .

Q: How many different recursive calls ed performs?
A:O(m ∗ n) different calls.

edM(A[1..m], B[1..n])
if m = 0 return n
if n = 0 return m
if T [m, n] is initialized then
return T [m, n]
pinsert = edM (A[1..m], B[1..(n − 1)]) + 1
pdelete = edM (A[1..(m − 1)], B[1..n]) + 1h i
pr/i = edM (A[1..(m − 1)], B[1..(n − 1)]) + A[m] 6= B[n]


T [m, n] ← min pinsert , pdelete , preplace/ignore
return T [m, n]

Q: Running time of edM (...)?

A:O(m ∗ n).
Understanding what the algorithm really do:

6
 edDP(A[1..m], B[1..n])
for i=1 to m T [i, 0] ← i
for j=1 to n T [0, j] ← j
for i ← 1 to m
for j ← 1 to n
pinsert = T [i, j − 1] + 1
pdelete = T [i − 1, j] + 1 h i
pr/ignore = T [i − 1.j − 1] + A[i] 6= B[j]


T [i, j] ← min pinsert , pdelete , pr/ignore
return T [m, n]

Q: How to reduce the space to linear (instead of quadratic)?

A: Just compute the matrix two rows in a time.