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

Authors: Cary Cherng 1; Richard E. Ladner 1

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

https://doi.org/10.46298/dmtcs.3368
Source: HAL:hal-01184040v1
Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM], [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO], [INFO.INFO-CG]Computer Science [cs]/Computational Geometry [cs.CG], [INFO.INFO-HC]Computer Science [cs]/Human-Computer Interaction [cs.HC], [en] Dynamic Programming, Cache-Oblivious Algorithms, Cache-Aware Algorithms
Funding:
    Source : OpenAIRE Graph
  • Algorithms for Media-on-Demand Systems; Funder: National Science Foundation; Code: 0098012

3 Documents citing this article

Share and export

Consultation statistics

This page has been seen 401 times.
This article's PDF has been downloaded 566 times.