This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Wagner-Fischer Algorithm”.
1. Wagner–Fischer is a ____________ algorithm.
a) Brute force
b) Greedy
c) Dynamic programming
d) Recursive
View Answer
Explanation: Wagner–Fischer belongs to the dynamic programming type of algorithms.
2. Wagner–Fischer algorithm is used to find ____________
a) Longest common subsequence
b) Longest increasing subsequence
c) Edit distance between two strings
d) Longest decreasing subsequence
View Answer
Explanation: Wagner–Fischer algorithm is used to find the edit distance between two strings.
3. What is the edit distance between the strings “abcd” and “acbd” when the allowed operations are insertion, deletion and substitution?
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The string “abcd” can be changed to “acbd” by substituting “b” with “c” and “c” with “b”. Thus, the edit distance is 2.
4. For which of the following pairs of strings is the edit distance maximum?
a) sunday & monday
b) monday & tuesday
c) tuesday & wednesday
d) wednesday & thursday
View Answer
Explanation: The edit distances are 2, 4, 4 and 5 respectively. Hence, the maximum edit distance is between the strings wednesday and thursday.
5. Consider the following implementation of the Wagner–Fischer algorithm:
int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) ____________; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; }
Which of the following lines should be inserted to complete the above code?
a) arr[i][j] = min
b) min = arr[i-1][j-1] – 1;
c) min = arr[i-1][j-1].
d) min = arr[i-1][j-1] + 1;
View Answer
Explanation: The line min = arr[i-1][j-1] completes the above code.
6. What is the time complexity of the Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)
View Answer
Explanation: The time complexity of the Wagner–Fischer algorithm is O(mn).
7. What is the space complexity of the above implementation of Wagner–Fischer algorithm where “m” and “n” are the lengths of the two strings?
a) O(1)
b) O(n+m)
c) O(mn)
d) O(nlogm)
View Answer
Explanation: The space complexity of the above Wagner–Fischer algorithm is O(mn).
8. What is the output of the following code?
#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "somestring", s2[] = "anotherthing"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) 6
b) 7
c) 8
d) 9
View Answer
Explanation: The program prints the edit distance between the strings “somestring” and “anotherthing”, which is 6.
9. What is the value stored in arr[3][3] when the below code is executed?
#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "somestring", s2[] = "anotherthing"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The value stored in arr[3][3] is 3.
10. What is the output of the following code?
#include<stdio.h> #include<string.h> int get_min(int a, int b) { if(a < b) return a; return b; } int edit_distance(char *s1, char *s2) { int len1,len2,i,j,min; len1 = strlen(s1); len2 = strlen(s2); int arr[len1 + 1][len2 + 1]; for(i = 0;i <= len1; i++) arr[i][0] = i; for(i = 0; i <= len2; i++) arr[0][i] = i; for(i = 1; i <= len1; i++) { for(j = 1; j <= len2; j++) { min = get_min(arr[i-1][j],arr[i][j-1]) + 1; if(s1[i - 1] == s2[j - 1]) { if(arr[i-1][j-1] < min) min = arr[i-1][j-1]; } else { if(arr[i-1][j-1] + 1 < min) min = arr[i-1][j-1] + 1; } arr[i][j] = min; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "dcba"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The program prints the edit distance between the strings “abcd” and “dcba”, which is 4.
Sanfoundry Global Education & Learning Series – Data Structures & Algorithms.
To practice all areas of Data Structures & Algorithms, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Apply for Computer Science Internship
- Practice Computer Science MCQs
- Check Programming Books
- Practice Data Structure MCQ
- Practice Programming MCQs
