Video 9-5: §9.5 Exhaustive tabulation

0:00 <Untitled Chapter 1>

0:04 in the last section of this module of this unit and of this module we'll look at a more sophisticated data structuring technique that i called exhaustive tabulation is also known under the uh slightly unfortunate name for russian's technique i'll come back to that in a second and this will be using the two embedding coding of binary trees that we've seen in the previous section to finally get the arrangement query problem solved in optimal pre-processing time

0:37 it goes back to uh maybe not surprisingly to a paper written by russians but it's not even clear i couldn't dig out if all our russians two were russia two are russian it was the soviet union at the time and some american authors who were working in this area i don't know whether i couldn't find who was the first who committed the original sin uh but it became known as the four russian trick which is uh maybe um a little uh derogatory maybe we shouldn't call it like that so instead um i like to call it the method of exhaust is exhaustive tabulation it's also much more descriptive but i wanted to put this here because if you if you read okay slides are gone if you read um about this technique you will often see it called the for russian trick so it's it's useful to know that this is meant i don't think it's particularly good to call it like that it's not very helpful and not even historically accurate

1:51 good there we are so what is what is the exhaustive tabulation trick to make the confusion perfect is also sometimes called bootstrapping because it it feels very that's maybe not fair to say bootstrapping is a is a technique that you use in combination with this exhaustive tabulation uh by bootstrapping people mean if you you pull yourself on your own bootstrap out of the swamp which in real life doesn't really work right there's no the physics doesn't work out for this uh but computers computer geeks sometimes have a weird sense of humor so you still call it to boot up a computer that comes from bootstrap because there's a little program that pulls out a bigger program and that starts the operating system in some way or another at different levels of abstractions so that's that's still where it comes from the idea of bootstrapping when people use this term is you somehow use something you already have and pump that up just to get something better out of it what does that have to do with arrangement queries we know this sparse table solution which again n log n could be a reti up pre-processing time and space but constant query time so that part we were happy with it's just not quite linear we would like something with

2:00 Exhaustive Tabulation Trick

3:27 linear pre-processing time if we somehow thin out our input don't use all the elements but just every log n element then we can reduce the number of elements to m which is then n divided log n and if you insert that m log m insert the definition you get linear so the bootstrapping part is we use the solution the sparse table one which is not fancy we've seen how this works we use that as a black box but on a smaller input we first have to throw out almost all the numbers just a log one over log n fraction remains but on these numbers we can use the existing technique and we get the optimal preprocessing time so here's an example how this works and i want to point out that the size of of these blocks is chosen so that the rest works out for now you could have chosen any constant in front of the log n but it will become important that these blocks are not too big in on the next slide be resume we break our array into blocks and the blocks have roughly log n divided by four element elements

3:52 Bootstrapping

4:49 each of these little blocks has a minimum somewhere or a leftmost occurrence of a minimum and this minima we promote to a different array b and that's a much smaller array it has only m numbers because we have blocks 1 up to m or block 0 up to m minus 1. shall we give those names

5:16 so this is the the block with id 0 block with id 1 and so on so we would end with block m minus 1. and then the ith entry in this in this blue array is just the index of the minimum inside the ith block so you just store the the result of the arrangement query if you query for the block

5:41 so far so good if we use the sparse table data structure for this small array b the overall space is is order n for the pre-processing and query time is constant so we can solve range minimum queries on this array b that's great but it's not what we originally wanted so it's not so clear yet how this how to make use of that

6:13 but we can puzzle together a general query out of different pieces now so again the red range is our actual query and it can cover any range in particular we have no no guarantee that the user of this data structure respects our block boundaries if the query was exactly from block i to block j we could just reduce it to the the b array but in general this is not working so we could have the query like this this case we're lucky because the the block minimum is actually included in the red range but we don't know if that's true and if it's not true we don't know where the next smaller element is

7:00 but we can always take our query and split it into three queries and some of these can be empty there will be a range in the middle that is only on block boundaries only whole blocks so the blue part is always from a certain block to the end of another block and we have two green queries which are not respecting the block boundaries but they're always inside a single block okay if i know the minimum from the blue range and the two green ranges it takes me three more two more comparisons to find the overall minimum right that's easy we just take uh take the first compared to the middle one if it's smaller you keep the minimum in your hand compared to the last one that's the usual way um the important part is constant time to find the minimum of the red range if we know the minima of the blue and the two green ranges

8:06 you can spell this out more carefully in this formula the arrangement query for the red range actually asks for the index k where the array is minimal and left most of these and this range k is just three numbers now the minimum from the green part the minimum blue part the minimum from the other green part and you can work out um the blue part is an offset of

8:49 you ask the b array for the minimum in this range why do i have to add the b times rmq that's the block size okay that's the the case before this so if this was the minimum in the blue part then um this here would give you the offset inside the block and this one would give you the number of blocks left of it

10:01 so you have to puzzle together the entire offset as the sum of how many blocks are left of this and where in this block that contains the minimum is the minimum that's something you can you can store in in this array

10:22 for the green ranges it's a little easier and here you can restrict it you could write rmq with respect to the whole array a but you can restrict it to just one block because we know it's inside a single block

