Skip to Main content Skip to Navigation
Conference papers

Cache efficient simple dynamic programming

Abstract : 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.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/hal-01184040
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Wednesday, August 12, 2015 - 3:52:29 PM
Last modification on : Thursday, May 11, 2017 - 1:03:09 AM
Long-term archiving on: : Friday, November 13, 2015 - 11:40:45 AM

File

dmAD0106.pdf
Publisher files allowed on an open archive

Identifiers

Collections

Citation

Cary Cherng, Richard E. Ladner. Cache efficient simple dynamic programming. 2005 International Conference on Analysis of Algorithms, 2005, Barcelona, Spain. pp.49-58, ⟨10.46298/dmtcs.3368⟩. ⟨hal-01184040⟩

Share

Metrics

Record views

86

Files downloads

928