Algorithms 3027 Assignment 3 Solution The University of Sydney 2019 Semester 1 School of Computer Science
Task 0
(Note: Task 0 is meant to help you figure out the correct recurrence for the DP. The following solution for Task 0 is overkill but it motivates the DP recurrence in the solution for Task 1. Solutions that do something like keeping track of the length of the current repetition are also fine.)
Description
For 0 ≤ i ≤ n, let RSI(i) denote the RSI of A[1 : i], the i-length prefix of A. We claim that RSI(i) satisfies the following recurrence:
RSI(i) =
0
2s(A[1])
RSI(i − 1) + s(A[i])
if i = 0 or 1
if i = 2 and A[1] = A[2]
if A[i] = A[i − 1] = A[i − 2]
RSI(i−1)+2s(A[i]) ifA[i]=A[i−1]andA[i−1]̸=A[i−2]
RSI(i − 1) if A[i] ̸= A[i − 1]
We will prove this claim in the Correctness section later.
Our algorithm evalutes the recurrence in a bottom-up processing A from left to right. We use 1-
indexing of arrays below.
• Set RSI[0] = RSI[1] = 0.
• If A[1] = A[2], then set RSI[2] = 2s(A[1]). • Fori=3ton:
– ifA[i]=A[i−1]=A[i−2],thensetRSI[i]=RSI[i−1]+s(A[i])
– elseifA[i]=A[i−1]andA[i−1]̸=A[i−2],thensetRSI[i]=RSI[i−1]+2s(A[i]) – else if A[i] ̸= A[i − 1], then set RSI[i] = RSI[i − 1] + 2s(A[i])
• Return RSI[n] Correctness
We now prove by induction on i that the above recurrence is correct. The base cases are when i = 0, 1, 2, and it is easy to see that RSI(i) for these base cases are as claimed. It remains to prove the inductive case for i ≥ 3. Let us suppose that RSI(i − 1) is indeed the RSI of the prefix A[1 : i − 1]. Now consider the increase in RSI when we append A[i] to A[1 : i − 1]. There are 3 cases to consider:
1. A[i] = A[i − 1] = A[i − 2]. In this case, adding A[i] increases the length of an existing repetition in A[1 : i − 1] so adding A[i] increases the RSI by s(A[i]).
2. A[i] = A[i − 1] and A[i − 1] ̸= A[i − 2]. In this case, adding A[i] starts a new repetition of length 2 so it increases the RSI by 2s(A[i]).
3. A[i] ̸= A[i − 1]. In this case, adding A[i] neither starts a new repetition nor does it increase the length of an existing repetition, so the RSI does not increase.
Therefore, the recurrence is correct.
Complexity
We assume that evaluating the strain function s(·) takes O(1) time.
• The loop takes O(n) time, as there are n iterations, each of which takes O(1) time as it involves
only looking up an entry of A and then evaluating the strain function on that entry
• In total this is O(n).
The total space used by the algorithm is dominated by the size of the input, so this is O(n).
1
Task 1: Description of Algorithm
Inspired by Task 0, we define the following function
s(d) ifd=d=d
3321 inc(d1, d2, d3) = 2s(d3) if d3 = d2, d2 ̸= d1
0 if d3 ̸= d2
This function gives the increase in the strain of a sequence when we add dance move d3 to a sequence
that ends with [d1, d2]. Subproblems
• Observe that in an optimal remix R of A[1 : i] and B[1 : j], there are four possibilities which of A and B the last two moves of R are constructed:
– both came from the last two moves of A – both came from the last two moves of B – last from A, second last from B
– last from B, second last from A.
• Define the set of possible endings E = {AA, BB, AB, BA}.
• For0≤i≤nand0≤j≤m,ande∈E,defineOPT(i,j,e)tobetheRSIoftheoptimalremix of A[1 : i] and B[1 : j] ending in e. When e = AB, this means that we are looking at the optimal remix whose second-last move came from A and whose last move came from B.
Recurrence and base cases
The best remix R of the prefixes A[1 : i] and B[1 : j] is a remix of length i+j. There are four cases to the recurrence depending on e. In each case, since e fixes the last two moves of R, we just need to decide which should be the third-last move of R.
• Ife=AB,thenR[i+j−2]mustbeeitherA[i−1]orB[j−1],so
OPT(i, j − 1, AA) + inc(A[i − 1], A[i], B[j])
OPT(i, j, AB) = min OPT(i, j − 1, BA) + inc(B[j − 1], A[i], B[j]) • Ife=BA,thenR[i+j−2]mustbeeitherA[i−1]orB[j−1],so
OPT(i − 1, j, AB) + inc(A[i − 1], B[j], A[i]) OPT(i, j, BA) = min OPT(i − 1, j, BB) + inc(B[j − 1], B[j], A[i])
• Ife=AA,thenR[i+j−2]mustbeeitherA[i−2]orB[j],so
OPT(i − 1, j, AA) + inc(A[i − 2], A[i − 1], B[j])
OPT(i, j, AA) = min OPT(i − 1, j, BA) + inc(B[j], A[i − 1], B[j]) • Ife=BB,thenR[i+j−2]mustbeeitherA[i]orB[j−2],so
OPT(i, j − 1, AB) + inc(A[i − 2], A[i − 1], B[j]) OPT(i, j, BB) = min OPT(i, j − 1, BB) + inc(B[j − 2], B[j − 1], B[j])
In the above, we define A[−1] and A[−2] to be the empty string, same for B. The base cases are
and
OPT(i, 0, e) =
OPT(0, j, e) =
RSI(A[1 : i]) ∞
RSI(B[1 : j]) ∞
if e = AA otherwise
if e = BB otherwise
2
Finding solution
Computing optimal RSI:
• Each subproblem OPT(i, j, e) only depends on OPT(i − 1, j, e′) and OPT(i, j − 1, e′′), where e′ and
e′′ depends on i, j, e.
• We create a 3-dimensional array M to store the values of OPT(i, j, e) and fill in M in increasing
order of i, then increasing order of j.
• The base cases can be computed using two runs of the algorithm from Task 1, one for A and one
for B.
• The optimal RSI is mine∈E OPT(n, m, e).
Finding optimal remix:
• We create a 3-dimensional array P where P [i, j, e] = A if there is an optimal remix of A[1 : i] and
B[1 : j] ending in e in which the third-last move is from A, and P [i, j, e] = B otherwise.
• The array P is computed simultaneously with M.
• To recover the optimal remix, we look at e∗ ∈ E that achieves the minimum of OPT(n, m, e), start at P[n,m,e∗] and backtracks through P to build up an optimal remix R. Initially,
[A[i],B[j]] ife∗ =AB
[B[j],A[i]] ife∗ =BA R=∗
[A[i − 1], A[i]] if e = AA [B[j−1],B[j]] ife∗=BB
If we are currently at the cell P [i, j, e], the entry tells us how to extend R and also which entry to go to next. For example, if P[i,j,AB] = A, then we prepend R with A[i−1] and go to P[i,j−1,AA].
Task 2: Correctness
Recurrence and base cases
• The correctness of the base cases follow from the fact that if A is the empty sequence, then the only possible remix is B, and vice versa.
• The base cases are sufficient since the recurrence for OPT(i, j, e) either looks at i − 1 or j − 1.
• Consider the recurrence for OPT(i,j,AB). Let R be an optimal remix of the prefixes A[1 : i] and B[1 : j] such that its second last move came from A and its last move came from B, i.e. R[i+j] = B[j] and R[i+j −1] = A[i]. The RSI of R is the RSI of the prefix of R excluding the last move plus the increase in RSI when we add the last move to the prefix so
RSI(R) = RSI(R[1 : i + j − 1)) + inc(R[i + j − 2], R[i + j − 1], R[i + j]) = RSI(R[1 : i + j − 1)) + inc(R[i + j − 2], A[i], B[j]).
Moreover, R[i + j − 2] is either A[i − 1] or B[j − 1] since A[i] and B[j] are already used. In the former case, we have that R[1 : i + j − 1] is the optimal remix of A[1 : i] and B[1 : j − 1] with the ending AA and in the latter case, R[1 : i+j −1] is the optimal remix of A[1 : i] and B[1 : j −1] with the ending BA. This proves the correctness of the recurrence for OPT(i, j, AB).
• The proof of correctness for the other cases follow similarly. Finding solution
• The correctness of computing optimal RSI follows from the correctness of the recurrence and base cases and the fact that the algorithm is explicitly computing the recurrence as it fills in M.
• The correctness of backtracking also follows from the correctness of the recurrence and the fact that the algorithm replicates an optimal choice of which move to add to the sequence.
3
Task 3: Complexity
Time complexity
• Both M and P have at most O(nm) entries since i can range from 0 to n, j can range from 0 to m, and there are four possibilities for e.
• The base cases take O(n + m) time to evaluate using the algorithm from Task 0. Filling in each entry of M takes O(1) time since we only need to take the min of two expressions that can be evaluated by looking up the strain factor (which is assumed to be O(1) time) and a table lookup.
• The backtracking takes at most O(n + m) time: each iteration of the backtracking extends R by one move and an iteration takes O(1) time to execute as it only needs to lookup P[i,j,e].
• Thus, the total time is at most O(nm).
Space complexity
• Array M has O(nm) entries and each entry is just a number.
• Array P has at most O(nm) entries as well and each entry can be encoded as a Boolean.
• Computing the base cases using the algorithm from Task 0 takes up a total O(n+m) = O(n) space. • The backtracking also uses at most O(n + m) space to build up the optimal remix.
• Thus, the total space used is at most O(nm).
4