### 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

#### Finds would cause damage to national security

Write review on this. Today in order to make face the increasing rate of data breaches in the companies, there is widespread agreement about the interests of participants

#### Prepare a detailed design document for the user interface

Prepare a detailed design document for the user interface for your project. Your design document should be based on your Project Requirements and Scope document and your Pro

#### Fuzzy system for forecasting electricity price

A Fuzzy System for Forecasting Electricity Price - Develop a fuzzy forecasting system using Matlab Toolbox. The system performs a forecasting task for power marketing price.

#### Write the boolean function as boolean algebra

Write the Boolean function as Boolean algebra terms. First, think about how to deal with the two outputs. Then, describe each single row in terms of Boolean al

#### Developing programs via functional decomposition and pointer

CSCI251/851 Advanced Programming Developing programs via functional decomposition and pointers.On completion you should know how to design a program by decomposing the problem

#### 3d animation using in object modelling and methods

Ngaruwahia Golf Course sits on the banks of the mighty Waikato River. This club is an easy 10 minutes' drive north of Hamilton and an hour's drive south of central Auckland

#### Implement a prototype

KIT205 Data Structures and Algorithms - Assignment 1: Data Structures Implement basic program functionality for a console driven application - Implement and test a linked list

#### Implementation of the spacecraft feature

Assignment 1: The Diamonds of Doom - Discuss and brain-storm with your associates, you must ensure that your submission is your own individual work - implementation of the "Sp