250+ TOP MCQs on Wagner-Fischer Algorithm and Answers [2024]

Data Structure Multiple Choice Questions & Answers (MCQs) on “Wagner-Fischer Algorithm”.

1. Wagner–Fischer is a ____________ algorithm.
a) Brute force
b) Greedy
c) Dynamic programming
d) Recursive
Answer: c
Clarification: 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
Answer: c
Clarification: 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

Answer: b
Clarification: 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

Answer: d
Clarification: 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

Answer: c
Clarification: 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)

Answer: c
Clarification: 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)

Answer: c
Clarification: The space complexity of the above Wagner–Fischer algorithm is O(mn).

8. What is the output of the following code?

#include
#include
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

Answer: a
Clarification: 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
#include
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

Answer: c
Clarification: The value stored in arr[3][3] is 3.

10. What is the output of the following code?

#include
#include
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

Answer: d
Clarification: The program prints the edit distance between the strings “abcd” and “dcba”, which is 4.

& Algorithms.

and Answers.

Leave a Reply Cancel reply