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?
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];
}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;
Answer: Option C
What is the main principle behind Dynamic Programming (DP)?
A. Recursion with memoization.
B. Greedy approach.
C. Divide and conquer.
D. Overlapping subproblems and optimal substructure.
Which of the following problems can be solved using Dynamic Programming?
A. Binary Search
B. Depth-First Search
C. Longest Common Subsequence
D. Quick Sort
What is the key advantage of using Dynamic Programming over plain recursion?
A. It makes the code simpler.
B. It reduces the time complexity by storing results of subproblems.
C. It uses more memory.
D. It makes the code simpler.
In the context of Dynamic Programming, what does the term "memoization" refer to?
A. Using a stack to manage function calls.
B. A method for dividing problems.
C. Storing intermediate results to avoid redundant calculations.
D. A technique to speed up sorting.

Join The Discussion