Video 9-1: §9.1 RMQ introduction

0:00 Introduction

0:02 in this last unit of come five to six i want to talk about the range minimum problem uh a very fundamental data structures problem that both has beautiful solutions and it also is the missing piece that we left open in in unit 6 about the text indexing application of longest common extensions and so this is a very nice way to wrap up this class it will be a little bit more advanced material so get well caffeinated definitely for the next session uh we'll start slowly and i'll warn you when i'm when i uh expect that uh you will find some of the material uh tough to digest at first at the first encounter so let's let's get going with this one um what is this about i'll start with a little bit of an introduction what is this problem what's this weird name coming versus weird name coming from my favorite subsection title i won't read it out or tell you what the abbreviations mean by right now and then we'll look at solutions for this range minimum problem uh first the the simple ones that are fairly easy to understand and come up with and then in the last two sections we'll go to the state-of-the-art solution that's also um well it's best possible for obvious

0:53 Overview

1:32 reasons because it's basically the time you need to read the input um and well we'll we'll see what the what's behind this this last subsection then next time all right uh what is the range minimum problem

1:50 RMQ problem

1:54 the range minimum problem or rmq problem for range minimum queries is is the following simple problem on an array you're given an array of of numbers well it can be any comparable items

2:21 is actually fine uh we'll use numbers in the example uh because these are nice and simple but it could be it could be strings it could be whatever object you define an ordering relation on the array is static so that means it doesn't change and the goal is to find the minimum in a range it's a very very simple question here's a range in an array and you can find the minimum well you just walk through it and you find 2 is actually smaller than all the others or at least there's no no smaller one no strictly smaller one this is trivial to do if you have the time to walk through the array the scenario that i'm interested in is we are given this array then we can work on the array in advance and we know the array doesn't change so we can pre-process the array but then we want the queries to be very very fast we don't want them to take linear time to scan through the array we actually want them at the very end okay i don't take that away right now two little details of the definition is we report the index instead of the value that's a minor thing um because you can always look in the

3:37 array so if i say rmq of 7 and 15 is 10 what that means is the range that stretches from 7 to 15 both inclusive um has a minimum at position 10. okay i don't report the two i report the index uh that's just convenient if you have arbitrary objects then an index is always quick and fast to return so you don't have to mess around with any objects and the second thing is we might have ties like in this example there's two twos that's the only ones and uh the minimum is always take the leftmost occurrence of the smallest element in the range okay

4:22 so far so good i think that's it's a fairly simple uh definition fairly simple problem you might wonder why people care about it because it seems so simple that there's not much you can do with it but not so fast it's actually very nice okay um to see if you're if you're following this let's do a very quick exercise on this where do we have this uh here's the question again just remember the two nitpicks we return the leftmost index of a minimum not anything else here's the array again in a little bigger so this this is supposed to be a very simple uh question i'm just testing you if you're still awake basically and also of course we will build on this definition so it's it's important that you have this in mind in the right way um yeah i'll give you a second and well we're not particularly in a rush so it'd be great if we get the same 17 uh answers that we had before the break

5:38 well it seems that a few people left so maybe 17 will be asking for too much i guess the announcement when i said this is not on on the exam is that when we uh when the number of viewers dropped

5:59 um i'll see a few more maybe we can get at least 10 for this for this question it's really simple um don't don't overthink it and if you don't if i was unclear with the definition say um i don't know or didn't understand the problem that's also fine i'm happy to repeat that before we move on

6:33 okay we have seven we can get uh our our 10 answers before i show you what you voted two more guys i know it's getting late in the term yep nine okay i see there's creative answers in there one more

7:07 great there we go and there seems to be a preference for one i'll see if that is what we expect so what does that mean okay uh range minimum query so first of all we have to find the range that this is talking about that's one up to seven that's not too hard we'd go from 1 up to 7 and it's inclusive so that's the range we talk about we're only looking at this range of the array so if you wanted and if that worked well you could zoom in and say we're only looking at this tiny portion of the array and now we're looking for the minimum in this range well four seems to be the smallest number it occurs twice but remember the the second nitpick we always report the first occurrence so this is where our minimum is

8:04 and then the last nitpick we don't report 4 we report the position so that's this one so one is the answer let's zoom this again okay good so everyone's uh up up to speed now i hope we find the minimum in the range we find the leftmost occurrence of that minimum we return its position that's rmq arrangement query all right good

8:47 Commentary

8:47 so we know what the problem is now um a little bit of uh commentary about around this we uh we ask for the minimum so all we really ask for is a comparison based uh question we can do this for arbitrary objects so the values don't really matter the only thing that matters is the relative order they appear in the array in other words if you give me one array and another array and the only thing they differ in is the the types of objects or the values but the relative ranking is the same then every arrangement query will have the same answer

9:30 simple consequence of returning the index and not the value now unlike other algorithms that we talked about we have more quantities of interest in terms of running time here we're already used to have time and space now we have two different times as well we have the the pre-processing time where uh that's that's how much time we take initially to look at the array a and do something smart with it and we have the query time that's the time it takes to answer the arrangement queries using the data structure we built in the pre-processing step a nice result here also just because [Music] okay first state what it what it says if the pre-processing time is at most p of n that also means the space usage of the data structure is at most p of n simply because suppose the data structure would be bigger you would at least need the time in the pre-processing step to write down the data structure so there's no way you can create something bigger than you have time to write it down you need the right you need the to write it down and that takes time so by bounding the preprocessing time we automatically bound the space of the data structure so when i say here two main quantities

10:55 of interest that's a bit of a lie we do care a lot about the space it's just that by bounding the pre-processing time we automatically get a bound on the space and that will be in general already enough to have a best possible solution so a little um piece of notation here is is this angle brackets because we have two times uh we want to make clear which one is which so i'll always give the preprocessing first and then the query time because preprocessing comes before query that makes sense i hope and so we'll just uh write this as a shorthand notation okay so that's the idea you you're given this array you can look at it take your time you pay for that in the p of n entry and then once you're done i'll ask you i'll fire you i'll fire so many arrangement queries at you potentially and then how long you take for each that's the key of n

11:59 Random guesses

12:03 so now um i want to see just some wild random guesses what do you think without knowing the problem without having really thought about it without really having haven't been given the time to think about it what do you think what combination of p and q is is possible to attain and yeah i set this up so that you can send multiple answers so maybe there's different combinations between p and q there's a trade-off between pre-processing query time that's maybe natural because there's also

12:41 a trade-off between time and space if you write down many more things maybe the queries get get easy and if you write down nothing then the queries can't be very fast

12:56 so what i'd like to see is is this pair of functions and it should it really should be two theta classes i think i didn't write this here but it would probably make sense to send two theta classes one for pre-processing one for query um [Music]

13:15 okay i meant just something for example you could write angle brackets of theta square root n comma theta uh n to the five or so obviously those these don't make sense i don't want to give you any anchor uh so that you're free to come up with the answers any way you like it and i think you can see the answers anyway so i might as well show this um [Music] okay you might want to edit the p of n yeah so the the 2.5 um i mean this doesn't work for arbitrarily large uh inputs we have order n for a couple of things what's that pre-processing or query or both

14:10 um theta and theta n that's interesting theta n order 1 i should probably highlight this here that's that's definitely the best you can you can possibly get because you need at least linear time to read the array in the preprocessing step if you want to do anything intelligent and you need at least constant time to report the answer to arrangement query so if you could get this theta n theta 1 then we'd be very happy this one theta and theta n is definitely doable because basically in linear time we can easily solve the arrangement queries even without preprocessing we'll i'll come back to that in a second