Vidyalelo
Data Structure · Q242

Dynamic Programming in Data Structures

Programming · Data Structure · question 242

Q242

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].
Answer
D.
min = arr[i-1][j-1] + 1;

Answer: Option C

Solution

Answer: Option C
No explanation is given for this question Let's Discuss on Board