# Data Structure Questions and Answers – Wagner-Fischer Algorithm

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

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

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

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

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;

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)

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)

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

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

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

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.