# Minimum cost of conversion Watch

Announcements

Page 1 of 1

Go to first unread

Skip to page:

Hello!!!!

We are given 2 strings and and the following 3 operations are allowed:

We are looking for the optimal sequence of operations(sequence of operations with the minimum cost),for the conversion of the string to the string .

According to my notes:

Why is the cost given by the above formula?Could you explain it to me?

We are given 2 strings and and the following 3 operations are allowed:

We are looking for the optimal sequence of operations(sequence of operations with the minimum cost),for the conversion of the string to the string .

According to my notes:

Why is the cost given by the above formula?Could you explain it to me?

0

reply

Report

#2

(Original post by

According to my notes:

Why is the cost given by the above formula?Could you explain it to me?

**evinda**)According to my notes:

Why is the cost given by the above formula?Could you explain it to me?

You can visualise this as a grid of points running from 0 to m on the x-axis, and 0 to n on the y-axis. Your goal is to reach the point (m,n) by the cheapest route - starting from (0,0).

At each stage you can go one step to the right, or one step up, or one step diagonally up & right.

As in dynamic programming, you start at the point (m,n). Consider T(m,n) to start and how you could have gotten to (m,n) and hopefully all will become clear.

0

reply

(Original post by

Looks like the start of a dynamic programming problem.

You can visualise this as a grid of points running from 0 to m on the x-axis, and 0 to n on the y-axis. Your goal is to reach the point (m,n) by the cheapest route - starting from (0,0).

At each stage you can go one step to the right, or one step up, or one step diagonally up & right.

As in dynamic programming, you start at the point (m,n). Consider T(m,n) to start and how you could have gotten to (m,n) and hopefully all will become clear.

**ghostwalker**)Looks like the start of a dynamic programming problem.

You can visualise this as a grid of points running from 0 to m on the x-axis, and 0 to n on the y-axis. Your goal is to reach the point (m,n) by the cheapest route - starting from (0,0).

At each stage you can go one step to the right, or one step up, or one step diagonally up & right.

As in dynamic programming, you start at the point (m,n). Consider T(m,n) to start and how you could have gotten to (m,n) and hopefully all will become clear.

For example,if we want to convert the string to the string ,knowing the costs:

I created the following matrix,that is at the attachments.Is it right? If so,is the minimum cost of the conversion then ? Or am I wrong?

0

reply

Report

#4

(Original post by

For example,if we want to convert the string to the string ,knowing the costs:

I created the following matrix,that is at the attachments.Is it right? If so,is the minimum cost of the conversion then ? Or am I wrong?

**evinda**)For example,if we want to convert the string to the string ,knowing the costs:

I created the following matrix,that is at the attachments.Is it right? If so,is the minimum cost of the conversion then ? Or am I wrong?

From a quick check I got 8, but it could be less.

Notice that

So, for instance, T(11,10) = T(10,9) = T(9,8)=T(8,7) since each time we're adding the same letter to each, "l", "a", "i", respectively.

So, we can effectively forget about the last three letters and just work with converting "exponent" to "polynom"

0

reply

Report

#5

(Original post by

...

**evinda**)...

As you can see from the bottom right, 8 is the minimum cost.

0

reply

(Original post by

OK, that was rather horrendous, but here's my table.

As you can see from the bottom right, 8 is the minimum cost.

**ghostwalker**)OK, that was rather horrendous, but here's my table.

As you can see from the bottom right, 8 is the minimum cost.

To find ,do we have to delete two elements and replace the first one,so , by ?

But,then wouldn't it be equal to ?

Or have I understood it wrong?

0

reply

Report

#7

(Original post by

Nice!!!

To find ,do we have to delete two elements and replace the first one,so , by ?

But,then wouldn't it be equal to ?

Or have I understood it wrong?

**evinda**)Nice!!!

To find ,do we have to delete two elements and replace the first one,so , by ?

But,then wouldn't it be equal to ?

Or have I understood it wrong?

So, only need to delete "ex", hence T(3,1)=4

There is more than one route to get there, but that's the shortest.

0

reply

(Original post by

T(3,1) relates to converting "exp" to "p"

So, only need to delete "ex", hence T(3,1)=4

There is more than one route to get there, but that's the shortest.

**ghostwalker**)T(3,1) relates to converting "exp" to "p"

So, only need to delete "ex", hence T(3,1)=4

There is more than one route to get there, but that's the shortest.

0

reply

Report

#9

