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)
Correct Answer: C — O(mn)
Explanation:
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)
Correct Answer: C — O(mn)
Explanation:
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);
Correct Answer: C — min = arr[i-1][j-1].
Explanation:
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
Correct Answer: D — wednesday & thursday
Explanation:
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
Correct Answer: B — 2
Explanation:
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
Correct Answer: C — Edit distance between two strings
Explanation:
Wagner-Fischer algorithm is used to find the edit distance between two strings.
Wagner-Fischer is a ____________ algorithm.
Brute force
Greedy
Dynamic programming
Recursive
Correct Answer: C — Dynamic programming
Explanation:
Wagner-Fischer belongs to the dynamic programming type of algorithms.
