Algorithms Homework

Closed Posted Oct 28, 2003 Paid on delivery
Closed Paid on delivery

| |

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

C Programming Engineering Linux MySQL PHP Software Architecture Software Testing UNIX

Project ID: #2998245

About the project

13 proposals Remote project Active Nov 15, 2003

13 freelancers are bidding on average $34 for this job

mihaiscortaru

See private message.

$64.11 USD in 5 days
(159 Reviews)
6.0
thecoder256

See private message.

$25.5 USD in 5 days
(33 Reviews)
4.6
dcrs

See private message.

$42.5 USD in 5 days
(11 Reviews)
4.6
shashikhanvw

See private message.

$85 USD in 5 days
(15 Reviews)
3.8
andreeamvw

See private message.

$17 USD in 5 days
(7 Reviews)
3.0
carefulwith

See private message.

$34 USD in 5 days
(13 Reviews)
3.1
adam16

See private message.

$25.5 USD in 5 days
(13 Reviews)
3.3
ciphereye

See private message.

$11.05 USD in 5 days
(16 Reviews)
2.7
icodeinc

See private message.

$85 USD in 5 days
(1 Review)
0.3
darkrainbowvw

See private message.

$12.75 USD in 5 days
(0 Reviews)
0.0
roard

See private message.

$8.5 USD in 5 days
(1 Review)
0.0
codrutvw

See private message.

$10.2 USD in 5 days
(0 Reviews)
0.0
echion

See private message.

$25.5 USD in 5 days
(0 Reviews)
0.0