(Original post by

I understand..So,to find ,do we have to delete one letter(e or x) and replace the one we haven't deleted, by o , since we already have a p? Or can't we do it like that?

**evinda**)I understand..So,to find ,do we have to delete one letter(e or x) and replace the one we haven't deleted, by o , since we already have a p? Or can't we do it like that?

T(3,2) relates to converting "exp" to "po"

We could delete the "ex" to get to "p" and then add the "o" to get to "po" at a cost of 6.

But there is a less costly route, delete the "e" to get to "xp" and then change the two letters to "po" at a cost, in total, of 4.

**Edit:**It should be possible to determine a route from the table, but I'm just going out now.

0

reply

(Original post by

But there is a less costly route, delete the "e" to get to "xp" and then change the two letters to "po" at a cost, in total, of 4.

**ghostwalker**)But there is a less costly route, delete the "e" to get to "xp" and then change the two letters to "po" at a cost, in total, of 4.

Don't we have to replace also at this case both "p" and "o"?

Is it possible to change the position of a letter ,knowing that the only allowed operations are to insert a letter,to delete a letter and to replace a letter ?

0

reply

Report

#11

(Original post by

How can we change the two letters to "po"?

Don't we have to replace also at this case both "p" and "o"?

**evinda**)How can we change the two letters to "po"?

Don't we have to replace also at this case both "p" and "o"?

Is it possible to change the position of a letter ,knowing that the only allowed operations are to insert a letter,to delete a letter and to replace a letter ?

**Also**I realise you can't determine the optimum route easily without having the costs of each step also recorded in the grid.

0

reply

(Original post by

Sorry, I though it was obvious what I meant. We change one letter at a time, which is why the cost is 1+1=2. And 2 for the deletion, making 4.

Yes. By using a combination of the first two you can change the position of a letter, but the cost is cd+ci for each position moved, all other things being equal.

**ghostwalker**)Sorry, I though it was obvious what I meant. We change one letter at a time, which is why the cost is 1+1=2. And 2 for the deletion, making 4.

Yes. By using a combination of the first two you can change the position of a letter, but the cost is cd+ci for each position moved, all other things being equal.

**Also**I realise you can't determine the optimum route easily without having the costs of each step also recorded in the grid.Could you tell me why the green boxes are wrong?

For ,I thought that we replace the letters e,x,p,o by p,o,l,y and that we insert then the letters n,o.So,the minimum cost is ,since if we would keep "po",the cost would be greater.

Am I wrong?

0

reply

Report

#13

(Original post by

I tried to create again the matrix,that is at the attachments.

Could you tell me why the green boxes are wrong?

For ,I thought that we replace the letters e,x,p,o by p,o,l,y and that we insert then the letters n,o.So,the minimum cost is ,since if we would keep "po",the cost would be greater.

Am I wrong?

**evinda**)I tried to create again the matrix,that is at the attachments.

Could you tell me why the green boxes are wrong?

For ,I thought that we replace the letters e,x,p,o by p,o,l,y and that we insert then the letters n,o.So,the minimum cost is ,since if we would keep "po",the cost would be greater.

Am I wrong?

We can do replace e,x,p with p,o,l at a cost of 3, insert y,n at a cost of 4, and then the final o costs nothing.

**For T(6,5).**

Notice that in your version you have T(6,5) = T(5,5) +

**3**. Clearly you can find a cheaper route from T(5,5).

PS: If you haven't done so already, I'd write a program to do all this.

0

reply

(Original post by

Notice that T(3,5) =7 for converting "exp" to "polyn". The next letter in each case is an "o", so no cost, hence T(4,6) is at most 7.

We can do replace e,x,p with p,o,l at a cost of 3, insert y,n at a cost of 4, and then the final o costs nothing.

Notice that in your version you have T(6,5) = T(5,5) +

**ghostwalker**)Notice that T(3,5) =7 for converting "exp" to "polyn". The next letter in each case is an "o", so no cost, hence T(4,6) is at most 7.

We can do replace e,x,p with p,o,l at a cost of 3, insert y,n at a cost of 4, and then the final o costs nothing.

**For T(6,5).**Notice that in your version you have T(6,5) = T(5,5) +

**3**. Clearly you can find a cheaper route from T(5,5).
(Original post by

PS: If you haven't done so already, I'd write a program to do all this.

**ghostwalker**)PS: If you haven't done so already, I'd write a program to do all this.

0

reply

X

Page 1 of 1

Go to first unread

Skip to page:

### Quick Reply

Back

to top

to top