Opening Cache-Oblivious Algorithms: Medians and Matrices
Cache-Oblivious Algorithms: Medians and Matrices
- Length
- 1 h 20 min
- Level
- Graduate
- Recorded
- MIT2016
Chapter 1 of 11: Before the lecture
Demaine pits recursive matrix multiplication on a space-filling layout against dot-product scans.
Cache-oblivious algorithms run efficiently at every level of a memory hierarchy without knowing the block size or cache size . In session 26 of MIT 6.046J, Demaine starts from the two-level external memory model, which counts block transfers between cache and disk. Scanning an array costs transfers, and Bentley's two-finger reversal shows that parallel scans keep that bound. Divide-and-conquer analysis stops at subproblems that fit in a block or in cache, adapting linear-time median finding to contiguous sub-arrays. Demaine then contrasts dot-product matrix multiplication with a recursive version and proves LRU replacement within a constant factor of optimal. The material assumes recurrences and asymptotic notation.
Cache-oblivious algorithms run efficiently at every level of a memory hierarchy without knowing the block size or cache size . In session 26 of MIT 6.046J, Demaine starts from the two-level external memory model, which counts block transfers between cache and disk. Scanning an array costs transfers, and Bentley's two-finger reversal shows that parallel scans keep that bound. Divide-and-conquer analysis stops at subproblems that fit in a block or in cache, adapting linear-time median finding to contiguous sub-arrays. Demaine then contrasts dot-product matrix multiplication with a recursive version and proves LRU replacement within a constant factor of optimal. The material assumes recurrences and asymptotic notation.

This lecture
Lecture 26 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. What comes after is on the rightat the bottom. 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
Cache-Oblivious Algorithms