Loading...
Please wait, while we are loading the content...
Similar Documents
Staging dynamic programming algorithms (2005).
| Content Provider | CiteSeerX |
|---|---|
| Author | Swadi, Kedar Taha, Walid Kiselyov, Oleg |
| Abstract | Applications of dynamic programming (DP) algorithms are numerous, and include genetic engineering and operations research problems. At a high level, DP algorithms are specified as a system of recursive equations implemented using memoization. The recursive nature of these equations suggests that they can be written naturally in a functional language. However, the requirement for memoization poses a subtle challenge: memoization can be implemented using monads, but a systematic treatment introduces several layers of abstraction that can have a prohibitive runtime overhead. Inspired by other researchers' experience with automatic specialization (partial evaluation), this paper investigates the feasibility of explicitly staging DP algorithms in the functional setting. We find that the key challenge is code duplication (which is automatically handled by partial evaluators), and show that a key source of code duplication can be isolated and addressed once and for all. The result is a simple combinator library. We use this library to implement several standard DP algorithms including ones in standard algorithm textbooks (e.g. |
| File Format | |
| Publisher Date | 2005-01-01 |
| Access Restriction | Open |
| Subject Keyword | Dynamic Programming Algorithm Code Duplication Dp Algorithm Recursive Nature Prohibitive Runtime Overhead Partial Evaluator Automatic Specialization Subtle Challenge Partial Evaluation Standard Algorithm Textbook Operation Research Problem Genetic Engineering Functional Setting Simple Combinator Library Key Challenge Systematic Treatment Introduces Several Layer Functional Language Dynamic Programming High Level Key Source Recursive Equation Several Standard Dp Algorithm |
| Content Type | Text |
| Resource Type | Article |
