4. Divide & Conquer: van Emde Boas Trees

Подписаться 5 млн

Просмотров 76 тыс.

50% 1

MIT 6.046J Design and Analysis of Algorithms, Spring 2015
View the complete course: ocw.mit.edu/6-0...
Instructor: Erik Demaine
In this lecture, Professor Demaine introduces the van Emde Boas Tree data structure and its uses.
License: Creative Commons BY-NC-SA
More information at ocw.mit.edu/terms
More courses at ocw.mit.edu

Опубликовано:

8 окт 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 51

@miguelguerrero2498 4 года назад

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.

@dieganga 2 года назад

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!

@abhinavkhanna8378 5 лет назад

Erik "I was just corresponding with Van Emde Boas yesterday" Demaine

@Adityarm.08 4 года назад

He's incredible even without such amazing correspondences.

@johnhart1790 6 лет назад

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.

@singularity108 7 лет назад

"Let's recurse, shall we"..... Best T-Shirt slogan eveeeeer.

@j7gy8b 3 месяца назад

Now I understand the importance of the bit scanning instructions!

@cupidvogel 8 лет назад

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

@elliott8175 4 года назад

@Christopher Migut Haha. He could definitely be a teacher in the magic school bus!

@damerkman 5 месяцев назад

I watched the entire video... you owe me 4 frisbees.

@davitmelikidze9030 Год назад

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)

@abhishekshah5961 5 лет назад

incredible.

@shashankfromindia Год назад

brilliant data structure...

@iridapajenga8481 Год назад

Erik i love you

@shymaaarafat1342 5 лет назад

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

@brandomiranda6703 8 лет назад

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)?

@erickzetina193 4 года назад

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

@Thien--Nguyen 4 года назад

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!

@luojihencha 4 года назад

do exponential on both sides

@jce8847 5 лет назад

So it’s used store credit card numbers or create credit card numbers

@Adityarm.08 4 года назад

Thank you!

@jce8847 5 лет назад

It’s used in printing a lot of money to identify the difference and comparison from each bill.

@shymaaarafat1342 5 лет назад

Do you have a reference for that please?

@enlgn7050 3 года назад

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 :(

@astropiu4753 3 года назад

There There

@mitocw 3 года назад

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!

@rudrapratap3303 3 года назад

@@mitocw wow, great explanation!

@aSeaofTroubles 8 лет назад

How might one describe this structure in complete abstract terms? what is it's mathematical analogue?

@dohyun0047 4 года назад

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..?

@SS-ld2hk 3 года назад

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?

@Antox68 7 лет назад

Very interesting

@kunwarshaanjeetsinghgrover2102 4 года назад

Isnt the successor function wrong? It doesnt have a base case. It should never terminate.

@chaddaifouche536 2 года назад

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.

@abhijitbub6672 3 года назад

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

@chaddaifouche536 2 года назад

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.

@kaustavguharoy4532 3 года назад

There's one thing I learn everytime I watch his lectures.... don't do anything...just recurse....

@beeszu5038 7 лет назад

What's the textbook of this open course?

@mitocw 7 лет назад

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

@mohamednofal5256 5 лет назад

it's Hard. maybe I will have a better luck trying to understand it better from the reference

@elliott8175 4 года назад

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. =)