Space and Time Analysis in Dynamic Programming Algorithms,
Abstract
Dr. Nazir Warsi, in recent work, showed how to solve certain dynamic programming problems while keeping strict bounds on the amount of working storage needed. We discuss extensions of Dr. WArsi's methods and anlaysis to more general dynamic programming networks. We describe a general algorithm for solving problems in this more general class. This algorithm may be applied in such a way as to limit working storage arrays to any dimensions greater than or equal to 2. In making this restriction, there are two costs: a number of arrays of dimension 2 may need to be stored simultaneously; searches for maxima can become arbitrarily complex with the complexity of the network. We discuss the implementation of the general algorithm in a higher level language with particular emphasis on storage management. We also discuss data representations and the practicality of implementing a system for handling general networks. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1984
- Accession Number
- ADP002963
Entities
People
- C. B. Setzer
- N. A. Warsi
Organizations
- University of Atlanta