Algorithms Week 5
Ljubomir Perkovi ́c, DePaul University
Fibonacci numbers
One of the most famous sequences of numbers is the Fibonacci sequence:
0,1,1,2,3,5,8,13,21,34,…
Fibonacci numbers
One of the most famous sequences of numbers is the Fibonacci sequence:
0,1,1,2,3,5,8,13,21,34,… The sequence can be defined recursively:
1 ifn=0orn=1 F(n)= F(n−1)+F(n−2) ifn≥2
Fibonacci numbers
One of the most famous sequences of numbers is the Fibonacci sequence:
0,1,1,2,3,5,8,13,21,34,… The sequence can be defined recursively:
1 ifn=0orn=1 F(n)= F(n−1)+F(n−2) ifn≥2
The Fibonacci numbers have various interesting properties, including being related to the golden ratio and its conjugate:
√√
φ= 1+ 5 ≈1.61803 φˆ= 1− 5 ≈−0.61803
√ You could prove by induction that F(n) = φn−φˆn .
22
5
Fibonacci number recursive algorithm
The obvious algorithm for computing F(n):
Fib(n)
if n = 0 or n = 1
return 1 else
return Fib(n-1) + Fib(n-2)
Fibonacci number recursive algorithm
The obvious algorithm for computing F(n):
Fib(n)
if n = 0 or n = 1
return 1 else
return Fib(n-1) + Fib(n-2)
What is the running time T(n) of this algorithm on input n?
Fibonacci number recursive algorithm
The obvious algorithm for computing F(n):
Fib(n)
if n = 0 or n = 1
return 1 else
return Fib(n-1) + Fib(n-2)
What is the running time T(n) of this algorithm on input n? T (n) = T (n − 1) + T (n − 2) + Θ(1).
Running time
Consider the recursion tree for F(n): F(n)
F (n − 2)
F (n − 4) F (n − 3)
F(n−5) F(n−4)
F (n − 1)
F (n − 3) F (n − 2)
F(n−5) F(n−4) F(n−4) F(n−3)
F(n−5) F(n−4)
Running time
Consider the recursion tree for F(n): F(n)
F (n − 2)
F (n − 4)
F (n − 3)
F (n − 1)
F (n − 3) F (n − 2)
F(n−5) F(n−4) F(n−4) F(n−3)
F(n−5) F(n−4)
F(n−5) F(n−4)
Insights:
Running time
Consider the recursion tree for F(n): F(n)
F (n − 2)
F (n − 4)
F (n − 3)
F (n − 1)
F (n − 3) F (n − 2)
F(n−5) F(n−4) F(n−4) F(n−3)
F(n−5) F(n−4)
F(n−5) F(n−4)
Insights:
• The number of recursive calls at depth i is 2i
Running time
Consider the recursion tree for F(n): F(n)
F (n − 2)
F (n − 4)
F (n − 3)
F (n − 1)
F (n − 3) F (n − 2)
F(n−5) F(n−4) F(n−4) F(n−3)
F(n−5) F(n−4)
F(n−5) F(n−4)
Insights:
• The number of recursive calls at depth i is 2i
• The shallowest leaf is the leftmost one, with depth n . 2
Running time
Consider the recursion tree for F(n): F(n)
F (n − 2)
F (n − 4)
F (n − 3)
F (n − 1)
F (n − 3) F (n − 2)
F(n−5) F(n−4) F(n−4) F(n−3)
F(n−5) F(n−4)
F(n−5) F(n−4)
Insights:
• The number of recursive calls at depth i is 2i
• The shallowest leaf is the leftmost one, with depth n . 2
n
Thus the total number of recursive calls is Ω(22 ), or exponential.
Running time
In fact, the solution to the recursion
T (n) = T (n − 1) + T (n − 2) + Θ(1)
is
T(n) = Θ(φn).
Running time
In fact, the solution to the recursion
T (n) = T (n − 1) + T (n − 2) + Θ(1)
is
T(n) = Θ(φn).
The reason the recursive algorithm is so slow is because the same recursive calls are recomputed over and over.
Memoization
How do we avoid making all these duplicate recursive calls?
Memoization
How do we avoid making all these duplicate recursive calls?
• One approach is to augment the recursive algorithm by storing the values returned by the recursive calls.
Memoization
How do we avoid making all these duplicate recursive calls?
• One approach is to augment the recursive algorithm by storing the values returned by the recursive calls.
• Then, at the beginning of each recursive call, check to see if the value we want already exists.
Memoization
How do we avoid making all these duplicate recursive calls?
• One approach is to augment the recursive algorithm by storing the values returned by the recursive calls.
• Then, at the beginning of each recursive call, check to see if the value we want already exists.
• If it does, then we re-use it. Otherwise we compute it.
Memoization
How do we avoid making all these duplicate recursive calls?
• One approach is to augment the recursive algorithm by storing the values returned by the recursive calls.
• Then, at the beginning of each recursive call, check to see if the value we want already exists.
• If it does, then we re-use it. Otherwise we compute it. This technique is called memoization.
Memoization
How do we avoid making all these duplicate recursive calls?
• One approach is to augment the recursive algorithm by storing the values returned by the recursive calls.
• Then, at the beginning of each recursive call, check to see if the value we want already exists.
• If it does, then we re-use it. Otherwise we compute it. This technique is called memoization. It:
• maintains the familiar, recursive, top-down structure of the algorithm
• but without the exponential costs of re-computing all the values.
Memoization
Memoized algorithm for Fibonacci numbers:
// F[0..n] is a global array
MemFib(n)
if n = 0 or n = 1 then F[n] ← 1
else if F[n] undefined
F[n] ← MemFib(n-1) + MemFib(n-2)
return F[n]
Memoization
Memoized algorithm for Fibonacci numbers:
// F[0..n] is a global array
MemFib(n)
if n = 0 or n = 1 then F[n] ← 1
else if F[n] undefined
F[n] ← MemFib(n-1) + MemFib(n-2)
return F[n]
Running Time?
Running time of MemFib
F(n)
F (n − 2) F (n − 1)
F (n − 3) F (n − 2)
F(n−4) F(n−3)
F(n−5) F(n−4)
Running time of MemFib
Memoized algorithm for Fibonacci numbers:
// F[0..n] is a global array
MemFib(n)
if n = 0 or n = 1 then F[n] ← 1
else if F[n] undefined
F[n] ← MemFib(n-1) + MemFib(n-2)
return F[n]
Running Time? O(n)!
Running time of MemFib
Memoized algorithm for Fibonacci numbers:
// F[0..n] is a global array
MemFib(n)
if n = 0 or n = 1 then F[n] ← 1
else if F[n] undefined
F[n] ← MemFib(n-1) + MemFib(n-2)
return F[n]
Running Time? O(n)! An exponential speedup!
Dynamic Programming
Rather than using a top-down approach to reach the bottom of the recursion and then compute Fibonacci numbers bottom-up, dynamic programming does the bottom-up approach directly and iteratively.
Dynamic Programming
Rather than using a top-down approach to reach the bottom of the recursion and then compute Fibonacci numbers bottom-up, dynamic programming does the bottom-up approach directly and iteratively.
To compute F(n):
01234567
Dynamic Programming
Rather than using a top-down approach to reach the bottom of the recursion and then compute Fibonacci numbers bottom-up, dynamic programming does the bottom-up approach directly and iteratively.
To compute F(n):
• We start by computing F(2) from F(0) = 1 and F(1) = 1.
01234567
Dynamic Programming
Rather than using a top-down approach to reach the bottom of the recursion and then compute Fibonacci numbers bottom-up, dynamic programming does the bottom-up approach directly and iteratively.
To compute F(n):
• We start by computing F(2) from F(0) = 1 and F(1) = 1.
• Then we compute F(3) from F(2) and F(1),
01234567
Dynamic Programming
Rather than using a top-down approach to reach the bottom of the recursion and then compute Fibonacci numbers bottom-up, dynamic programming does the bottom-up approach directly and iteratively.
To compute F(n):
• We start by computing F(2) from F(0) = 1 and F(1) = 1.
• Then we compute F(3) from F(2) and F(1),
• and then F(4) from F(3) and F(2), and so on…
01234567
Dynamic programming
IterFib(n)
F[0] ← 1
F[1] ← 1
for i ← 2 to n do
F[i] ← F[i-1] + F[i-2] return F[n]
Dynamic programming
IterFib(n)
F[0] ← 1
F[1] ← 1
for i ← 2 to n do
F[i] ← F[i-1] + F[i-2] return F[n]
Running time?
Dynamic programming
IterFib(n)
F[0] ← 1
F[1] ← 1
for i ← 2 to n do
F[i] ← F[i-1] + F[i-2] return F[n]
Running time? Clearly Θ(n).
Dynamic programming
IterFib(n)
F[0] ← 1
F[1] ← 1
for i ← 2 to n do
F[i] ← F[i-1] + F[i-2] return F[n]
Running time? Clearly Θ(n).
Note that this algorithm uses Θ(n) space. Can you modify it so it uses Θ(1) space?
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
c Identify dependencies
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
c Identify dependencies
d Find a good evaluation order
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
c Identify dependencies
d Find a good evaluation order
e Write down the algorithm
Dynamic Programming
The basic idea behind dynamic programming is recursion without repetition.
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
c Identify dependencies
d Find a good evaluation order
e Write down the algorithm
f Analyze space and running time
Text Segmentation
Input: A sequence of characters stored in A[1..n].
Output: True if A can be segmented into a sequence of words,
False otherwise.
Text Segmentation
Input: Output:
Given:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.
Text Segmentation
Input: Output:
Given: Example:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.
If sequence A consists of characters
BOTHEARTHANDSATURNSPIN
and IsWord(w) is True if w is a word in English, then:
Text Segmentation
Input: Output:
Given: Example:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.
If sequence A consists of characters
BOTHEARTHANDSATURNSPIN
and IsWord(w) is True if w is a word in English, then:
• Output True because BOTH·EARTH·AND·SATURN·SPIN is a valid segmentation of A
Text Segmentation
Input: Output:
Given: Example:
A sequence of characters stored in A[1..n].
True if A can be segmented into a sequence of words, False otherwise.
Function IsWord(w) that returns True if sequence of characters w is a word, False otherwise.
If sequence A consists of characters
BOTHEARTHANDSATURNSPIN
and IsWord(w) is True if w is a word in English, then:
• Output True because BOTH·EARTH·AND·SATURN·SPIN is a valid segmentation of A
• By the way, BOT·HEART·HANDS·AT·URNS·PIN is another valid segmentation of A.
Dynamic Programming algorithm development, step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
Dynamic Programming algorithm development, step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
Dynamic Programming algorithm development, step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
// Is the suffix A[i..n] Splittable?
Splittable(i):
if i > n
return True
for j ← i to n
if IsWord(i, j) and Splittable(j + 1)
return True
return False
Dynamic Programming algorithm development, step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
// Is the suffix A[i..n] Splittable?
Splittable(i):
if i > n
return True
for j ← i to n
if IsWord(i, j) and Splittable(j + 1)
return True
return False
Running time?
Dynamic Programming algorithm development, step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
// Is the suffix A[i..n] Splittable?
Splittable(i):
if i > n
return True
for j ← i to n
if IsWord(i, j) and Splittable(j + 1)
return True
return False
Running time? O(2n)
Repetitive recursive calls
Note that there are:
• Only n + 1 different ways to call the recursive function Splittable(i), one for each value of i between 1 and n + 1
Repetitive recursive calls
Note that there are:
• Only n + 1 different ways to call the recursive function
Splittable(i), one for each value of i between 1 and n + 1
• Only O(n2) different ways to call IsWord(i, j), one for each pair (i,j) such that 1 ≤ i ≤ j ≤ n.
Repetitive recursive calls
Note that there are:
• Only n + 1 different ways to call the recursive function
Splittable(i), one for each value of i between 1 and n + 1 • Only O(n2) different ways to call IsWord(i, j), one for each
pair (i,j) such that 1 ≤ i ≤ j ≤ n.
“Why are we spending exponential time computing only a polynomial amount of stuff???”
Repetitive recursive calls
Note that there are:
• Only n + 1 different ways to call the recursive function
Splittable(i), one for each value of i between 1 and n + 1 • Only O(n2) different ways to call IsWord(i, j), one for each
pair (i,j) such that 1 ≤ i ≤ j ≤ n.
“Why are we spending exponential time computing only a
polynomial amount of stuff???”
For example:
BLUE
STEM
UNIT
ROBOT
HEARTHANDSATURNSPIN
BLUEST
EMU
NITRO
BOT
HEARTHANDSATURNSPIN
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a Each recursive subproblem is Splittable(i) with i between
1 and n+1 …
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a Each recursive subproblem is Splittable(i) with i between
1 and n+1 …
b … so we can memoize the function Splittable into an array
SplitTable[1..n+1].
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a Each recursive subproblem is Splittable(i) with i between
1 and n+1 …
b … so we can memoize the function Splittable into an array
SplitTable[1..n+1].
c Each subproblem Splittable(i) depends only on results of
subproblems Splittable(j) where j > i …
1inn+1
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a Each recursive subproblem is Splittable(i) with i between
1 and n+1 …
b … so we can memoize the function Splittable into an array
SplitTable[1..n+1].
c Each subproblem Splittable(i) depends only on results of
subproblems Splittable(j) where j > i …
1inn+1
d … so we should be filling the array in decreasing index order, starting with SplitTable[n+1] = True.
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a Each recursive subproblem is Splittable(i) with i between
1 and n+1 …
b … so we can memoize the function Splittable into an array
SplitTable[1..n+1].
c Each subproblem Splittable(i) depends only on results of
subproblems Splittable(j) where j > i …
1inn+1
d … so we should be filling the array in decreasing index order, starting with SplitTable[n+1] = True.
e The algorithm is on the next slide …
f Also on next slide, the running time analysis …
Text segmentation dynamic programming algorithm
// Is A[1..n] splittable?
FastSplittable(A[1..n]):
SplitTable[n + 1] ← True for i ← n down to 1
SplitTable[i] ← False for j ← i to n
if IsWord(i, j) and SplitTable[j + 1] SplitTable[i] ← True
return SplitTable[1]
Text segmentation dynamic programming algorithm
// Is A[1..n] splittable?
FastSplittable(A[1..n]):
SplitTable[n + 1] ← True for i ← n down to 1
SplitTable[i] ← False for j ← i to n
if IsWord(i, j) and SplitTable[j + 1] SplitTable[i] ← True
return SplitTable[1]
Running time?
Text segmentation dynamic programming algorithm
// Is A[1..n] splittable?
FastSplittable(A[1..n]):
SplitTable[n + 1] ← True for i ← n down to 1
SplitTable[i] ← False for j ← i to n
if IsWord(i, j) and SplitTable[j + 1] SplitTable[i] ← True
return SplitTable[1]
Running time? O(n2)
Longest Increasing Subsequence
For any sequence S,
26142429535783
Longest Increasing Subsequence
For any sequence S, a subsequence of S is another sequence obtained from S by deleting zero or more elements, without changing the order of the remaining elements.
26142429535783
Longest Increasing Subsequence
For any sequence S, a subsequence of S is another sequence obtained from S by deleting zero or more elements, without changing the order of the remaining elements.
Problem: Given a sequence of integers S find the Longest Increasing Subsequence (LIS) of S.
26142429535783
Longest Increasing Subsequence
For any sequence S, a subsequence of S is another sequence obtained from S by deleting zero or more elements, without changing the order of the remaining elements.
Problem: Given a sequence of integers S find the Longest Increasing Subsequence (LIS) of S.
Input: Output:
Example:
Integer array A[1..n].
Longest possible sequence of indices 1≤i1
return 0
else if A[i] ≥ A[j]
return LISbigger(i, j + 1)
else
skip ← LISbigger(i, j + 1) take ← LISbigger(j, j + 1) + 1 return max{skip, take}
Dynamic programming algorithm development step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
// return length of LIS of A[j..n] s.t.
// every element is larger than A[i]
LISbigger(i, j):
if j > n
return 0
else if A[i] ≥ A[j]
return LISbigger(i, j + 1)
else
skip ← LISbigger(i, j + 1) take ← LISbigger(j, j + 1) + 1 return max{skip, take}
Running time?
Dynamic programming algorithm development step 1
Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
// return length of LIS of A[j..n] s.t.
// every element is larger than A[i]
LISbigger(i, j):
if j > n
return 0
else if A[i] ≥ A[j]
return LISbigger(i, j + 1)
else
skip ← LISbigger(i, j + 1) take ← LISbigger(j, j + 1) + 1 return max{skip, take}
Running time? O(2n)
Dynamic programming algorithm development step 2
To develop a dynamic algorithm:
1 Formulate the problem recursively
a Describe the problem that you want to solve recursively
b Give a clear recursive formula or algorithm
2 Build solutions to your recurrence from the bottom up
a Identify the subproblems
b Choose a memoization data structure
c Identify dependencies
d Find a good evaluation order
e Write down the algorithm
f Analyze space and running time
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a The subproblems are LISbigger(i, j + 1) and LISbigger(j, j + 1) with indices i and j with values between 0 and n
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a The subproblems are LISbigger(i, j + 1) and LISbigger(j, j + 1) with indices i and j with values between 0 and n
b We can memoize the results of these subproblems into a two-dimensional array LISbigger[0..n, 1..n+1].
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up a The subproblems are LISbigger(i, j + 1) and
LISbigger(j, j + 1) with indices i and j with values
between 0 and n
b We can memoize the results of these subproblems into a
two-dimensional array LISbigger[0..n, 1..n+1].
c Each entry LISbigger[i, j] is filled in using entries
LISbigger[i, j+1] and LISbigger[j, j+1]. 1 jj+1
0
i j n
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a The subproblems are LISbigger(i, j + 1) and LISbigger(j, j + 1) with indices i and j with values between 0 and n
b We can memoize the results of these subproblems into a two-dimensional array LISbigger[0..n, 1..n+1].
c Each entry LISbigger[i, j] is filled in using entries LISbigger[i, j+1] and LISbigger[j, j+1].
d Fill in the entries of the two-dimensional table column-by-column, right-to-left.
Dynamic programming algorithm development step 2
Build solutions to your recurrence from the bottom up
a The subproblems are LISbigger(i, j + 1) and LISbigger(j, j + 1) with indices i and j with values between 0 and n
b We can memoize the results of these subproblems into a two-dimensional array LISbigger[0..n, 1..n+1].
c Each entry LISbigger[i, j] is filled in using entries LISbigger[i, j+1] and LISbigger[j, j+1].
d Fill in the entries of the two-dimensional table column-by-column, right-to-left.
e Iterative algorithm on the slide…
f Running time analysis on the next slide…
FastLIS
// return length of LIS of A[1..n]
FastLIS(A[1 .. n]):
A[0] ← −∞
for i ← 0 to n
LISbigger[i, n + 1] ← 0 for j←n down to 1
for i ← 0 to j – 1
keep ← 1 + LISbigger[j, j + 1] skip ← LISbigger[i, j + 1]
if A[i] ≥ A[j]
LISbigger[i, j] ← skip else
LISbigger[i, j] ← max{keep, skip} return LISbigger[0, 1]
FastLIS
// return length of LIS of A[1..n]
FastLIS(A[1 .. n]):
A[0] ← −∞
for i ← 0 to n
LISbigger[i, n + 1] ← 0 for j←n down to 1
for i ← 0 to j – 1
keep ← 1 + LISbigger[j, j + 1] skip ← LISbigger[i, j + 1]
if A[i] ≥ A[j]
LISbigger[i, j] ← skip else
LISbigger[i, j] ← max{keep, skip} return LISbigger[0, 1]
Running time?
FastLIS
// return length of LIS of A[1..n]
FastLIS(A[1 .. n]):
A[0] ← −∞
for i ← 0 to n
LISbigger[i, n + 1] ← 0 for j←n down to 1
for i ← 0 to j – 1
keep ← 1 + LISbigger[j, j + 1] skip ← LISbigger[i, j + 1]
if A[i] ≥ A[j]
LISbigger[i, j] ← skip else
LISbigger[i, j] ← max{keep, skip} return LISbigger[0, 1]
Running time? O(n2)