Video 1-4: Turnpike Backtracking Example

0:04 I want to briefly come back to our turnpike puzzle. Uh we discussed the algorithm. Here's the corrected version that also does the recursive call correctly or uses the result of the recursive call correctly. Um I've briefly thrown that at you last time without uh a lot of introduction or explanation. Um, all we really had time for was this very short example of how things might work. Now, um, the solution for this example, maybe you, uh, you figured out, um, kind of the explanation I want to give why the algorithm is correct needs to know the solution already. So you could either try to go through the algorithm but then at each point in time you have to make the right guess and you have to do some calculations to see um whether the guess was correct. And usually in this in this instance um is a fairly tame instance. Most of the time you immediately see if you've made the wrong choice then you just get stuck immediately and you can take the other choice. So it's a a somewhat harmless instance and it's small anyways.

1:21 So for the systematic solution, let me just give away what the numbers in this case were. Um, and let me recap the notation maybe for for the problem because this was a slight point of confusion. Last time I started the definition with P which was the weights the sequence of weights of these beads or the sequence of weights of the amino acids in a in a a protein. That's why um I thought it's smart to call it P. The input for the problem really you should rather think of the prefix sums. So S is more naturally the input for this turnpike problem which would be uh or not not the input the output of the turnpike problem. That's the desired locations of the exits on our uh highway. And these these essentially correspond to the uh cumulative sums of these weights, right? The distance the weights would be distances between consecutive exits. Uh prefix sums would be the distance from an arbitrary point is called zero. Say the leftmost exit is zero and then you count from there.

2:29 That's s. That's what we want to find. And what we're given is this um difference multis set of just all the differences between elements. And the way I've defined it here is that we only get the positive differences. Um it's not hard to work out. If you uh drop this restriction here to go over all pairs of i and j then you just get twice the set and you get everything with an with a negated sign as well. These are easy to convert to each other. So either either can be used as an input for the problem. And then the turnpike problem is you're given the difference set and you're trying to find either the weights or uh the prefix sums. Uh we're happy with with either because these are very easy to convert. Okay.

3:23 So in this case um the set S or the the sequence of S well that's the benefit of the prefix sums because they're in sorted order as a sequence you can also represent them as a sum and you don't lose information that might be convenient for doing examples. Is that clear? So, the uh we only need the sound later. The the speakers are driving me nuts. So, if I freak out because the video doesn't have sound, please remind me to turn these back on. So, the positions of our exits on this highway are like this.

4:06 And you can check that if you take all the differences that you get uh exactly this difference set. For example, what we figured out last time already was that uh this this large distance 17 has to be at the end that corresponds to this distance 17 from the beginning to the 17 and the smallest distance is placed at the right end between 17 and 18. Okay. Now what what's the new thing? uh a different way to think about these different sets is to arrange them in a in a two-dimensional uh in a matrix or in a uh a pyramid. Uh if you write down the numbers might need a bit more space and I'm leaving out the zero um doesn't add much interesting. So say these are uh the distances as we have them. Now we have to take all the differences between those to generate the difference multis set delta s. The first one I can make is consecutive differences. So I can take 18 minus uh 17 and um Okay, they arranged this differently than what I thought.

5:41 Um let's take 18 minus 4. So the largest difference I can possibly make takes the most extreme values in in this sequence 18 minus 14 uh 18 - 4 is 14. So let's put that here. And then similarly you can take 17 - 4 and get a 13. So you continue this diagonal that way.

6:12 Trying to write it nice and neatly. And here we get the six from 10 minus 4. So here this guy is this minus this. That's how that comes about. And then we can take um the next smaller sets of distances we get from uh reducing uh one in or subtracting the next larger from everything. So we can take 18 minus 10 to get eight and we can get 17 minus 10 to get seven and 15 - 10 to get five. And then you see we naturally end at the bottom because there's uh 17 minus um uh this there's nothing left apart from the zero taken all the three things below 17 and subtracted them. Okay, let let's complete the thing quickly. So the 15 minus 4 you get 11. Hold on. No, 18 - 15. Sorry, that's three. And 18 minus 10.

7:27 No, I'm I'm taking the wrong distances differences again. Right. 17 minus 4. Done that before. Hold on. What? Where does the next one come from?

7:51 So the uh the three was from 18 - 15 and then 17 - 4, you say? >> Okay, we're subtracting the 15. Sorry. Yeah. Yeah. Okay, this means uh here we're subtracting four, here we're subtracting 10, and here we're subtracting the 15.

