Video 9-1: §9.1 RMQ introduction

0:00 <Untitled Chapter 1>

0:03 welcome back to com 5 to 6. we'll look this time in our last unit at the range minimum query problem it's a classic data structure problem that at first size seems very innocent and easy but it's quite quite tricky if you look at it closely and it's used in many places to speed up things and we you've seen already one of those places we'll come to that in a second and so it closes off this last missing black box that we didn't look at look we didn't look into at the time but today we'll close that off or today and and next next time

0:41 Learning Outcomes

0:45 i want you to to roughly know what this rmq problem so range minimum query abbreviated what that is and how it connects to longest common extensions in strings because that's the black box i referred to we'll look at some simple solutions and you will all be able to figure these out and then we'll look at some combinatorial objects that are related to this in a somewhat magic way if you want if you first look at it looks looks really dubious but then um i think it's quite quite clean and we'll see how we can use this plus another trick uh that you haven't seen so far to get the the best possible solutions for this for this range minimum query problem

1:36 that's roughly the chapters that we'll look at i'll introduce the problem then we'll dive into some abbreviations and see the simple and then the the fancy solution so let's um start with what this problem is all about the range minimum query problem consists of being given an array and these can just be numbers

1:49 Range-minimum queries (RMQ)

2:03 and so you're given this this array ahead of time and you can look at it and work your magic on it and take notes and then at query time you're given a contiguous range from i to j and you're supposed to find the minimum in that range and that's all so it's quite fundamental the array is static in this case so we suppose the array does never change that's why you can look at it in the first place take your notes and then the array remains the same throughout the time

2:42 uh let's do a small example and uh so here's here's an array of numbers as always we start counting at zero indices start at zero uh and the the range is given as the the leftmost and rightmost index that is included in the range that's the the convention here which means that rmq of 7 and 15 the minimum in this range is any occurrences of the number two that's the smallest that occurs and so what the rmq function returns is the position it's the the index not the number not the minimum but the value the not the value of the minimum but the position where it is attained and if there are several we take the leftmost just to break ties in some way this doesn't usually matter too much but let's uh let's just pick one convention and stick with that so we always want the leftmost position of a minimum in that range okay

3:43 Clicker Question

3:46 time to see if you are awake so here's a another small example um this the question is open on slido but i'll leave up the array because i didn't copy that on the question so here's an array and a sample query what is the return value in this case

4:54 there's more to people on the live stream now as well so expecting maybe a few more 23. anyone still busy in here then um let's switch to slider and show the results i'll leave it open

5:15 so the biggest biggest chunk is for one and that's that's the correct answer and to do this so we first pick out uh pick out the range that is between one and six

5:34 so you just look at this range you can ignore the rest of the array the smallest number in here seems to be four and it occurs as the leftmost position at position one the first here and so one is the val the index that we return

5:52 Rules of the Game

5:54 now what are we trying to do with this and this will this it all doesn't seem to be so well motivated or interesting but um i'll tie it to the application that you've already seen in a second um a few a few remarks before we do that the whole problem is comparison based we just asked what is the smallest thing so it doesn't really need to be numbers it could be any objects that you can compare and so we can we can just take numbers that are convenient to write and they represent whatever object there really is you've seen this over and over again with sorting

6:31 unlike most of the problems we've looked at so far they're really two times two running times that are interesting in this problem and both are important uh we first have the time that we spend pre-processing this array you're given the array you can look at it and there's the second time when you query when i ask when i give you some range you should come back with the minimum and that's a different type of running time and we'll see that there's a certain trade-off between those two indeed

7:06 just for notation we'll call a solution to have to have to write it this time this this way so angle brackets for two two functions two running times just the first is the pre-processing and the second is the query time

7:26 yeah one more thing to note because we we're talking about a data structure you're given the array you build a data structure you don't know which queries are coming so i don't tell you up front i will need this range in this range in this range i just tell you here's your array and then afterwards once you once you've built your data structure there will be queries coming so you don't know in advance which queries or which ranges are needed um and you can you can spend it's kind of clear if you want to you make use of this pre-processing step you have to memorize something you have to store something and so you can use certain amount of space for that and we will not look at this in much detail because the pre-processing time basically bounds the space as well you cannot not really use more space then you have time to write something during pre-processing and we'll see that in the in the cases here the interesting space bounds directly follow from that so the space is never more than the pre-processing time and that's good enough for us otherwise we would have a third dimension you could also talk about reducing the space further good so far

8:46 now let's see again uh this is like um in the last in the last unit i asked you about error correcting codes what do you think is possible to achieve of course without knowing much about this so i assuming you haven't looked at the slides already you there's no no good reason for you to know this but let's just see what do you think is possible so you're supposed to type an answer like this with two angle brackets and then two functions say i don't want to prime you on anything but pick and put in any functions of n like uh n to the 10 and 2 to the n i think these are ridiculously large that no one would really pick them

9:35 so your answer should really be two two functions okay something like angle bracket open 10 n to the tenth comma two to the n angle bracket close that's the the format i'm after

9:56 okay some some come through nicely others are weirdly formatted maybe you want to edit this so there shouldn't be any p's and q's in your answer it's just two functions of n right p and q is just the name of these functions

11:15 so i guess the the big answer is supposed to mean the first function is linear and the second is constant and then we have n log n constant linear and log n

11:29 and and billions of other combinations okay i don't want to comment on this at this point it's it's for you basically to make some guess and then see what comes out of it