Cary Cherng ; Richard E. Ladner
-
Cache efficient simple dynamic programming
dmtcs:3368 -
Discrete Mathematics & Theoretical Computer Science,
January 1, 2005,
DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
-
https://doi.org/10.46298/dmtcs.3368
Cache efficient simple dynamic programming
Authors: Cary Cherng 1; Richard E. Ladner 1
NULL##NULL
Cary Cherng;Richard E. Ladner
1 Department of Computer Science and Engineering [Seattle]
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.