8:22 And then we subtract the 17. We get the one that we already have here. Yeah, don't convert between different examples. Um, so this is this is a general how you can arrange the solution or the the difference multi set. If you know what the result is, of course, in general, we wouldn't know this left uh this left spine here, that's the solution, right? If we have that, we're already done. uh the point of of the algorithm is uh the way we got started was also looking at the largest of the numbers and that has to go in the top of this pyramid because uh the pyramid the way it's constructed it's increasing in both directions. If you move up in any diagonal then uh in in this diagonal you're subtracting a constant thing and we've started arranging the original numbers in sorted order. So also these diagonals will always be sorted.

9:29 And for the diagonals in the other direction, you're starting with 18 and subtract successively larger things. So these will always well go down if you move up or increase if you move uh move up the pyramid from bottom right to top left. Same here. I'm taking the 17 and subtract different things. If you wanted, you could say this is the minus0 diagonal, which means the largest number always needs to go into the top. That's the obvious step that we've taken last time as well.

10:09 Again, let me uh write down what we observed. The pyramid And so the topmost element always has to go in the top of the pyramid.

10:40 But that we already knew. There's more we can read from this picture. Namely, where can the second largest number go? It has to be increasing along all diagonals. So if you put it anywhere down here, you get a contradiction because you would have to increase along any diagonal. So it can only be a point that's again maximal in the sense I can't go up further and there's exactly these two slots that are maximal any other you can still move up along any uh of the diagonals that's a kind of easy visual proof that there's only two options for the second largest and that's exactly what we've used last time as well right uh I said after the 18 is clearly the end point let's look at the 17 which gives us the largest distance from either of the end points. And we worked out by kind of geometric intuition as opposed to this invariant that the long stretch of 17 has to be either flush left or flush right. And this corresponds to these two positions.

11:58 And uh there's a little more so we can maybe okay I'm uh maybe not continuing the example entirely but let's suppose we don't know the solution and we try to work out um our way through this uh in a way simulating the algorithm but trying to be a bit more guided by the intuition of this of this arrangement. We know that 18 will have to go up here. That's all we know at the beginning. And then we have the 17 and we can say suppose we take the wrong choice. We put 17 here. Now we have to try and uh deduce what that means about other numbers or other positions in the pyramid. Okay. So for that we have to go back what the the rows meant. Um, for example, if the 17 is here, that means I've subtracted this row here, this diagonal, I have to subtract something. So that 18 minus that thing gives me 17. So it's got to be minus one.

13:09 And that means um the one will be the last one here. It has to go in here. So I know another position. And it has to be the one in this place. Otherwise, it wouldn't match up with the 17. That's about as much as I can deduce at this point, right? There's no um no immediate contradiction and I don't subtract anything think from the one.

13:47 So, we've dealt with the 18, the 17, and the one. These are gone and we now have to somehow get by with the remaining numbers. Now the 15 is the next largest and again we have two maximal positions either in this spot or in this spot where we can put the 15. >> Excuse me. >> Yeah. >> Why can't the one be on the bottom right? The way we construct this uh this matrix um there's a every position here is calculated by taking the number that's in the top left and subtracting the corresponding one on the right. Um so uh without doing index arithmetic in a way you go steps down and that means you move steps up of what you subtract. In the topmost column here, you take the 18 and you subtract the lowest in this direction. I move one step down here. Well, let's take the seven. Again, I'm calculating this value as the difference of two things, namely the 17 here. And then I move one two steps down, which means from the bottom I move one two steps up. So, I'm subtracting the 10.

15:04 And this rule tells you in this case the 17 comes about as subtracting from 18 the bottom left most. So it's got to be one. Now let's do one more example and um maybe we'll see uh how things go. Let's put the 15 here.

15:30 Now again we can uh try to work out um what that teaches us uh about other columns. Um we know the row 15 down has to be filled in the same way as this. So this position here we know has to be 15 minus one. So that's a 14. Uh we still have a 14. So that's fine. Um and there should be one more number that we get.

16:10 I also now know that I'm subtracting 15 at some point. So this last one here must correspond to subtracting 15. So I get 18 minus 15. I have to put the a three here. Okay. So now we should we should uh try to keep track of um the numbers that we've used.

16:44 So the one is gone 18 17 15 and the three is gone. I've crossed out five things, but there's six in here. Am I missing something? The 14. Yeah, that's right. Good. Yeah.

