I really like the way Erik instead of just giving you the algorithm goes over the rationale at each step, and lets you think about what could you do next to improve what we have. The algorithm is amazing, and the way is exposed even more so as an exercise in algorithm design.
I saw Harvard's Advance Algorithms Lec on Van emde boas trees but the difference between this and the other is just gigantic. I wasn't able to understand the trees structure and operations from the other lecture. Prof. Erik is an amazing teacher!
This guys...his teaching method is so simple and friendly that once cannot immediately fathom who he actually is. He is a child prodigy. Read him up here: en.wikipedia.org/wiki/Erik_Demaine
If you are studying... I implemented the optimized version of all the data structures from the CLRS in python, just import it like `pip3 install datality` -> github.com/Zetinator/datality
space requirement was said to be O(n) at the end, but what about the fact that keys use O(logu) bits? I guess we consider one key to have O(1) space requirement, but bit count for representing a key is in dependence with u, so if we count the bits then it's O(nlogu)
Well, this is one only thing (Van Emde Boas) that I didn't take as a student back in 1992 in Egypt(one reason I'm grateful) I didn't teach it too, because most Algorithms course I taught was Level1 However, I did get something in post graduate courses about especially designed hw implementation in O(log2 n) then enhanced to O(log{log3} n) (and I think that's how am I going to approach it if I decided to teach this under graduate) Starting how comparisons is the most dominant operation, and if we're going to implement a especially designed HW, (a little on practical real life examples like the routing he mentioned and more) Then let's think how the comparison is implemented (comparators) bitwise comparisons How can we do it faster (HW or algorithmically in abstract sense) if we compare only 1 bit? divide the bits into half size (remember that's equivalent to sqrt) Then, I'd go into examples and diagrams of the data structure I think I'll avoid the code and recursive equations, at least till the final version of the algorithm and YES he explained it much better than the published Harvard lecture, but it IS really complicated.. he mentioned he had to contact Van Emd Boas the author himself before he gave this lecture
wait what? the van Emde Boas is actually used a bunch in practice? I did not know that. Thats cool. For some reason I thought their constant factors was really large (maybe thats true for Fib. Heaps and not for van Emde Boas)?
i have question.. so we are basically having 3 layer ( 1. space O(u) the leaf part/// 2. the OR operation part(middle thing O(rootu))/// 3. summary) in every tree level? or do i have just "one" tree level made of 3 layer i think former is right because otherwise we don't need to consider recursion time complexity..?
15.44 could we not just store a 1 bit here at the start of each galaxy. If the array has a bit, then it will be in the first element and therefore we can skip overthose that have 0 bits at the start?
The trouble I have with MIT OCW courses is that.....I follow along, or at least try to .... and then somewhere down the line, the professor mentions something as pretty fundamental and basic and I seem to have no idea of it. And then I slowly creep into depression .... and feel like my life was a lie, and then I go to a corner of my room ..... and cry :(
The good thing about this material is that there is no deadline. Go at your own pace. Here is our suggestion-- if you find something you don't understand, stop the video, write it down, then search for videos on what you are having trouble with. Once you seem to understand it, go back and continue watching. As you keep track of each thing you learn, you will see a list of your new knowledge. Step by step you will see progress. Also, if these videos do not seem to work for you, try someone else's videos on the same subject. Sometimes an instructor explains things in a way that might be confusing for you. Another instructor might be a better match. There is nothing wrong with that. We seen people write that an instructor 'made it so clear to them' and that the 'instructor was the worst, and made everything confusing' all on the same video. Best wishes on your studies!
Actually Éric never speak about it (except at the very end) because it's uninteresting but you need to have a base case for the data structure, depending on the size of the universe, on both sides of your tree (root and leaves). The simple choice is to have a base case for u=1 where you just stock whether you're full or not (so every single function become simple) but as Éric explains, you can stop using a VEB recursively as soon as the size of your universe is u = log(log U) (where U is the size of the complete universe you're searching to stock), at this point you can store your set any way you want even if the operations on this data structure are in O(n) since at this size that means at most O(log log U) anyway. In term of implementation, you may provide an interface with min, max, insert, delete and successor and implement two variations on it, the full Van Emde Boas and your base class.
You could do it in constant time on the initial data structure (the bit vector) but then you wouldn't have access to a summary vector that allows you to do the successor operation in O(log log u), and to efficiently consult the summary, it needs to have a summary, and so on… But that means you need to insert into the summary too, which may need to insert into its summary, etc. Thus the need for recursion. Remember that the point of this data structure is the successor operation : we already have performant data structures for the insert and delete operations.
From the Syllabus: "The primary written reference for the course is: Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848. (www.amazon.com/exec/obidos/ASIN/0262033844/ref=nosim/mitopencourse-20) In previous semesters the course has used the first or second edition of this text. We will be using material and exercise numbering from the third edition, making earlier editions unsuitable as substitutes." For more information and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-046JS15
These lecture a really great, but because he's so efficient at delivering the ideas and the proofs I find that sometimes I have to pause, think or scribble on some paper. Hopefully that might help you also. =)
wait what? the van Emde Boas is actually used a bunch in practice? I did not know that. Thats cool. For some reason I thought their constant factors was really large (maybe thats true for Fib. Heaps and not for van Emde Boas)?
![[#2024MAMA] BIGBANG (빅뱅) - 뱅뱅뱅 (BANG BANG BANG) + FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/EQsYfiPR9uM/mqdefault.jpg)
I really like the way Erik instead of just giving you the algorithm goes over the rationale at each step, and lets you think about what could you do next to improve what we have. The algorithm is amazing, and the way is exposed even more so as an exercise in algorithm design.
I saw Harvard's Advance Algorithms Lec on Van emde boas trees but the difference between this and the other is just gigantic. I wasn't able to understand the trees structure and operations from the other lecture. Prof. Erik is an amazing teacher!
Erik "I was just corresponding with Van Emde Boas yesterday" Demaine
He's incredible even without such amazing correspondences.
This guys...his teaching method is so simple and friendly that once cannot immediately fathom who he actually is. He is a child prodigy. Read him up here: en.wikipedia.org/wiki/Erik_Demaine
@Christopher Migut Haha. He could definitely be a teacher in the magic school bus!
The fundamental theorem of arithmetic is unique factorization into primes (up to order), what is on the board at 21:11 is the division algorithm.
"Let's recurse, shall we"..... Best T-Shirt slogan eveeeeer.
Now I understand the importance of the bit scanning instructions!
If you are studying... I implemented the optimized version of all the data structures from the CLRS in python, just import it like `pip3 install datality` -> github.com/Zetinator/datality
space requirement was said to be O(n) at the end, but what about the fact that keys use O(logu) bits? I guess we consider one key to have O(1) space requirement, but bit count for representing a key is in dependence with u, so if we count the bits then it's O(nlogu)
I watched the entire video... you owe me 4 frisbees.
Why is T(u) = 2*T(√u) + O(1) T'(lg u) = T'(lg (u^1/2) + O(1)? Like why can we replace u with lg(u) and obtain the time complexity for T(u)? Thanks!
do exponential on both sides
So it’s used store credit card numbers or create credit card numbers
Well, this is one only thing (Van Emde Boas) that I didn't take as a student back in 1992 in Egypt(one reason I'm grateful)
I didn't teach it too, because most Algorithms course I taught was Level1
However, I did get something in post graduate courses about especially designed hw implementation in O(log2 n) then enhanced to O(log{log3} n) (and I think that's how am I going to approach it if I decided to teach this under graduate)
Starting how comparisons is the most dominant operation, and if we're going to implement a especially designed HW, (a little on practical real life examples like the routing he mentioned and more) Then let's think how the comparison is implemented (comparators) bitwise comparisons
How can we do it faster (HW or algorithmically in abstract sense) if we compare only 1 bit? divide the bits into half size (remember that's equivalent to sqrt)
Then, I'd go into examples and diagrams of the data structure
I think I'll avoid the code and recursive equations, at least till the final version of the algorithm
and YES he explained it much better than the published Harvard lecture, but it IS really complicated.. he mentioned he had to contact Van Emd Boas the author himself before he gave this lecture
wait what? the van Emde Boas is actually used a bunch in practice? I did not know that. Thats cool. For some reason I thought their constant factors was really large (maybe thats true for Fib. Heaps and not for van Emde Boas)?
It’s used in printing a lot of money to identify the difference and comparison from each bill.
Do you have a reference for that please?
There's one thing I learn everytime I watch his lectures.... don't do anything...just recurse....
How might one describe this structure in complete abstract terms? what is it's mathematical analogue?
incredible.
i have question.. so we are basically having 3 layer ( 1. space O(u) the leaf part/// 2. the OR operation part(middle thing O(rootu))/// 3. summary)
in every tree level?
or do i have just "one" tree level made of 3 layer
i think former is right because otherwise we don't need to consider recursion time complexity..?
brilliant data structure...
15.44 could we not just store a 1 bit here at the start of each galaxy. If the array has a bit, then it will be in the first element and therefore we can skip overthose that have 0 bits at the start?
Erik i love you
The trouble I have with MIT OCW courses is that.....I follow along, or at least try to .... and then somewhere down the line, the professor mentions something as pretty fundamental and basic and I seem to have no idea of it. And then I slowly creep into depression .... and feel like my life was a lie, and then I go to a corner of my room ..... and cry :(
There There
The good thing about this material is that there is no deadline. Go at your own pace. Here is our suggestion-- if you find something you don't understand, stop the video, write it down, then search for videos on what you are having trouble with. Once you seem to understand it, go back and continue watching. As you keep track of each thing you learn, you will see a list of your new knowledge. Step by step you will see progress.
Also, if these videos do not seem to work for you, try someone else's videos on the same subject. Sometimes an instructor explains things in a way that might be confusing for you. Another instructor might be a better match. There is nothing wrong with that. We seen people write that an instructor 'made it so clear to them' and that the 'instructor was the worst, and made everything confusing' all on the same video.
Best wishes on your studies!
@@mitocw wow, great explanation!
Isnt the successor function wrong? It doesnt have a base case. It should never terminate.
Actually Éric never speak about it (except at the very end) because it's uninteresting but you need to have a base case for the data structure, depending on the size of the universe, on both sides of your tree (root and leaves). The simple choice is to have a base case for u=1 where you just stock whether you're full or not (so every single function become simple) but as Éric explains, you can stop using a VEB recursively as soon as the size of your universe is u = log(log U) (where U is the size of the complete universe you're searching to stock), at this point you can store your set any way you want even if the operations on this data structure are in O(n) since at this size that means at most O(log log U) anyway.
In term of implementation, you may provide an interface with min, max, insert, delete and successor and implement two variations on it, the full Van Emde Boas and your base class.
Thank you!
recursion in insert operation is not necessary since we can do it in constant time, I don't understand why he use recursion during insertion operation
You could do it in constant time on the initial data structure (the bit vector) but then you wouldn't have access to a summary vector that allows you to do the successor operation in O(log log u), and to efficiently consult the summary, it needs to have a summary, and so on… But that means you need to insert into the summary too, which may need to insert into its summary, etc. Thus the need for recursion.
Remember that the point of this data structure is the successor operation : we already have performant data structures for the insert and delete operations.
Very interesting
What's the textbook of this open course?
From the Syllabus: "The primary written reference for the course is:
Cormen, Thomas, Charles Leiserson, et al. Introduction to Algorithms. 3rd ed. MIT Press, 2009. ISBN: 9780262033848. (www.amazon.com/exec/obidos/ASIN/0262033844/ref=nosim/mitopencourse-20)
In previous semesters the course has used the first or second edition of this text. We will be using material and exercise numbering from the third edition, making earlier editions unsuitable as substitutes." For more information and materials, see the course on MIT OpenCourseWare at: ocw.mit.edu/6-046JS15
it's Hard. maybe I will have a better luck trying to understand it better from the reference
These lecture a really great, but because he's so efficient at delivering the ideas and the proofs I find that sometimes I have to pause, think or scribble on some paper. Hopefully that might help you also. =)
These videos turn me on
cushions were better :-D
Erik i love you
wait what? the van Emde Boas is actually used a bunch in practice? I did not know that. Thats cool. For some reason I thought their constant factors was really large (maybe thats true for Fib. Heaps and not for van Emde Boas)?