Now consider the so-called Wagner-Fischer algorithm for computing the Levenshtein distance: WF (a[1...m], b[1...n]) Let D[0...m][0...n]...

Transcribed Image Text:

Now consider the so-called Wagner-Fischer algorithm for computing the Levenshtein distance: WF (a[1...m], b[1...n]) Let D[0...m][0...n] be matrix of zeros For i in [1...m] do D[i][0] = i End For For j in [1...n] do D[0][j] End For = j For i in [1...m] do For jin [1...n] do If a[i] b[j] Then D[i][j] = D[i-1] [j-1] Else D[i][j] = min(D[i-1][j], D[i][j-1], D[i-1][j-1]) + 1 End If End For End For 4 Return D[m] [n] End WF. 13. (2 points) Analyze its runtime complexity and express it as a function U(N) of the total number N:=m+n of input characters. You can assume for simplicity that m = n = N/2. Now consider the so-called Wagner-Fischer algorithm for computing the Levenshtein distance: WF (a[1...m], b[1...n]) Let D[0...m][0...n] be matrix of zeros For i in [1...m] do D[i][0] = i End For For j in [1...n] do D[0][j] End For = j For i in [1...m] do For jin [1...n] do If a[i] b[j] Then D[i][j] = D[i-1] [j-1] Else D[i][j] = min(D[i-1][j], D[i][j-1], D[i-1][j-1]) + 1 End If End For End For 4 Return D[m] [n] End WF. 13. (2 points) Analyze its runtime complexity and express it as a function U(N) of the total number N:=m+n of input characters. You can assume for simplicity that m = n = N/2.

Answer rating: 100% (QA)

The WagnerFischer algorithm for computing the Levenshtein distance has a ... View the full answer