Find the edit distance between the string "ARTIFICIAL" and "NATURAL" U | Design and Analysis of Algorithms 2079

Design and Analysis of Algorithms20795 marksNumerical: edit distanceDP Algorithms

Find the edit distance between the string "ARTIFICIAL" and "NATURAL" Using dynamic programming. [5]

String A = "ARTIFICIAL", length $m = 10$ : A-R-T-I-F-I-C-I-A-L - String B = "NATURAL", length $n = 7$ : N-A-T-U-R-A-L - Operations allowed: insertion, deletion, substitution (each cost 1). $$dp[i][j] = \begin{cases} i & j = 0 \ j & i = 0 \ dp[i-1][j-1] & A[i]=B[j] \ 1 + \min(dp[i-1][j],, dp[i...

String A = "ARTIFICIAL", length $m = 10$: A-R-T-I-F-I-C-I-A-L - String B = "NATURAL", length $n = 7$: N-A-T-U-R-A-L - Operations allowed: insertion, deletion, substitution (each cost 1). $$dp[i][j] = \begin{cases} i & j = 0 \ j & i = 0 \ dp[i-1][j-1] & A[i]=B[j] \ 1 + \min(dp[i-1][j],, dp[i...