ObjectiveMcq
Print Protected
This page is protected for print. Use the website to view the content.
7 practice sets · Page 1 of 1
What is the space complexity of the above implementation of Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
The space complexity of the above Wagner-Fischer algorithm is O(mn).
What is the time complexity of the Wagner-Fischer algorithm where "m" and "n" are the lengths of the two strings?
O(1)
O(n+m)
O(mn)
O(nlogm)
The time complexity of the Wagner-Fischer algorithm is O(mn).
Which of the following lines should be inserted to complete the above code?
arr[i][j] = min
(min = arr[i-1][j-1] - 1);
min = arr[i-1][j-1].
(min = arr[i-1][j-1] + 1);
The line min = arr[i-1][j-1] completes the above code.
For which of the following pairs of strings is the edit distance maximum?
sunday & monday
monday & tuesday
tuesday & wednesday
wednesday & thursday
The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.
What is the edit distance between the strings "abcd" and "acbd" when the allowed operations are insertion, deletion and substitution?
1
2
3
4
The string "abcd" can be changed to "acbd" by substituting "b" with "c" and "c" with "b". Thus, the edit distance is 2.
Wagner-Fischer algorithm is used to find ____________
Longest common subsequence
Longest increasing subsequence
Edit distance between two strings
Longest decreasing subsequence
Wagner-Fischer algorithm is used to find the edit distance between two strings.
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive
Wagner-Fischer belongs to the dynamic programming type of algorithms.
