This set of Data Structure Multiple Choice Questions & Answers (MCQs) focuses on “Edit Distance Problem”.
1. Which of the following methods can be used to solve the edit distance problem?
a) Recursion
b) Dynamic programming
c) Both dynamic programming and recursion
d) Greedy Algorithm
View Answer
Explanation: Both dynamic programming and recursion can be used to solve the edit distance problem.
2. The edit distance satisfies the axioms of a metric when the costs are non-negative.
a) True
b) False
View Answer
Explanation: d(s,s) = 0, since each string can be transformed into itself without any change.
d(s1, s2) > 0 when s1 != s2, since the transformation would require at least one operation.
d(s1, s2) = d(s2, s1)
d(s1, s3) <= d(s1, s2) + d(s2, s3)
Thus, the edit distance satisfies the axioms of a metric.
3. Which of the following is an application of the edit distance problem?
a) Approximate string matching
b) Spelling correction
c) Similarity of DNA
d) Approximate string matching, Spelling Correction and Similarity of DNA
View Answer
Explanation: All of the mentioned are the applications of the edit distance problem.
4. In which of the following cases will the edit distance between two strings be zero?
a) When one string is a substring of another
b) When the lengths of the two strings are equal
c) When the two strings are equal
d) The edit distance can never be zero
View Answer
Explanation: The edit distance will be zero only when the two strings are equal.
5. Suppose each edit (insert, delete, replace) has a cost of one. Then, the maximum edit distance cost between the two strings is equal to the length of the larger string.
a) True
b) False
View Answer
Explanation: Consider the strings “abcd” and “efghi”. The string “efghi” can be converted to “abcd” by deleting “i” and converting “efgh” to “abcd”. The cost of transformation is 5, which is equal to the length of the larger string.
6. Consider the strings “monday” and “tuesday”. What is the edit distance between the two strings?
a) 3
b) 4
c) 5
d) 6
View Answer
Explanation: “monday” can be converted to “tuesday” by replacing “m” with “t”, “o” with “u”, “n” with “e” and inserting “s” at the appropriate position. So, the edit distance is 4.
7. Consider the two strings “”(empty string) and “abcd”. What is the edit distance between the two strings?
a) 0
b) 4
c) 2
d) 3
View Answer
Explanation: The empty string can be transformed into “abcd” by inserting “a”, “b”, “c” and “d” at appropriate positions. Thus, the edit distance is 4.
8. Consider the following dynamic programming implementation of the edit distance problem:
#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; } _____________; } } return arr[len1][len2]; } int main() { char s1[] = "abcd", s2[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
Which of the following lines should be added to complete the above code?
a) arr[i-1][j] = min
b) arr[i][j-1] = min
c) arr[i-1][j-1] = min
d) arr[i][j] = min
View Answer
Explanation: The line arr[i][j] = min completes the above code.
9. What is the time complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of two strings?
#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[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)
View Answer
Explanation: The time complexity of the above dynamic programming implementation of the edit distance problem is O(mn).
10. What is the space complexity of the following dynamic programming implementation of the edit distance problem where “m” and “n” are the lengths of the two strings?
#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[] = "defg"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) O(1)
b) O(m + n)
c) O(mn)
d) O(n)
View Answer
Explanation: The space complexity of the above dynamic programming implementation of the edit distance problem is O(mn).
11. 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[] = "defg"; 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 “defg”, which is 4.
12. What is the value stored in arr[2][2] when the following 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[] = "abcd", s2[] = "defg"; 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[2][2] when the above code is executed is 2.
13. 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[] = "pqrstuv", s2[] = "prstuv"; int ans = edit_distance(s1, s2); printf("%d",ans); return 0; }
a) 1
b) 2
c) 3
d) 4
View Answer
Explanation: The code prints the edit distance between the two strings, which is 1.
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.
- Practice Computer Science MCQs
- Check Design and Analysis of Algorithms Books
- Apply for Computer Science Internship
- Check Computer Science Books
- Check Programming Books