Opening Cache-Oblivious Algorithms: Searching & Sorting
Cache-Oblivious Algorithms: Searching & Sorting
- Length
- 1 h 18 min
- Level
- Undergraduate
- Recorded
- MIT2016
Chapter 1 of 11: Before the lecture
Derives the optimal cache-oblivious Van Emde Boas binary search tree layout without knowing cache parameters.
Demaine covers cache-oblivious search and sorting in session 27 of MIT 6.046J, an undergraduate algorithms course. He proves a cache bound for least recently used eviction, constructs the Van Emde Boas layout, and analyzes memory transfers in multi-way mergesort.
Demaine covers cache-oblivious search and sorting in session 27 of MIT 6.046J, an undergraduate algorithms course. He proves a cache bound for least recently used eviction, constructs the Van Emde Boas layout, and analyzes memory transfers in multi-way mergesort.
This lecture
Lecture 27 of 27 of Design and Analysis of Algorithms.
Choose a node to see how it connects to this lecture. What comes before is on the leftat the top. The ring is what it teaches. People and places are above. Other lectures and books are below.
Press a chosen node again to open it.
Your comment is kept while you sign up.Sign in