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 programmingArticle

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.


Volume: DMTCS Proceedings vol. AD, International Conference on Analysis of Algorithms
Section: Proceedings
Published on: January 1, 2005
Imported on: May 10, 2017
Keywords: Dynamic Programming,Cache-Oblivious Algorithms,Cache-Aware Algorithms,[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]
Funding:
    Source : OpenAIRE Graph
  • Algorithms for Media-on-Demand Systems; Funder: National Science Foundation; Code: 0098012

3 Documents citing this article

Consultation statistics

This page has been seen 208 times.
This article's PDF has been downloaded 359 times.