In: N. Mastorakis (editor), Procs. of CSCC, July 4-8, Athens. WSES Press.

Authors: Oege de Moor
>

Abstract

Dynamic programming is usually regarded as a design technique, where each application is designed as an individual program. This contrasts with other techniques such as linear programming, where there exists a single generic program that solves all instances. From a software engineering perspective, the lack of a generic solution to dynamic programming is somewhat unsatisfactory. It would be much preferable if dynamic programming could be understood as a software component, where the idea common to all its applications are explicit in shared code. In this paper, we argue that such a component does indeed exist, at least for a large class of applications where the decision process is a sequential scan of the input sequence. We also assess the suitability of C++ for expressing this type of generixc program, and argue that the simplicity offered by lazy functional programming is preferable. In particular, functional programs can be manipulated as algebraic expressions. This paper does not present any novel results: it is an introduction to recent work on the formalisation of algorithmic paradigms in software engineering.

(PDF)

BIBTEX:

           @inproceedings{cscc99moor, 
           author = "Oege de Moor", 
           title = "Dynamic Programming as a Software Component", 
           booktitle = "CSCC", 
           editor = "N. Mastorakis", 
           year = "1999", 
           publisher = "WSES Press"}