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 <>
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

  • HAL Id : hal-01184040, version 1

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. ⟨hal-01184040⟩

Share

Metrics

Record views

160

Files downloads

1355