Video 9-1: §9.1 RMQ introduction

0:00 Introduction

0:01 it our last time welcome back to com556 for this time efficient algorithms we have one one more unit that's kind of my bonus unit um full of some some neat ideas but also a bit on the side so I um I took it out of the exam material but I think it's it very nicely fits into the theme of this lecture maybe just the last bits are a bit too advanced so I I wasn't curious enough to demand that from you uh but I I still think you can enjoy it very much let's see uh it's about the range minimum problem and I'll introduce that what that means and you'll immediately recognize it after a few slides as something familiar but in disguise

0:50 Learning Outcomes

0:53 I mean I do have learning outcomes even though they're not assessed so well I still have the goal that you understand what this problem is and its connection to the longest common extensions okay I gave that away now um uh I think everyone can understand these um these Simple Solutions which are uh not unreasonable to use as well especially essentially is especially the sparse tables and then a bit more interesting is um a connection to something called Cartesian trees I'll get to that uh and then the advanced bit is the the exhaustive tabulation technique that allows us to get to the final performance we'll come to that it's a relatively short unit um I want to introduce this this problem a little bit and then the successively more advanced Solutions

1:37 Problem Introduction

1:48 Problem Explanation

1:51 let's first see what this problem is about uh abbreviated as rmq the range minimum query problem is given an array of numbers or could be other objects it's entirely comparison based say an array of numbers and the goal is um the the game is as follows I give you this array up front and you can have a look at it you can take notes you could build a data structure and then later on I will ask you for range minimum queries which is given a range from I to J where in that position where in that range is the smallest value so here's an example array and an example range and then you can find well the smallest value in that range is the 2 and it occurs several times um so the definition of the arrangement query problem is to find the leftmost minimum that's somewhat arbitrary but you have to break ties somehow and also we'll return the position where you find the minimum instead of the actual value now that's not a big restriction you can just look in the array what's what's there but this will this will come uh come back later it will come in handy in the in a later section it just turns out to be this is more convenient

3:12 ok so relatively simple definition now I mean I haven't told you why this is at all useful this looks like a a nice exercise problem um any food in music you just check if you can solve this but it has very very good motivation but before we get to that let's make sure that the definition is clear so here's some

3:43 no trick question just checking if you're if you're getting all the the bits right um an example array and it could be array I'm not um this is not about your ability to take the memory so if we're given this range from I to J right both endpoints are inclusive in this case maybe a bit inconsistent to how we handle ranges otherwise but I chose it this way in this this module

4:25 foreign I feel for you do I have my coffee then you can see the array we had 23 votes for the attendance code so maybe you can it's nine people who voted I will give you a few more seconds but I don't want to bore the ones uh in the room

5:40 shall we say 15 is the magic number that would be three more on the other hand it looks like all of you are done and that's mostly okay we got one more

6:07 I don't feel very patient let me show the results so again um in this in this image you don't see it so well four people voted for one and then all the other options okay if two people voted for the four six for some reason it doesn't show the commas there's this commas in the actual answer weird okay someone decided for these for these weird diagrams we don't want commas uh but the Emoji survived that's the important bit all right let's let's briefly go through this uh nothing um complicated so we take our our range I set both endpoints are inclusive so we have this range and now we find the smallest value in that range seems to be number four it occurs two times but the definition said pick the leftmost so this is this is our minimum and then the second nitpick was what you should return is not number four but position one so

7:18 that's the answer okay I kind of um I trained myself to write the ones like this so that they're more distinct from other things but then people often mistake it for a seven or something so I have to be very careful to write it clearly good so we understand what the definitions like that's that's good a few observations the the way it's defined it just asks for a Minima and because it returns just the position the queries actually know nothing about the values in the array and there's there's this notion you can you can talk about two arrays being essentially the same for all range main queries the answer of the arrangement query is this just the position so if you have an array and you add a constant to all the numbers for example it doesn't change any of the Minima so many many arrays will turn out equivalent with respect to these range mean queries all right um now for this data structure problem uh there's unlike before maybe um there's there's several things that are important or interesting to look at uh one one parameter is the pre-processing time that's the time you spend when I give you the array up front before we can start the game of actually answering queries

7:38 Observations

8:40 and I'll call that P of n like pre-processing uh notice that the way we Define the problem the space usage of your data structure can also be at most P of n because you have to create that data structure from scratch you have to write it and so you can't even touch more memory than P of n if you spend so much time so in a way this is two parameters it's the pre-processing time and the space for the data structure but we'll see that this is always bounded so by minimizing the pre-processing time with through the back door also make sure we don't use much more space

9:24 and the second parameter is the query time that's the time for answering one query okay to have a short notation I use this these angle brackets so the important bit is just p is before Q in the alphabet and pre-processing comes before query so the first parameter is how much time do you spend when you're given the array first and then the query time is the second thing

9:53 okay let's do a guessing game I haven't told you anything else and so you can know but I'd like to ask you to just guess what do you think might be possible what do you think is a reasonable pre-processing time and query time uh just from your gutting instinct and then you can later compare to the solutions I'll show you

10:37 so what what you're supposed to send is something like a pair of two functions in N so it could be again I don't want to Anchor you on anything specific let me put something so ridiculous that you probably won't be anchored to it you could send uh angle bracket open 2 to the N comma 3 to the N angle bracket close

11:02 I hope you won't come up with that exponential time because that's uh that's way too slow let me let's just leave that open um and while you make up your mind um I'll show you the motivation for that I'm Q problem