250+ TOP MCQs on Edit Distance Problem and Answers

Data Structure Multiple Choice Questions 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
Answer: c
Clarification: 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

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

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

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

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

Answer: b
Clarification: 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
#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;
               }
                _____________;
         }
     }
     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

Answer: d
Clarification: 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
#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[] = "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)

Answer: c
Clarification: 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
#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[] = "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)

Answer: c
Clarification: 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
#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[] = "defg";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
Answer: d
Clarification: 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
#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[] = "defg";
      int ans = edit_distance(s1, s2);
      printf("%d",ans);
      return 0;
}

a) 1
b) 2
c) 3
d) 4

Answer: b
Clarification: 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
#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[] = "pqrstuv", s2[] = "prstuv";
     int ans = edit_distance(s1, s2);
     printf("%d",ans);
     return 0;
}

a) 1
b) 2
c) 3
d) 4
View Answer

Answer: a
Clarification: The code prints the edit distance between the two strings, which is 1.

Leave a Reply

Your email address will not be published. Required fields are marked *