What is the complexity of any dynamic programming approach

Assignment Help Computer Engineering

Reference no: EM132137149

On a string s, we have the following elementary operations: i) Insertion of a single letter into the string s, e.g., BT ? BAT. ii) Deletion of a single letter in the string s, e.g., CAT E ? CAT. iii) Substitution of one letter in the string s by another one, e.g., BAT ? CAT. The Levenshtein distance D(s, t) between two strings s and t is equal to the smallest number of operations i), ii), or iii) to transform the string s into t. Let m denote an array where the entry m[i, j] contains the Levenshtein distance of the initial segments s[1..i] and t[1..j] of the strings s and t, respectively. (a) Determine the entries and justify your claim:

(a) m[i, 0] =

(b) m[0, j] =

(b) The following facts are easily established: (F1) If we can transform s[1..i] to t[1..j - 1] in k operations, then we can simply add t[j] afterwards to get t[1..j] in k + 1 operations. (F2) If we can transform s[1..i - 1] to t[1..j] in k operations, then we can do the same operations on s[1..i] and then remove the original s[i] at the end in k + 1 operations. (F3) If we can transform s[1..i - 1] to t[1..j - 1] in k operations, we can do the same to s[1..i] and then do a substitution of t[j] for the original s[i] at the end if necessary, requiring k or k + 1 operations. These three facts suffice to determine the value of m[i, j] from the entries m[i, j - 1], m[i - 1, j], and m[i - 1, j - 1]. Derive the formula for m[i, j] and justify your result. Explain how the two subcases in F3 are resolved.

m[i, j] =

(c) What is the complexity of any dynamic programming approach based on parts a) and b), assume that s and t are of length a and b. Use Big Omega notation

Reference no: EM132137149

Questions Cloud

The trial court rendered judgment against lamas : The trial court rendered judgment against Lamas. On appeal, did the appellate court reverse? Explain.

Employer take to minimize possiblity of terminations : What steps can an employer take to minimize the possiblity of terminations being overturned by legal actions? Why?

The risks associated planned procurement approach : Identify the risks associated planned procurement approach. how procurement risks for this project will be monitored and controlled.

Annual holding and setup costs : The soft goods department of a large department store sells 175 units per month of a certain large bath towel. annual holding and setup costs?

What is the complexity of any dynamic programming approach : What is the complexity of any dynamic programming approach based on parts a) and b), assume that s and t are of length a and b. Use Big Omega notation

Print the converted sentence both to the screen : Print the converted sentence both to the screen and to an output file. Your input file consists of a variable number of records.

Develop your own string class : Develop and work with a C++ class, define constructors and destructors, define member functions outside .

Which of the following statements will display a string : Which of the following statements will display a string as "Jones, Jane" (the last name, a comma, a space, and the first name) in the lblFullName control?

Write a method with an input variable : Write a method with an input variable (string type). The method should return the number of uppercase letters of the input variable.

User Account

All Pages