Question: Below is the pseudocode for an Alignment algorithm used to align two string sequences. What is the biggest cause for concern with this algorithm? Alignment

Below is the pseudocode for an Alignment algorithm used to align two string sequences. What is the biggest cause for concern with this algorithm?
Alignment(X,Y)
Array A[0...m,0... n]
Initialize A[i,0]= i for each i
Initialize A[0, j]= j for each j
For j =1,..., n
For i =1,..., m
A[i, j]= OPT(i, j)= min[xiyj + OPT(i 1, j 1), + OPT(i 1, j), + OPT(i, j 1)]
Endfor
Endfor
Return A[m, n]
Group of answer choices
The algorithm uses O(mn) space, which scales poorly for very long sequences.
The algorithm performs 3 recursive calls.
The algorithm runs in O(n3) time.
The algorithm does not store enough information to retrieve the actual alignment once the minimum alignment score has been found

Step by Step Solution

There are 3 Steps involved in it

1 Expert Approved Answer
Step: 1 Unlock blur-text-image
Question Has Been Solved by an Expert!

Get step-by-step solutions from verified subject matter experts

Step: 2 Unlock
Step: 3 Unlock

Students Have Also Explored These Related Programming Questions!