so this is cs224 Advanced algorithms uh my name is gelani Nelson uh and we have a TF who's in the back it's Jeffrey with his hand up if you want to contact us uh you should email cs224 df14 D staff at C's. harvard.edu um also there's a a yellow sheet of paper that's going around you should fill it out uh let's see what else should I say and there's a course website so I won't bother writing the URL of the course website on the board just Google the course or Google my name and it's on linked from my website right one thing I will say about the course website is we have a mailing list um so please go to the website and sign up put yourself on the mailing list um before I get started with things uh I guess I'll tell you some logistical things about the course then I'll tell you what the course what the goals of the course are and then I'll start on something okay so uh Logistics oh I I completely did it backwards okay so there are three components to this course in terms of grading one is scribing and this is 10% of your grade basically you just do it and you get the 10% so um there's no textbook for this course students will will take turns taking notes on what I say in lecture and the the course is recorded so you can go back over the lecture and see anything you missed and then basically write up some lecture notes um in lwtech describing the lecture and there's a template on the website a ltech template to to use two is uh pets that's 60% of your grade okay and the third one is a final project which is the remaining 30% and that's just written okay so there are details on the website about the final project you do it the last day of reading period you submit your project and um I grade it okay so let's see final project so there's a proposal for your final project do I think it's on the website but I think it's October 30th and then project do last day of reading period okay um so yeah I'll read through the proposals and make sure I like the idea of the project and give you feedback regarding it and then you spend the last six weeks working on the project roughly six weeks um let's see what else pets All Pets should be law teched and there's and um you submit them by email okay and also pets have page limits meaning your pet should not be longer than the specified page limit okay uh to avoid people just typing uh mindlessly if they don't know the answer to a problem okay so actually brief Solutions are appreciated uh there's one part of the course that um so we'll see how many people actually stay in this class right now it looks like a lot but you know it's shopping period uh depending on the SI the final size of the class or actually this will most likely happen um students will also take turns being graders you probably only have to do it once during the semester but uh a team of maybe three to four or some number of students together with the TF will meet once a week and uh or once per P set and do and grade that P set okay so that's a required part of the class um students have to be greaters at least once okay and these things are first come first serve and and you have to scribe at least once possibly twice if the class gets very small um these things are first come first serve so if there's a date that you really want you know you'll be available to scribe for example then sign up right away before it gets taken also scribe notes are due the following day so you have a little more than 24 hours to describe your lecture notes um they're doe 900m on the following day um is there something I wanted to say about that yeah I mean uh I know it's a short amount of time so just do the best job you can and then I might make a Passover them myself and make some edits okay good so I think that's all I want to say about logistics any any questions about that yeah May oh okay put them in okay I'll maybe I'll maybe talk to me afterward because I I don't anything else yeah only a subset of students will be describing each lecture or everyone describes every lecture um one like no one person will be the Scribe for that lecture actually yeah I need a scribe for today so who's who thinks that they're going to be in this class for sure and is willing to subcribe today's lecture okay um good any other questions okay so uh good so this is Advanced algorithms uh who's here who has taken cs124 or some form of algorithms course before this okay a lot most people I guess um so I guess the main difference between cs124 and CS2 24 well well first of all I guess algorithms is very broad so even though 124 was a whole semester of algorithms we didn't see all there is to know about algorithms even in terms of topics so uh in 224 we'll see some models for analyzing efficiency or some measures of efficiency or models of algorithms that we didn't see in 124 um also I guess it will be more uh Theory focused there won't be any programming assignments all though for the final project you can do an implementation project that's described on the website but the pets will be purely uh just written written pets okay no programming [Music] um uh what else do I want to say so I guess the goals of this course I guess there're what you would expect uh increased ability to analyze and create algorithms okay we're going to see lots of different techniques in this class for analyzing algorithms some of many of which were not in 124 and also modeling you know creating uh so uh looking at different models we're seeing you know inspiration for models uh looking at different models within which to analyze algorithms so in in 124 we usually just looked at say running time and running time we didn't I guess really ever Define it it was just the number of steps of the algorithm and we also looked at memory minimizing the amount of memory used by the algorithm but here there will be other parameters that we'll look at as well okay um so I think I'm just going to get started and I use the wrong board first So speaking of models um so who who here has seen sorting okay good that's what I expected uh who here knows that you can't sort n numbers faster than n log n okay um so that's actually it's I lied to you you can sort n numbers faster than n log n okay so today and uh the next lecture we're going to see something we're not going to do the the full sorting algorithm but we're going to look at a related problem a data structural problem which is uh predecessor uh we'll look at the static predecessor problem say static predecessor problem okay so this is a data structural problem so uh the data structure represents a set uh s of items X1 up to xn okay and we support one kind of qu query um which is predecessor of X predecessor of X is the max element which is less than X or let me say predecessor of Z is the maximum X and S uh let me write like this the maximum X and S such that X is less than Z okay um we want low space and fast query and this word so predecessor you see why that's there static in in data structure speak static just means that the set s of items doesn't change if you had said a dynamic data structural problem like Dynamic predecessor you would also support the insertion and deletion of items okay we'll also look at um so static versus Dynamic static no insertions Dynamic insertions okay so what's one way someone knows how to solve uh dynamic or static predecessor quickly using say linear space in a binary search tree oh store the numbers and do binary search yeah you yeah so um an example solution that works store numbers sorted and then do binary search is this static or dynamic static okay so this is static and what's the query time login okay and what if you wanted login Dynamic query time yeah so um uh log so I'll l in Dynamic query using a balanced BST say like a red black tree or something and the second solution also supports log n for updates for insertions and deletions okay so if you use I mean this is not uh TR no okay uh this is not usually the way people uh teach sorting algorithms at first but you know I claim that if you have a such a solution to Dynamic predecessor um then you can get and let's say all the numbers are distinct okay uh you can get you can get a fast sorting algorithm right so what do you do to get a fast sorting algorithm using Dynamic uh predecessor you you first go through in linear time your input and find the maximum and then you go through the input again and just insert them all into a a predecessor data structure okay and then now you output the max you compute its predecessor now you have the second biggest comput its predecessor Etc and you'll retrieve all the items in sorted order so you've just sorted the elements using a dynamic pred processor data structure okay and what I'm going to show you today and as well as Thursday is uh a faster Dynamic predecessor faster than log n okay so actually uh I won't exactly show you that today I'll show you um I'll show you two data structures uh one of which is dynamic and the other I'll show you the static version it can be made Dynamic but it's more complicated I'll just show you uh the basic idea is to get the static data structure but I I promise I'll give you a reference that shows you it can be made Dynamic and if you use those data structures you can beat um you can beat and log in for sorting okay but some people raised their hand when they said that they knew that sorting couldn't be done faster than n log n okay so for the people who who said they know sorting can't be done faster than n logn um what assumption are you making about sorting algorithm comparison it's comparison sort it's comparison based sorting right which means you have n items and in each step your algorithm is allowed to choose two items and compare them and based on the results of the comparison it can make further comparisons okay but that's not how real computers work right so when you code in C um first of all all the input numbers are integers let's say or floats there there's something that fit in some say 32 or 64bit word and you can do bitwise exor and bit shifting and all kinds of other operations which are not just comparison and multiplication right so that inspires the word Ram model okay so items are integers in uh the range from 01 up to 2 the wus one okay and W is the word size and the universe size U is two to the W this 2 wus one is 2 the wus one okay and we also assume also assume that pointers fit in a word okay so so for the last assumption if you have a data structure that's storing n items presumably um presumably your data structure is using at least n space to even remember what the items were right so we know that space is at least n okay and if a pointer fits in a word well a pointer is what an address into our space so w should be at least log of the space which we just said is at at least log in okay so we're always going to assume that uh our word size W is at least log in okay and what I'm going to show you today and on Thursday are two different uh predecessor data structures that get different bounds one is going to be better when w is small like closer to log n one is going to be better when w is very large so two data structures so one is the uh it's called the van well that's a lowercase van M deoa trees uh this is from what year somewhere in sometime in the 70s so um I'll frequently put the conference or Journal name in the year so this is for the scribes um and this is due to vanm deaz and if you Google it you'll find a reference so please put a reference in the Scribe notes and what this gets is um update this Dynamic so it supports updates update and query are both going to be uh log W time okay and the second thing that I'm going to cover and it's um and we're going to show also that well let me let me say something else the unfortunate thing though is going to be that the space the space is going to be U and you know I like I like linear space independent of the universe size right imagine if you have a 64-bit machine U is 2 to the 64 so I don't want to use 2 to 64 space uh ever um and we'll we'll see that uh this uh can be made Theta n with randomization and we'll also see a related data structure called uh y fast y fast trees tries which get the same bounds okay and uh this is due to Willard in IPL 83 so originally vom deaz and his paper didn't get linear space um but the move from u space to linear space is going to turn out to be pretty simple and the second data structure we're going to see um so this is the one that can be made Dynamic but I'm only going to present the static version in class otherwise it gets too complicated uh these are Fusion trees okay and this is due to fredman and Willard I believe in jcss 93 okay and these support query in time uh log based W of n okay and it's also linear space so already this beats binary search trees right if W is at least log n log remember log based W of n is the same thing as log n over log W so this is never going to be more than log n over log log n okay but of course we could choose based if we know w i mean we know the machine that we're coding on if we know w we can choose the better of fusion trees and let's say vanam trees or yast trees so we can that implies that we can achieve the Min of log W and log base W of n right and the Min of this is if we want to maximize this expression uh we'll do it when these two things are equal which means log W equals log n over log W which means log n is the square of log W okay which is so this will be always at most square root log in okay okay good um and I mentioned that this can be made Dynamic so in particular that means you can sort in time n times the square root of log n okay um things that I won't cover in this class um this implies with Dynamic Fusion trees uh o of n root log n sorting okay question um so okay so there's G to be an yeah so there's an issue which I haven't discussed which is the pre-processing time to actually create the data structure so in the dynamic case when you start with an empty data structure um that doesn't come into play but with the static case we're going to spend polinomial time to actually create this this Fusion tree and that's G to be bad for sorting any other questions okay so you could ask you know is n root log n the best sorting algorithm uh in this model and you you can actually get faster sorting okay so you can get o of n log log n deterministic uh this is due to Han and stock 2002 you can also get uh o of n s square root log log n expected time randomized this is due to Han and thorup um in Fox of 2002 which is about five months later and it's an open question whether or not you can get a linear time sorting algorithm in this model so it's possible there's no there's nothing saying that you can't do it okay and let me go back to the word Ram model before I actually present the vanm de Boaz data structure okay so um so I mentioned we can do more than just compare so what can we do so in word Ram assume that given XY fitting in a word we can do basically all the things that you can do in say C so you can do integer arithmetic so plus minus I mean divide times minus and this is integer div division so it rounds down okay um you can also do uh bitwise negation xor or and uh and can't can't write and properly okay and you can also do bit shifting with some fixed constant or with each other or okay yeah yeah uh so so we'll assume that for multiplication it fits in two words so the upper bits will be in the in the second word yeah okay any other questions um though I think it's also I think it's also accurate to say I mean we don't we don't need to I think make that assumption um there could be integer overflow in which case we'll get the Overflow of the correct answer but um you can simulate at multiplying bigger numbers using in the word Ram anyway but so maybe I'll leave that as an exercise you might need to use a couple words yourself when you when you do the the arithmetic okay so we can do these in constant time so just out of curiosity who's seen Venom deaz trees so one H the infusion trees okay so I'm okay good just making sure I'm not teaching you something you've seen okay so we're doing vanz okay so the basic idea is well I guess you guess that we're going to do something with fudging with bits because we can't just do comparisons the basic idea is kind of divide and conquer okay so um so VB trees will be defined recursively Okay so what a v what a VB tree will look like and it'll be parameterized by the universe size so let's say this isign a universe say of size U it will look like if I open up what it looks like inside of that data structure it'll have square root U VB data structures on un each on a universe of size square root U and there will also be a top one of size of on universes of size square root U okay and separately we'll also store one extra element which is the minimum element in the data structure and I'm going to say more okay so you know let's say you're using some uh objectoriented programming language and you wanted to declare the fields that your veb data structure has so the fields of VB uh let's say on a size U Universe you would have an array of size root u a root U size array uh let's call this thing uh v v is our VB data structure you'd have v. cluster uh zero up until do cluster < TK uus one and this is a VB square root U data structure what I mean is the elements in here are numbers between zero andun uus one uh we'll also store the Max maybe I'll say that too let's say we also store the max I'm going to write that down here um we also have a uh V Dot summary is a VB square root U instance as well and V do Min V do Max are integers in the range from zero to uus one okay any questions I haven't actually told you how you insert into this St this will be a dynamic data structure so I haven't told you how you query and I haven't told you how you insert so let's see that okay so say we have an item that we want to have living in this data structure so X is some integer okay so we can write we can write X in binary okay and we can divide X into the upper half the leftmost half of the bits and the rightmost half of the bits let we call this C let we call this I so let's write X as c i okay and notice that these numbers C and I are in the range from zero up to root U minus one right okay so we're basically writing X in base root U and the idea behind vanm de Boaz trees is that we will store you know if x lives in the data structure then we will store the number I in the Seth cluster okay in this picture okay so um now tell me if you if given what I just said how would you say do a query for the predecessor of X and people hopefully people agree that you can extract you can extract C and I each in constant time just by bitwise uh anding and shifting okay okay so how would you search for the predecessor of X in a in this recursive data structure as I've defined it guess I didn't tell you what the summary does let me tell you what the summary does too um so I told you that I'll insert I into the uh Seth cluster okay also if the cth cluster happened to be empty when I did the insertion I'll also insert C itself into the summary okay so the summary keeps track of which clusters are nonempty that's the point of the summary okay so now how would you do a predecessor yeah you have your element extract the element look that cluster theive thater it's theow element thater you find the next okay yeah so what you said works there's one there's one recursive call you could save right which is you know we store them in explicitly ah yes okay so um so so let me just uh say repeat what you said but using that fact are you here for advanced algorithms yeah okay well uh okay so here is the idea right so I can extract C and I each in constant time using shifts and and masking with with an bitwise and and then what I do is I look in the Seth cluster okay and I look at the Min the minimum element in the Seth cluster if I'm bigger than it then I know my predecessor lives in the same cluster as me and I can just recursively do a predecessor in that cluster a predecessor on I in that cluster if there is no minimum element if that clust if that cluster happened to be empty um or maybe I'm bigger than the men bigger than or equal to the men then I know my predecessor is not in my cluster he's in the he's in the largest cluster before me that's non empty and how do I find that I find that by doing a predecessor on C in the summary and then I return the max inside of that cluster okay um okay good I don't need to recurse on that cluster I just returned the Max uh good so let me let me write that down so uh so predecessor takes his input v as well as this x which I write as CI okay and I say the first if is if if x is bigger than v. Max so if X is bigger than everything in my data structure I just return v. Max okay otherwise I look at the cth cluster of v and I check its Min and compare its Min to me Elsa V do C do Min is less than x then I'll just recurse okay otherwise otherwise what I have to look in the summary for the predecessor cluster so C Prime will be my predecessor cluster and then I return the maximum element in that that uh in that cluster okay okay so the next thing is the insertion algorithm okay so the first thing is we're going to see why in a moment but I'm going to treat the minimum element as being special it's only going so the minimum element will be stored in this minimum field uh where my Fields the minimum element will be stored in the minimum field but I won't also store it in its appropriate cluster okay so it could be that the the v. Min is some non-empty value and everything else in the data structure is empty so if V is empty I'm going to say V do Min gets assign to X and then I'll return sorry for my pseudo code is like changing between C and python but you know what I mean I think okay otherwise what do I do based on what I've told you and also this with this constraint that the Min only lives in v. min I'll say one thing if if the Min only lives at in v. Min I'll do if x is less than v. Min then I'll swap x with v do Min before I continue okay so now I know that the X I'm actually inserting is is not the minimum element think of this v. Min field as being like a buffer so the minimum always lives in that buffer and it's not actually recursively stored okay so so first I make sure that the thing I'm inserting recursively into the structure is not the minimum okay and then where do I have to put it okay and let's pretend that when I do this swap uh the C and I are for the new X okay so I don't want to write more code um so what I do is oh and there's also this issue of uh before before I recursively insert it into the cluster I should check the summary to see if that cluster was empty if so I need to insert it into there as well so what how can I check if uh um if the cluster is empty I can just check its uh minimum element and check that it's empty so if x uh if sorry if v. cluster C do Min is uh is a null value then I need to insert C into the summary then v. summary I'll insert into v. summary the value um C and then I'll insert I into cluster C okay and you can think about what you would do for deletion it's not really that much different conceptually okay so let's just analyze the running time of uh of these procedures so predecessor if uh there's only ever I guess one recursive call right in any of the in any of the if cases you'll have at most one recursive call so we have the recurrence so for predecessor time we have the occurrence that t of U we start off with Universe of size U is equal to T of U over 2 plus o of one oh T of root U sorry and if you remember your occurrences this implies that t of U is of log log U okay which is equal to uh log W remember U is uh basically 2 the w u is two to the W okay how about insertion yeah uh oh yeah so yeah that's right so you can in constant time you can follow a pointer and read the value in that memory address okay so how about insertion time it looks a little worrisome right because this if doesn't necessarily return return after the if right so if V do cluster. Min is empty you insert it into the summary and then you again do another insertion so it looks like it looks like um T of U is at most 2 * T of root U plus o of one right and uh do people know so another way of thinking about this is maybe this will make it more obvious is that t of w is is at most 2 * T of w / 2 plus o of 1 right so if we're saying that W is getting square rooted that basically means this if we're saying you get square rooted that's like saying w got cut in two so what does this resolve to it should yeah w okay um yeah so this solves the W okay so that's not great we're trying to get log W here but I claim that this is overly pessimistic why first yeah go yeah exactly right so what y said is if this if actually happens then the second if will be shallow and not recurse further right because the second if will be in this case and will immediately return okay so actually this two really can be written as a one you can think about this one as in that case you can think about just moving this line here and then this another else okay um and this implies that t of U is also o of log log U okay so that's the basic vom to Boaz tree data structure and that's also why we stored them in kind of separately right to make the insertion cost log log U as opposed to W which would be log U right if you had if yeah if you actually like if you if you treat them in as the same as any other object and store recursively in the data structure then will be times when you have to recursively insert into the summary and recursively insert insert into the cluster and and that will cost you that will make things double you yeah oh yeah I keep forgetting about these Maxes yeah uh no you don't have to yeah but yes um that's a good point and where's that paper that where people are signing up has it been passing around everyone saw the paper raise your hand if you didn't write your name down on that piece of paper so toward the front I guess okay so how about the space what's the space of the vanomas data structure what's the recurrence anyway s of U is equal to squ otk of U + one for the summary s ofun of U uh plus a constant toor say the Min okay so this I'm not going to solve it here this implies that s of U is Theta of U okay so this is uace which is not great um so we're going to get instead linear space okay so what's what's something that intuitively seems a little bit silly about this space requirement you a lot of empty clusters right I mean yeah that's that's it okay so what could you imagine uh doing instead so we will see who here has who here has seen hashing or okay so I gave you a hint so you know what so you know that there's something called hashing um what would you do with this hashing in order to improve the space yeah so so okay so we're going to have a hash table what is this hash table store sorry like what are the keys in the so in hash tables there are keys and values okay so what are the keys that will live in this hash table and what will the values be so we'll have a hash table keys will be yes the keys will be like these cluster IDs okay so keys keys are cluster IDs C and uh what will the value so what will the value be yeah a pointer to some so value is a pointer to corresponding non-empty cluster okay so for the empty clusters they don't live here okay and I claim that the space of now this scheme is linear it's Theta of n why is it Theta of n how would you account for all the space that's being used in a way that makes it clear it's Theta of n yeah yeah each tree has a minimum element right so we can charge this pointer and and value this is like this is like two words right we can charge the cost of these two words of storing this uh cluster ID and pointer to the minimum element that's contained in that cluster okay and now each minimum element each element is stored as a minimum somewhere okay maybe at a leaf maybe at a leaf cluster in this recursion but it's stored as a minimum somewhere um and each minimum element is charged exactly once in this way right it's charged in the parent VB tree that contains it so charge the cost of storing C pointer to Cluster C to the minimum element of cluster C each minimum is charged so each each item in the set let's say each x s actually is charged exactly once does that make sense questions about yeah uh this assumes that yeah so um I I guess I haven't covered hashing yet we will see hashing later in the course but turns out that it's possible to so first of all uh let me say something about hashing maybe this will answer tell me if it doesn't answer your question once I say it so you know I think it's it's good to think in terms of problems and then there are algorithms or data structures that solve those problems so let's forget about hashing what's the problem that we want to solve the problem want to solve is what's called The Diary problem so short aside so we have something called the dictionary problem okay and the goal of this problem is to store uh key value pairs I'm going to assume that the keys and the values each fit in a machine word and the semantics are as follows so query K okay what should that do it should return value associated with key K or or null if K is not associated to anyone and there's also insert or you can think of as associate so insert a key with a value which Associates value V with TK okay so you can look at both the static and dynamic versions of the dictionary problem so in the in the static version you're told all the key value pairs up front and you never do future associations in the dynamic version you can make updates to what keys are associated with and you can also delete keys from the hash from the dictionary okay and it turns out um I don't know if we'll see exactly this solution later in the course but we'll see some solutions to the dictionary problem um Dynamic dictionary is possible with linear space okay constant query time worst case query time worst case query as well as constant expected insertion or updates insertion and also deletion uh let me write so this is from it's actually not that it's fairly Rec recent ditzell Binger I need to look back at the reference but uh this is from by ditzell Binger and others and yeah I mean it's some form of hash table okay um if you if you know about Universal hashing that would get it wouldn't get worst case constant query it would get expected constant query it turns out you can get worst case but so um yeah the point is that whether it's expected or or worst or worst case and actually you can even do better than expected constant time you can do constant time with high probability but the point is really what we need here is a dictionary okay we need a dictionary that stores uh mapping the keys are the cluster IDs and the values are these pointers to those nonempty clusters and that's a that's a solved problem which we'll just take as a black box for now did that answer your question yeah okay any other questions um yeah I believe well I can even say you can even do make this with high probability so I guess the question is can this I mean the only thing you could hope to improve here is make make it fully deterministic um I don't know off hand whether that's been ruled out as a possibility okay so I have about a little more than 15 minutes left I mentioned that there's another data structure called a y Fest tree or Y fast try which also gets this bound I'll sort of just sketch the idea um which apparently is the which apparently I think is the original way uh Venom de trees were made to to support the bounds that I stated and then much later other people came along and kind of uh reinterpreted the data structural ideas and came up with what I showed you um but the Y fast try I mean originally vom de Boaz data structures were described in a way that got usace and it wasn't as it wasn't as clear as change this to a hash table in the way that it was described to make it linear space so I'll show you the um another way that you can get the same bound Okay so um what's one way that pretend you didn't care about query time and you're willing to use uace what's a very very simple data structure uh for predecessor I want you to use exactly U bits of space yeah a bit array okay so have a bit array of size U of length U and the I bid is one if I is in your set otherwise the I bit is zero so use a bit array so uh another solution we can use a bit array of length U so let's say U is 16 or something so um 1 Z one one 0 z0 1 one one zero one0 0 one one0 0 okay so this corresponds to elements 0 1 2 3 up to 15 okay and so what's the running time of predecessor now it's you okay that's terrible so we're gonna make one small tweak to this which is we're going to build a perfect binary tree over all of these leaves and and each internal node each internal node is going to store The Ore of its two children and we end up up with a tree that looks like this okay now suppose now someone gives me a zero um suppose someone gives me a zero and asks for the predecessor okay uh well okay so let me also say let me also say this uh I'll do one more thing too I'll store all the ones in a doubly link list okay so suppose someone asked me for the uh predecessor of a one what would I do yeah go back one in the link list constant time suppose someone asked me for a predecessor of a zero so for example they asked me for the predecessor of this element okay what would I do okay and then what okay so um I go up so I go up the tree until I find a one okay and then I know that so here when I found when I transitioned into a one I went up this way right so then I know that I am bigger than everything on the left hand side so I should just find the maximum element uh in this sub tree which I can do by uh going down to ones for example okay um but what if I what if someone asked me for the predecessor of this element I would go up and here's the first one so now you know I don't go and find the minimum element here that's not my predecessor but what is the minimum element here it's my successor the minimum element here is my successor and all the are stored in a w link list so I can just go back one and that will be my predecessor okay so I can just keep going up until I find a one and then uh either I either I will find the predecessor or the successor depending on whether I went up that way or went back that way and I can get this I can get the predecessor okay now so now there's there's still one problem though which is what's the running time of this what's the height of this tree log of you so my running time it seems like it would be log of you okay so I'm trying to get log log you so what does that suggest binary search yeah actually I do want to do a binary search but can you so um justify why can I where am I doing a binary search search and why am I doing a binary search okay the lowest one right so so the point exactly so the point is on any Leaf to root path the bits are monotone okay meaning that they're zero for a while and then they're one after that so I can binary search and find the first one and that will give me log log you there's still a catch though which is how do I binary search on following pointers right like if I need to follow seven pointers I need to actually you know I need to actually follow them how can I just access the guy who's seven above me and right you see what I mean any ideas on that yeah it be the right like yeah so if it's stored the right way so what's the what's the right way yeah so you could you know you could store this entire tree so I don't know if people remember binary heaps you could store this entire tree as an array this is index zero that's index one and that's index uh two so in general let me write this store tree as an array okay root is at index zero node V has left child at 2v + 1 and right child at 2v + 2 right so if I want to find the ancestor who K above me what do I need to do divide by what by two to the K but integer division right so that's a bit shift so I can find anyone who's K above me and constant time okay so there's that so this implies can find kith ancestor in constant Time by doing bit shift to the right by K that's a bit shift okay another thing you could do which uses more space is to actually store the tree using pointers but for each node you don't just store its parent but you store its two to the kth ancestor for every k so could also for each node store its two to the kth ancestor for each K going from zero up to log log U because the tree has height log U that would make the space of the data structure U Times log logu or U Times log W okay but there's still the dominant part of the space is you yeah ANC will follow particular what what do you mean like my is like I'm to yeah you mean the the height of the 3 is 16 yeah of the I'll go to yeah and then from8 I can go to 12 or right from 12 I go to 14 I see uh is that accurate oh I see you're saying I only need an but okay so suppose that suppose so suppose the eight one fails so let's do a bigger power of two24 suppose 512 fails now I have to go to 256 yeah that fails and I have to go to 128 yeah won't I need all all those oh I could I could just use the the ancestor of that node yeah okay um I have to think about it maybe what you're saying is accurate so he's saying so I'll exact number suppose the highest power of two yeah which divides your number is 2 to the L okay the height of the tree is two to the L no no no for every nde yeah take it number okay and and suppose the high highest of two the device that is 2 the L okay then you store two the L by two then Su the thing that follows you by a distance of L by2 and the thing that I see uh for okay well maybe what you're saying I have to think about what you're saying but anyway I'm going to do better space right now because uh I'm still using uace I'm still using more than uace and I want to use linear space um so so here's I mean so we the main trick to using to getting linear space in the vom Boaz data structure was to use a hash table to store non-empty clusters so I I want to do something similar here okay so any thoughts again using hash tables so this one maybe is a little trickier so I'll just say it to save space Only Store the ones in a hash table okay so at each level of the tree there are at most n1s so this hash table contains n times W items in it so I'm using n * w space or you could imagine having W different hash tables one for each level of the tree which stores all the ones that occur in that level so for each level of tree hash table stores locations of ones okay so when as I'm doing my binary search if I want to know whether something is a one or a zero I just look it up in the hash table and if it's a Miss in the hash table if it's not in my dictionary then uh I know it's a zero okay this implies space n * W and this is called an xfast tree so if you look at if you look at the paper by uh I mentioned that y fast tries are due to Willard that was an 83 it's like a four-page paper including the intro and bibliography and in the first page or two he describes xfast tries and then and then he then he gives a y fast tries in the very next section uh which is which eliminates that W okay so and the trick to eliminating that W is a trick that is good to know guess I mentioned One goal of this course was knowing the right techniques to apply to data structures and algorithms so this is a technique that gets used a lot so from xfast to Y fast use what's called indirection okay this is a so the basic idea is I'll have my data structure okay I'll have my xast try it takes NW space this is an xfast try on N over W items what do you know it uses n space but what's each item so these are my n over W items each item if you if you open it up it's actually like a super item that contains roughly W items okay so approximately this contains like the first W items the xw items Etc and one of them will be like the representative item that actually lives in the X fast try okay and the way that I'll store these items is I'll build a balanced binary search tree on them okay yes Theta W let's say so I mean there's a problem besides the space you know the okay so I'm I'm basically there's one minute left let me just say this I'll just sketch this you've already seen a solution that gets this bound so you know if you want to see the full details of the yast try you can read about it on on your own but I just want to give you a flavor of of what's going on here so the space is NW okay um but actually the time is also W instead of log w why is the time W the time is W because if you think about this tree if I change if I insert a guy and change him to one I need to like or all the way up the tree I need to change W things so the time is w and the SPAC is off by a factor of w and this idea basically fixes both issues and the Bas so in terms of the space this is now definitely using linear space in terms of the query time the query time is still log log U because I can search in an xfast try in log log U time and then I reach the BST containing that super item and to search in that BST takes log W time which is again log log how about insertions so the point is these super items contain somewhere between let's say w over two and uh two w items okay um uh so they're going to contain Theta W items and the basic idea is going to be when I do an insertion I'm not going to actually insert into the xast try I'm going to find where it goes and insert it into the balanced BST and only when this thing overflows when it becomes size bigger than two w I'll split it into two super items and then insert those into the above one but approximately that only happens like every W steps okay so in an amorti sense um it only costs me a constant to do that well it only costs me kind of I only have to do that once every W steps and then when I do it it costs me log of uh log of w so I know I didn't go into the full details on that but that's uh I'm not going to get too deep into y fast tries since they get the same exact bound as this I think simpler one um but that's the basic idea okay so questions class is basically done qu any final questions before next time we'll see Fusion trees and actually I do want to say one thing which is so I told you the bounds for Fusion trees and I told you the bounds for um Venom de Boaz trees there's actually a paper that shows a matching bound which shows that you can never do better than the Min of vanm De Boaz and and uh Fusion trees or a treat a slightly tweaked version of vanm deaz so these are known to be optimal for linear space or for nearly linear space data structures okay okay so