# Minimum cost of conversionWatch

Announcements
#1
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? 0
5 years ago
#2
(Original post by evinda)

According to my notes: Why is the cost given by the above formula?Could you explain it to me? 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.
0
#3
(Original post by 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
5 years ago
#4
It's going to take me a while to go through that in detail.

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
5 years ago
#5
(Original post by evinda)
...
OK, that was rather horrendous, but here's my table.

As you can see from the bottom right, 8 is the minimum cost.
0
#6
(Original post by ghostwalker)
OK, that was rather horrendous, but here's my table.

As you can see from the bottom right, 8 is the minimum cost.
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?
0
5 years ago
#7
(Original post by 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?
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
#8
(Original post by 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.
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? 0
5 years ago
#9
(Original post by 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? We can't do it like that as the p is in the wrong position.

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
#10
(Original post by 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.
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 ? 0
5 years ago
#11
(Original post by evinda)
How can we change the two letters to "po"? Don't we have to replace also at this case both "p" and "o"?
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.

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 ? 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.
0
#12
(Original post by 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.
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?
0
5 years ago
#13
(Original post by 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?
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).

PS: If you haven't done so already, I'd write a program to do all this.
0
#14
(Original post by 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).
I understand..Thank you very much!!! (Original post by ghostwalker)

PS: If you haven't done so already, I'd write a program to do all this.
That would be nice,I haven't written a program yet.. 0
X

new posts Back
to top
Latest
My Feed

### Oops, nobody has postedin the last few hours.

Why not re-start the conversation?

see more

### See more of what you like onThe Student Room

You can personalise what you see on TSR. Tell us a little about yourself to get started.

### University open days

• Sheffield Hallam University
Get into Teaching in South Yorkshire Undergraduate
Wed, 26 Feb '20
• The University of Law
Solicitor Series: Assessing Trainee Skills – LPC, GDL and MA Law - London Moorgate campus Postgraduate
Wed, 26 Feb '20
• University of East Anglia
Sat, 29 Feb '20

### Poll

Join the discussion

#### Do you get study leave?

Yes- I like it (110)
59.46%
Yes- I don't like it (9)
4.86%
No- I want it (52)
28.11%
No- I don't want it (14)
7.57%