COMP 3711 − Design and Analysis of Algorithms 2022 Spring Semester − Written Assignment # 4 Solution
Solution 1 [25 pts] Number of Contiguous Subarrays with sum k
Let Sj = ji=1 A[i] and S0 = 0. We use a hashmap d to store the number of subarrays that have a specific sum. For example, in the beginning d[0] = 1, since S0 = 0. We progressively find the number of contiguous subarrays that end with the element A[i] and have sum k. We do this by finding the number of prefix subarrays that we need to remove from the front of the subarray that ends with A[i] such that the remaining subarray has sum k. Such prefixes must have sum Si − k. Let ri store the number of all contiguous subarrays thathavesumkuptoindexi. ThebasecasesareS0 =0,r0 =0,andd[0]=1. The recurrence relation is:
ri−1 +d[Si −k] ifSi −k∈d ri = ri−1 otherwise
Copyright By PowCoder代写 加微信 powcoder
Algorithm 1 Number of Contiguous Subarrays with sum k Input: array A[1…n], int k
for i ← 1 to n do
S ← S + A[i]
if S − k in d then
r ← r + d[S − k] end if
ifSnotindthen d[S] ← 0
▷ Base case ▷ Base case ▷ Base case
▷ Calculate Si ▷ Check if Si − k ∈ d ▷ Appropriately update ri
▷CheckiftheentryofSi doesnotexistind ▷ Create an entry
▷ Update the hashmap for the new Si The running time of the above algorithm is Θ(n).
d[S] ← d[S] + 1 end for
Solution 2 [25 pts] Distinct Subsequences
We create a matrix D[1…m+1][1…n+1] to store our results. The first row and column represent when we work with no characters from our strings yet. So ourbasecasesareD[i][1]=0foralli>2,andD[1][j]=1forallj. Whenthe latest characters we work with, A[j−1] and B[i−1] are not equal to each other that means we need to carry over the solution we found so far without including the character A[j − 1], so D[i][j] = D[i][j − 1]. Otherwise, we have the option to pick the character A[j − 1] or not, so D[i][j] = D[i][j − 1] + D[i − 1][j − 1]. Finally, we return D[m + 1][n + 1]. The recurrence relation is:
D[i][j−1]+D[i−1][j−1] ifA[j−1]==B[i−1] D[i][j] = D[i][j − 1] otherwise
Algorithm 2 Number of Distinct Subsequences of A that equal B Input: string A[1…n], string B[1…m]
Output: D[m+1][n+1]
Create D[1…m + 1][1…n + 1] for i ← 2 to m + 1 do
D[i][1] ← 0 end for
for j ← 1 to n + 1 do D[1][j] ← 1
for i ← 2 to m + 1 do
for j ← 2 to n + 1 do
if A[j − 1] == B[i − 1] then
▷ Stores results ▷ Base case
▷ Base case
▷ Last characters of the strings are equal
D[i][j] ← D[i][j − 1] + D[i − 1][j − 1] else
D[i][j] ← D[i][j − 1] end if
end for end for
The running time of the above algorithm is Θ(mn).
▷ Case 1 ▷ Case 2
Solutions 3 [25 pts] Unique Paths
We create a matrix D[1…m][1…n] to store the results, where D[i][j] represents the number of unique paths that can reach the cell MAZE[i][j]. To reach the starting point, it is possible in only way, so D[1][1] = 1. When the MAZE has a single row or column, then we can reach all the cells until we encounter the first obstacle and there is only one path. If there is an obstacle at the cell MAZE[i][j] == 1, the number of paths to reach there is D[i][j] = 0. Otherwise, when MAZE[i][j] == 0, we can reach that cell either from above or the left, thus D[i][j] = D[i − 1][j] + D[i][j − 1]. The recurrence relation is:
D[i − 1][j] + D[i][j − 1] 0
Algorithm 3 Number of Unique Paths Input: MAZE[1…m][1…n]
Output: D[m][n]
Create D[1…m][1…n] D[1][1] = 1
for i ← 2 to m do
if M[i][1] == 0 then D[i][1] ← D[i − 1][1]
D[i][1] ← 0 end if
for j ← 2 to n do
if MAZE[1][j] == 0 then D[1][j] ← D[1][j − 1]
D[1][j] ← 0 end if
for i ← 2 to m do
for j ← 2 to n do
if MAZE[i][j] == 0 then
D[i][j] ← D[i][j − 1] + D[i − 1][j] else
D[i][j] ← 0 end if
end for end for
The running time of the above algorithm is Θ(mn).
if MAZE[i][j] == 0 otherwise
▷ Stores results ▷ Base case ▷ Base case
▷ Base case
▷ The cell is not blocked ▷ Case 1
Solutions 4 [25 pts] Change Permutations
We create an array D[1…W +1], where D[j] represents the number of ways we can return change equal to j−1. In the beginning, if we do not use any coins yet D[j] = 0, except D[1] = 1, since there is only way to return 0 change. When we consider coin C[i] for change j − 1, we need to ensure that we can pick it (C[i] < j). If we can select coin C[i] for change j−1, D[j] = D[j]+D[j−C[i]]. Otherwise, D[j] = D[j]. Finally, we return D[W + 1]. The recurrence relation is:
D[j]+D[j−C[i]] ifC[i]