17:36 >> Uh, this position right here. Do we already know what's going there? Maybe not yet. Right. Um, do we know what's supposed to go here? I think we don't we don't need that. We don't know that number. And so we only know we subtract one from something.

18:09 Now the two is the three is gone and the one's gone. Yeah, I think that's all we can deduce. So, we have to try the next number 13. Let's put it somewhere left or right.

18:37 That's the 13 gone. So, what do we learn? Uh we learn that this column now corresponds to subtracting five. So, I can immediately fill in this next one. There should be a 10 here. That one's gone. Um, and I also learned that exactly the five that we subtracted has to be here.

19:19 Can we put more in? Should learn more from this. There should be this one should also be filled right now. 5 minus one is a four. So that still works out. Yeah. Uh I think that's all. So it's always going to be the bottom part here is one shorter than this is long. And same here. This is one shorter than this is long. This dimension. Okay. Okay, I was hoping this would fail earlier, but I guess uh we're done essentially now. So the eight can go at some point. Let's put it here. So we have eight is gone. 8 minus one is seven. That's fine. We can put that. But then 8 minus 5. Um we don't have another three. So at this point we detect a violation.

20:07 And so well all this tells us we've done some mistake at some point. uh but uh there's no no way to know in general where you've taken the wrong turn. Now in our case, we can try to see uh I mean it's symmetric of if you go left or right doesn't matter. But uh I've split the 15 and the 17. Um so that's unlikely to succeed. But maybe the example shows two things. One, it's a bit more intuitive why the two options are really the only thing. Whatever you build the pyramid will always have this this shape that um the current bit nicer maybe what you've discovered is a certain part at the top and then I don't know if this is L by K then you get um a a triangle down here that's K minus one and you get a a triangle here that's L minus one. That's a pattern we've always had. So you always end up with this situation that there's two peaks that are maximal and you can put the next largest free number there.

21:24 Okay. Uh in the exercises your your goal is to make this algorithm fail maximally badly by uh constructing an example where it really takes exponential time. Um now there was there was a question um you can take the the task and the algorithm as they're literally written and that could make the task a bit easier. You can also try to create an interesting example where it's not completely obvious from local arguments that the algorithm could have terminated earlier or could have detected dead ends earlier. uh the algorithm we have in mind is is kind of nasty in that sense. Um I don't think very small tweaks to the algorithm would fix it. Okay, let's make this this important point. Um we've briefly discussed some of it for this unique or uh well, we've already established last time it cannot possibly be unique in the strict sense because you can have left and right symmetries. Peace.

24:10 I think the the middle answer is uh is going to be tricky to quantify, but I'll comment on that a bit of what is known.

24:28 If anyone's still thinking, um, happy to wait a sec. Otherwise, I'll at least show what people voted. If you don't stop me, then there you go. Uh, clear no from 2/3 and some split of the rest. Uh, happy to see that no idea wasn't there. Uh I mean the last one is kind of true but that's not the point why we're figuring this out as mathematicians or um the no is clearly correct in the obvious sense we discussed last time. I can take the differences uh and uh take the mirror image reverse the the protein so to speak or um you can also do it on the on the prefix sums by taking the total and subtracting everything. Either way it's it's symmetric left to right. So the algorithm cannot possibly be more unique than that. Uh but it turns out uh there's nasty examples beyond that. For example, this one is this is from uh from a paper I'll I'll mention in a sec uh in a different context. Um these are two sets of uh distances. So these are S's.

25:44 That's an S1 and an S2. But their different sets are the same not in an obvious way. Uh just mirror images, uh and there's even a recipe to construct more nasty versions. So in in a sense um it's not unique and this is kind of a problem sometimes if your actual example uh is not unique then you you can't possibly know. uh you can also say for in favor of this statement C there's some some things you can prove if your original inputs are not integers but uh real numbers and you draw them randomly then usually you just have these two solutions uh the the unique one and its reverse and no other solution and for this case Um and for these kind of inputs you can also show that the algorithm has expected behavior that's that's polomial but unfortunately that's not very helpful in the application we look at because we kind of have to round the weights anyways there's going to be measurement errors. So this this likely comes from the fact that if if you draw random numbers then most of the differences are unique and so on. Uh there's a lot of uh simplicity coming from just the the richness of the inputs there. Um the mass spectrometry application has the measurement error on top of all of it. So you're not going to make be able to make use of that fact. Uh but it's still mathematically is is of course true.