COMP3711: Design and Analysis of Algorithms
DP Tutorial 1
COMP3711: Design and Analysis of Algorithms
Copyright By PowCoder代写 加微信 powcoder
Version of April 1, 2020
Longest Monotonically Increasing Subsequence
Question 1
Give an time dynamic programming algorithm to find the longest monotonically increasing subsequence of a sequence of numbers, i.e, each successive number in the subsequence is greater than or equal to its predecessor.
For example, if the input sequence is
the output should be either
We first give an algorithm which finds the length of the longest increasing subsequence; will later modify it to report a subsequence with this length.
Let denote the prefix of consisting of its first items. Define
= the length of the longest increasing subsequence that ends at .
The length of the longest increasing subsequence in is then
= the length of the longest increasing subsequence that ends at Initial Condition:
If all items to left of are than , answer must be .
Otherwise longest increasing subsequence that ends with hasform ,
where is the longest increasing subsequence that ends with for some and .
This yields the following recurrence relation:
We do not write the pseudocode, but just note that we store the ‘s in an array whose entries are computed in order of increasing .
After computing the array, we run through all the entries to find the maximum value.
This is the length of the longest increasing subsequence in .
For every it takes time to calculate .
=>therunningtimeis .
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
𝑖=2:Since𝑥≤𝑥 ⇒ 𝑐2 =max𝑐1 +1=2
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
𝑖=2:Since𝑥≤𝑥 ⇒ 𝑐2 =max𝑐1 +1=2
𝑖=3:Since𝑥,𝑥≤𝑥⇒c3 =max𝑐1,𝑐[2] +1=2+1=3
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
𝑖=2:Since𝑥≤𝑥 ⇒ 𝑐2 =max𝑐1 +1=2
𝑖=3:Since𝑥,𝑥≤𝑥⇒c3 =max𝑐1,𝑐[2] +1=2+1=3 𝑖=4:Since𝑥,𝑥,𝑥>𝑥 ⇒c4 =1
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
𝑖=2:Since𝑥≤𝑥 ⇒ 𝑐2 =max𝑐1 +1=2
𝑖=3:Since𝑥,𝑥≤𝑥⇒c3 =max𝑐1,𝑐[2] +1=2+1=3 𝑖=4:Since𝑥,𝑥,𝑥>𝑥 ⇒c4 =1
𝑖=5:Since 𝑥≤𝑥 and𝑥,𝑥,𝑥>𝑥 ⇒c5 =max𝑐4 +1=2
The input sequence is X = 4,5,7,1,3,9 ;
Find the longest monotonically increasing subsequence.
𝑖=2:Since𝑥≤𝑥 ⇒ 𝑐2 =max𝑐1 +1=2
Return:maxisc6 =4
𝑖=3:Since𝑥,𝑥≤𝑥⇒c3 =max𝑐1,𝑐[2] +1=2+1=3 𝑖=4:Since𝑥,𝑥,𝑥>𝑥 ⇒c4 =1
𝑖=5:Since 𝑥≤𝑥 and𝑥,𝑥,𝑥>𝑥 ⇒c5 =max𝑐4 +1=2
𝑖=6: Since𝑥,𝑥,𝑥,𝑥,𝑥≤𝑥⇒c6 =max𝑐1,𝑐2,𝑐3,𝑐4,𝑐5 +1=4
Toreportoptimalsubsequence,weneedtostoreforeach ,notonly , but also value of which achieves the maximum in the recurrence relation.
Denote this by . ( means no predecessor)
Suppose . Let S be optimal subsequence
is the last item in S. the optimal subsequence. 2nd tolastiteminSis ,
3rd tolastiteminSis ,etc.
until we have found all the items in S
Runningtimeofthisstepis soentirealgorithmisstill .
Toreportoptimalsubsequence,weneedtostoreforeach ,notonly , but also value of which achieves the maximum in the recurrence relation.
Denote this by . ( means no predecessor)
Return:maxis c6 =4, so𝑘=6 Solution is
𝑥[ ] ←𝑥[ ]←𝑥[] ←𝑥 i.e.𝑥 ←𝑥 ←𝑥 ←𝑥
i.e. {4, 5, 7, 9}
𝑟𝑟6 =𝑟3 =2
𝑟[𝑟𝑟6] =𝑟[2]=1 𝑟[𝑟[𝑟 𝑟 6 ] =𝑟[1]=∅
Alternative Solution
This problem can also be solved using the Longest Common Subsequence (LCS) Algorithm
be the original input.
be the items from sorted.
Then LCS(X, Y) is exactly the Longest Increasing Subsequence of X (why?)
Alternative Solution
This problem can also be solved using the Longest Common Subsequence (LCS) Algorithm
be the original input.
be the items from sorted.
Then LCS(X, Y) is exactly the Longest Increasing Subsequence of X (why?)
Since LCS(X, Y) uses time, this new algorithm also uses time.
Surprisingly, there is also an algorithm for solving the problem. See
https://www.cs.princeton.edu/courses/archive/spring13/cos423/lectures/LongestIncreasingSubsequ ence.pdf
COMP3711: Design and Analysis of Algorithms
The Subset Sum Problem
The subset sum problem is: Given a set of
and an integer determine whether there is a subset
the elements in is equal to . For example, let
, then the answer is “yes” because the elements of
If , the answer is “no”.
positive integers,
, such that the sum of
Give a dynamic programming solution to the subset sum problem that runs in time.
Justify the correctness and running time of your algorithm.
Define a Boolean array , and as follows:
Easy Cases:
For all ,
ifthereisasubsetof thatsumsto , otherwise
(choosing no items equals )
, because item is too large to use
Otherwise,
(i) because either solution uses
can be solved with first
in which case can be solved with first items
This can only happen if (ii) or solution does not use
to do to do
Dynamic-SubsetSum( )
It is easy to see that this runs in time.
There will be a solution if and only if
to do then
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Solution: we use a table to store A
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Solution: we use a table to store A
𝒙𝟏 =𝟕>𝒋=𝟏,..𝟔
so, for all j
𝐴1,𝑗 =𝐴[0,𝑗]
Solution: we use a table to store A
𝒙𝟐 =𝟒≤𝒋=𝟒,𝟓,𝟔 so, when 𝑗 = 4,5,6
𝐴2,𝑗 =(𝐴1,𝑗−4 𝑂𝑅𝐴1,𝑗)
e.g.𝐴2,4 =(𝐴1,0 𝑂𝑅𝐴1,4) = 𝑇𝑂𝑅𝐹=𝑇
𝒙𝟐 =𝟒>𝒋=𝟏,𝟐,𝟑
so, when 𝑗 = 1,2,3 𝐴2,𝑗 =𝐴[1,𝑗]
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Solution: we use a table to store A
𝒙𝟑 =𝟖>𝒋=𝟏,..𝟔
So, for all j
𝐴3,𝑗 =𝐴[2,𝑗]
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Solution: we use a table to store A
𝒙𝟒 =𝟐≤𝒋=𝟐,𝟑,𝟒,𝟓,𝟔
So, when j = 2, …, 6
𝐴4,𝑗 =(𝐴3,𝑗−2 𝑂𝑅𝐴3,𝑗 ) e.g.𝐴4,2 = 𝐴3,0 𝑂𝑅𝐴3,2
= 𝑇 𝑂𝑅 𝐹 = 𝑇
so𝐴 4,1 =𝐴 3,1 =𝐹
Given a set 𝑆 = {7, 4, 8, 2, 5, 3}, and W=6, determine whether there is a subset, 𝑆 ⊆ 𝑆, such that the sum of the elements in 𝑆’ is equal to 𝑊.
Solution: we use a table to store A
Fill the table
𝑹𝒆𝒕𝒖𝒓𝒏: 𝐴 6, 6 = 𝑇𝑟𝑢𝑒
COMP3711: Design and Analysis of Algorithms
DP Maximum Contiguous Subarray
The Maximum Subarray Problem: A DP solution
Input: Profit history of a company. Money earned/lost each year.
Profit (M$)
Problem: Find the span of years in which the company earned the most Answer: Year 5-8 , 9 M$
Formal definition:
Input: An array of numbers Output: Find the maximum value
, both positive and negative
Brute force Algorithm
(Reuse of Information) Algorithm
Divide-and-Conquer Algorithm Linear Scan Algorithm
Now: design a Dynamic Programming Algorithm
Note: previous algorithms solved a slightly different problem than the one defined on the previous page. The problems differ (ONLY) in the case that for all 𝒊, 𝑨 𝒊 < 𝟎.
In that case, the old algorithms returned the value 0.
The problem as defined on the previous page returns 𝑚𝑎𝑥 𝐴[𝑖] .
Easy to transform the solution of one problem to that of the other in 𝛩 𝑛 time.
A dynamic programming (Θ( )) algorithm
Define: to be max value subarray ending at
The main observation is that if
This immediately implies DP Recurrence
The DP recurrence
Set We just saw
Original problem then becomes finding such that
The DP recurrence permits constructing in O(1) time from .
We can construct in order in O(n) total time while keeping
track of the largest found so far
This finds in O(n) total time, solving the problem.
Note: This algorithm is very similar to the linear scan algorithm we developed in class, but found using DP reasoning
Derived recurrence that
Implementation
and need to find such that
This is very straightforward.
Next slides give actual code, and a worked example
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 6 9 8 356667799
Solution is
Simplified: We only need to remember the last
Base condition: Recurrence:
𝑖 ( call it
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉 ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉)
if 𝑉𝑚𝑎𝑥 < 𝑉
then 𝑉𝑚𝑎𝑥 ← 𝑉
end if return 𝑉𝑚𝑎𝑥
This gets same result as Version 1, but is simpler!
Running time:
Next pages provide a detailed walk-through of how Version 1 fills in the DP table.
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 3566
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 35666
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 356667
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 6 3566677
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 6 9 35666779
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 6 9 8 356667799
Store 𝑖 in a table , at each step calculating from
Base condition:
Recurrence:
let 𝑉[1,2,...,𝑛] be an array storing 𝑉 𝑉1←𝐴1
𝑉𝑚𝑎𝑥 ← 𝐴[1]
for 𝑖←2 to 𝑛 do
𝑉[𝑖] ← max(𝐴[𝑖], 𝐴[𝑖] + 𝑉[𝑖 − 1])
if 𝑉𝑚𝑎𝑥 < 𝑉[𝑖]
then 𝑉𝑚𝑎𝑥 ← 𝑉[𝑖] end if
return 𝑉𝑚𝑎𝑥
Running time:
3 2 1 -7 5 2 -1 3 -1
3 5 6 -1 5 7 6 9 8 356667799
Solution is
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com