🚀 go-pugleaf

In article <22553@alice.att.com>, Fernando Pereira (pereira@research.att.com)
writes:

> In article <1992Apr12.172448.21191@acsu.buffalo.edu> bharat@acsu.buffalo.edu:
>>Regarding 4), may I ask what is a "dynamic-programming solution", i.e.,
>>would you not entertain a top-down solution with memoization?   If not, 
>>why not?  This is a crucial question,  as it has serious implications for all 
>>WAM-based implementations.

> Many thanks for the references. As for "dynamic programming" solutions,
> I was concerned more specifically with the ability to imitate the best
> dynamic programming solutions for problems such as shortest path, not just
> with the ability to store intermediate results (which may not be enough).

You're welcome --- my basic point was that those optimizations with sets 
can be arranged very nicely in a functional-language setting under 
a top-down regime.  And thanks for mentioning the work by R and S 
on distributing min over sets.  

Regarding dynamic programming and memoization,  I have always thought 
that memoization yields the same order of performance as dynamic 
programming, faring better or worse (to within a constant factor) 
depending upon the problem at hand.  But I would think that, for
problems "such as shortest path", memoization would fare better
than dynamic programming because one doesn't have to solve all possible 
subproblems (as one would if one imitates dynamic prog. strictly), 
e.g.,  there might be unreachable segments of the graph that have no 
bearing on the shortest path for a given vertex pair, and a top-down 
scheme with memoization would naturally avoid them.  On the down-side, 
accessing those memo-tables efficiently is not a trivial matter (the
constant-factor problem), but work is in progress on that front ...

Bharat Jayaraman
bharat@cs.buffalo.edu