Video 9-1: §9.1 RMQ introduction

0:03 so welcome back to efficient algorithms comp 526 the last time a new unit Unit Nine our our Christmas lecture where we'll talk about range minimum queries I'll tell you what this is in a second uh just to set the scene it's it's a little more advanced towards the end than I was comfortable of putting on the exam so it's it's just for your enjoyment or For Your Entertainment uh but it also nicely closes one last uh black box that we like left open in Unit 8 and since that was just last week I hope you still have some some fresh memories of that I put some learning outcomes but again these are just for orientation uh we'll look at this this problem abbreviated as rmq range minimum

0:50 queries and the connection it has to things we've discussed in the previous unit we'll see some solutions for that and up to this point I think it would be fine to to do it as part of this module uh but in isolation it doesn't add too much um too much interesting opportunities to ask exam questions and then we'll look at the more sophisticated ways that make the best possible solution of this problem possible

1:24 okay uh let's start with a little bit of introduction and what this problem is about so uh first of all just the definition what is the range minimum query problem it will at first sound like a very simple and slightly strange problem why would you care about this uh but we'll come back to that in a minute so the input is just an array of of numbers or arbitrary objects uh static here means it's not changing over time that's to uh simplify the problem and it will be will be interesting in that in in that variant for us already so you have n numbers and uh you can pre-process that array of numbers up front and you can build some build some data structures do whatever you want and then later I'll ask you queries which will always be a contiguous range so some start and end indices and you have to tell me where's the minimum in that range um so in this in this case if I ask for the range minimum query that starts at index 17 index 7 and ends at 15 that's the range so if you look at those numbers two is the minimum so I return that position uh to nitpicks about this I'm not asking for the value of the minimum

2:51 I'm asking for the position so you're returning an index not a a number a value here so you would return 10 and if there's ties then we take the leftmost of those occurrences some would arbitrary but uh that's that's the conventional way to solve ties here so far so good uh let's see

3:18 so just a simple example query to test that we all talking about the same same problem so what you should send back as a as an answer is just one

4:25 that's 66 on the attendance code so maybe we can get a few more here too let's wait until 40 and then okay there we are now here's the results again what you can see is nine people are behind the the one and well a few few other answers okay so let me go through this and

5:05 um I want to draw this the same way uh the range first of all that we're given it starts at index one and ends with index six so the range we're looking at is this that's the part of the array that we're focusing on and only what's inside of this range matters now we're looking for the minimum and the smallest number in that range is four which occurs twice here and here and the actual answer that we return is one because we're supposed to return the leftmost index of that minimum it's here okay that's that's what this is about now you may you may Wonder um why that's at all relevant or even connected to what we've done last time but uh we'll come to that a few more uh comments on the definition first of all notice that everything is comparison based I'm asking for a minimum so all I need to be able to to do is compare two elements two objects and tell which one is smaller so I defined it in terms of numbers because we'll use it for that and it's kind of without loss of generality uh but really it's comparison based so it could be arbitrary

6:25 objects and then we have um unlike in in some other problems we have two types of running times that were simultaneously trying to keep in check one is the pre-processing time that's the time you spend on the array before any query comes and then the time per query and you can you can maybe imagine that there will be some trade-off between the two so what will uh we want to keep both in in our uh uh in our Solutions and be able to talk about both so we I'll use this angle bracket notation to say the two running times are such and such and the first one is pre-processing second one is Crea

7:06 okay so without really knowing or without thinking deeply about this maybe um you want to give me uh your best guess of what could be achievable and I mean if You'

7:22 sorry if you look forward in the slides of course you can find the answer but the the goal would be to get your gut feeling so your answer should be of this of this form with two running times so for example in angle brackets 1 comma 1 would be you spend constant time on the pre-processing and constant time on the queries I'm mean spoiler alert that's not going to be possible that's the kind of format that you're that you're aiming

9:30 answers okay let me show you uh most people seem done okay you you broke the algorithm for doing these worldles uh word clouds the the middle one big O of n for both might be what we could read it as

9:59 um well I don't want to give much away we'll see okay I'll just leave it