CS/ECE 374 A (Spring 2022) Homework 6 Solutions
Problem 6.1: For a sequence ⟨b1,…,bm⟩, an alternation is an index i ∈ {2,…,m−1} such that (bi−1
Describe an O(kn2)-time dynamic programming algorithm to solve this problem.1 In this part, your algorithm only needs to output the optimal value (i.e., the length of the longest subsequence).
(b) (20 pts) Give pseudocode to also output an optimal subsequence.
(a) Definition of subproblems.
For each i,j with 1 ≤ i < j ≤ n+1 and each h ∈ {0,...,k}, let L+(i,j,h) be the length of a longest subsequence of ⟨ai,aj,aj+1,...,an⟩ such that the number of alternations is at most h and the first element in the subsequence is ai and the second element (if exists) is greater than ai.
For each i,j with 1 ≤ i < j ≤ n+1 and each h ∈ {0,...,k}, let L−(i,j,h) be the length of a longest subsequence of ⟨ai,aj,aj+1,...,an⟩ such that the number of alternations is at most h and the first element in the subsequence is ai and the second element (if exists) is less than ai.
The final answer we want is maxni=1 max{L+(i, i + 1, k), L−(i, i + 1, k)}.
Base cases. L+(i,n+1,h) = L−(i,n+1,h) = 1 for each i ∈ {1,...,n} and h ∈ {0,...,k}. Recursive formula. For each i,j with 1 ≤ i < j ≤ n and h ∈ {0,...,k},
L+(i,j,h) =
max{L+(i,j+1,h), L+(j,j+1,h)+1, L−(j,j+1,h−1)+1} ifa >a andh≥1
L+(i, j + 1, h) 1You may assume that all the ai’s are distinct.
max{L+(i,j+1,h), L+(j,j+1,h)+1}
ifa >a andh=0
1. 2. 3. 4. 5.
10. 11. 12. 13. 14. 15.
fori=1tondoforh=0tokdoL+[i,n+1,h]=L−[i,n+1,h]=1 forj=ndownto2do
for i = 1 to j − 1 do for h = 0 to k do
ifaj >ai andh≥1then
L+[i,j,h]=max{L+[i,j+1,h], L+[j,j+1,h]+1, L−[j,j+1,h−1]+1}
elseifaj >ai andh=0then L+[i,j,h]=max{L+[i,j+1,h], L+[j,j+1,h]+1}
elseL+[i,j,h]=L+[i,j+1,h] ifaj
ifL−[i,i+1,k]>l∗ thenl∗ =L−[i,i+1,k],i∗ =i,sign∗ =− return l∗
max{L−(i,j+1,h), L−(j,j+1,h)+1, L+(j,j+1,h−1)+1} ifa ai. In this case, L+(i, j, h) = L+(j, j + 1, h) + 1.
Case 3: the second element in the optimal subsequence is aj and the third element (if exists) is less than aj. This case is applicable only when aj > ai and h ≥ 1. In this case, L+(i, j, h) = L−(j, j + 1, h − 1) + 1 (since the first three elements in the optimal subsequence form an alternation, so after excluding ai, we are allowed at most h − 1 alternations).
We don’t know which case we are in beforehand. So, we take max over all applicable cases.
The justification for L−(i, j, h) is similar.
Evaluation order. In order of decreasing j. Pseudocode.
max{L−(i,j+1,h), L−(j,j+1,h)+1}
ifa i:aj>aimax{L+(j,h)+1,L−(j,h−1)+1}} ifh≥1 max{1, maxj>i: aj >ai (L+(j, h) + 1)} if h = 0
max{1,maxj>i:ai: aj