Jiahai Feng

Some notes for the time being

  • Cache Oblivious Algorithms

    Cache-Oblivious Algorithms Cache-oblivious algorithms seemed incredible to me when I first heard about it in 6.854 (Advanced Algorithms). It’s relatively straightforward to imagine algorithms that utilizes information about page size $B$ and cache size $M$ to create efficient data structures. However, cache-oblivious algorithms are algorithms that achieve similar efficiencies without knowing $B$ or $M$. That means the same cache-oblivious algorithm can be run on computers with different cache or page sizes and still achieve the same asymptotic efficiency as one that is tailored to that specific cache.