Algorithms Homework

| |

| **Cyclic Edit Distance** * * *In this homework, you are given * two strings X and Y of length n and m respectively,* four edit operations (copy, insert, delete and replace) with different costsand asked to calculate the *"cyclic edit distance"* between them. Edit distance is the cost of the least expensive transformation sequence (i.e. a sequence of operations with smallest total cost) that converts X to Y. Let D(X,Y) denote the edit distance between X and Y.

If you remove first character of a string and append it to the end, you obtain a cyclic shift of the original string. For example, *bcdefa* is a cyclic shift of *abcdef*. kth cyclic shift is defined as the composition of k cyclic shifts. (ex. *defabc* is the 3rd cyclic shift of *abcdef*) Let sk(X) denote the kth cyclic shift of X. **"cyclic edit distance"** between X and Y is defined as:

CD(X,Y) = min { D(sk(X), sl(Y)) | k = 0..n-1, l = 0..m-1 }

Using dynamic programming you can find edit distance between X and Y in O(nm) time (how?). One way to calculate cyclic edit distance is to determine D(sk(X), sl(Y)) for each k=0..n-1 and l=0..m-1. This would lead to an O(n2m2) algorithm (in fact it is only O(nm2) where m ≤ n, why?). However, it is possible to find a better solution, so try to do "your best"!

**Input**

The first line of the input file *[login to view URL]* contains six integers *ccopy, cinsert, cdelete, creplace, n, m* denoting the cost of copy operation, the cost of insert operation, the cost of delete operation, the cost of replace operation, the length of first string and the length of second string respectively. (0<*n, m*<1000, cost of each elementary operation will be less than 100) The second line of the input line contains a string of length n, and third line contains a string of length m.

_ced.inp_ 0 3 4 5 9 10

rithmalgo

altruistic

**Output**

Output of your program is a file named *[login to view URL]*. It must contain a single integer number, giving the cyclic edit distance between two strings.

_ced.out_ 25 |

## Deliverables

1) Complete and fully-functional working program(s) in executable form as well as complete source code of all work done.

2) Installation package that will install the software (in ready-to-run condition) on the platform(s) specified in this bid request.

3) Exclusive and complete copyrights to all work purchased. (No GPL, 3rd party components, etc. unless all copyright ramifications are explained AND AGREED TO by the buyer on the site).

## Platform

UNIX/SUN SOLARIS

Programación en C Ingeniería Linux MySQL PHP Arquitectura de software Verificación de software UNIX

Nº del proyecto: #2998245

Sobre el proyecto