10:40 so at the end what i said already we have three values to check and and that's easy to do moreover we know how to deal with the blue range the blue minimum only needs rmq computations on this b array and we know that we can use the sparse table data structure for that what's left is these green ranges we know they're all small they only ask for the small ranges up to log n over four elements uh but we don't have a solution for those yet

11:18 so what's left is these intra block queries the queries that are contained entirely inside one block we want overall the same time that we got for the blue range so linear preprocessing constant query time but we have many many blocks the number of blocks is n over log n so we somehow can only spend log n preprocessing time for a block and that is linear so it means we would already need an rmq data structure with linear preprocessing to build the data structure that has linear preprocessing that's a chicken egg problem and that's where the the second part of bootstrapping comes into the into the game

12:08 if you look at one such block it only contains log n over four different it contains log number four numbers and we've seen that there's not so many cartesian trees if i have b elements there's only roughly four to the n different cartesian trees there's a few less but this is an upper bound so we can use at most two b bits to encode any cartesian tree inside the little block so all the possible arrangement queries inside a block the answers can only be one out of four to the b different equivalence classes and at least information theoretically if we don't if we only want to specify what's the right answer without regards to how to find it it's enough to store two b bits for each block

13:09 and um if you do the math here uh this this 4 to the b with our choice of b works out to be square root of n that's not that big so we have a lot of different blocks n divided log n that's almost n but they come from just square root and different types so almost all are kind of duplicates there they look exactly the same through the the arrangement query glasses and so we can we can try to encode them in a more efficient

13:48 Exhaustive Tabulation

13:49 way and that's where the exhaustive tabulation comes into the game so we know we have many blocks but they all look like just a small number of different blocks so we store for all the different possible options how they can look like explicitly what the answers are and we only store for each block which type it is

14:13 so we will store two b bits for each block to encode the cartesian tree in a in a way that is not really useful to extract the answers but we don't care because we also enumerate all possible by um cartesian trees and all possible arrangement queries with their answers i'll show a table on the next slide that makes this a bit more concrete and we just pre-compute all possible cartesian trees and that way we get around this problem that we have these many blocks that we can't really spend time on by reducing it to the much smaller set so that's that's the this is the invention behind the the full russian trick the exhaustive tabulation you have many little blocks but they come from a small set of different blocks

15:03 this representation of the cartesian tree can be computed in linear time exactly using this algorithm that i explained to you the traversal is linear and the type of each node to find is is easy to do in constant time and so what we do is we compute one giant um lookup table and let's let's fill out just for our small example that we had earlier so this type of tree that's the one that we encoded in binary so we did our traversal this one has both children so the code is one one then we go to this node that only has left child one zero and two leaves okay so i would put an entry for this block type

15:57 and every combination of i and j in my case this is just four elements right so this would correspond to a fairly small array and now i can ask what are all the possible arrangement queries i could ask for this tree for example i could ask from 0 to 3 the entire range what has to be the minimum in this case does anyone remember and is willing to puzzle puzzle the pieces together

16:38 remember rmq on the tree translates to going to the nodes of the same inorder index and jumping to the lowest common ancestor so zero three are these notes lowest common answers is the root which has index two so i would put a two in here okay that's how it goes uh and you would fill in all the other combinations right there's not a ton in this small example so we could actually go through these zero and one the lowest commonances is one zero two we get two one two we get two two three we get two you you see a lot of twos here in this small example because that's the root if the tree gets a bit bigger then it's a little less boring and you would copy this in each cell

17:49 i'm missing the one three but uh never mind same same answer so this is this is the idea behind this if our block size was four there would be these six rows for this one choice for the cartesian tree there's a lot of other choices to have a tree over four nodes right so this table would get would go on for a while but it wouldn't go on for too long because there's only root and different trees if our array has length n spending root and extra space is actually a fairly small amount

18:40 so we have a square root and different block types we have roughly b squared combinations for i and j it's a few less because they're in order so we have square root n times log squared and rows and each row if you do it naively can be computed in log n time so if you multiply that all together you're still far below linear so the computation of this of this seemingly huge exhaustive table is actually a tiny fraction of the overall time it's the least expensive bit even though it seems seems to take a while but it's compared to the big array it's nothing

19:28 and so um i should probably have said this before if you go back to the green queries the way to solve the green queries is to look up in a table what's the type of this green block and to compute the the two ranges that you're interested in the i and j

19:51 and then there is one big array that has as one index the block type so you just use that that type as a number and jump into the right row and use i and j as the next indices so it's some multi-dimensional array and the result is just stored there so these green queries are very simple it's just a bunch of array lookups table lookups

20:20 should probably say this uses that we are working on the word ram machine with login bit words that's from far back uh i told you about these machine models in was it unit one or one or two one i guess uh so this this depends a bit on on your machine model whether this counts as constant time array lookups but on all computers that we have you can do array lookups like this so i think it's fair game to say is constant time so you can pull all this together you get a range memory data structure that has linear pre-processing time constant query time and that's the best we can hope for you can plug this in into the longest common extension data structure from unit 6 that closes the last magic black box we did their look into at the time a little bit of a stretch into the world of data structures you can fill this black box as well

21:26 i called it a bit complicated you'll be my judge this is also something that people still look at a bit you can ask the question if you can reduce the space further um and a second nifty bit is you can build data structures that don't need the array at query time so i can give you the array for pre-processing and then take it away from you so you can only answer the arrangement queries then and don't even have the knowledge what is in the array