Cache efficient simple dynamic programming
Cary Cherng, Richard E. Ladner · Discrete Mathematics & Theoretical Computer Science · 2005
New cache-oblivious and cache-aware algorithms for simple dynamic programming based on Valiant's context-free language recognition algorithm are designed, implemented, analyzed, and empirically evaluated with timing studies and cache simulations. The studies show that for large inputs the cache-oblivious and cache-aware dynamic programming algorithms are significantly faster than the standard dynamic programming algorithm.