I was trying to distinguish memoization from dynamic programming --- in
a technical way --- and I failed. Can you write something like a
mathematical definition of each one?

On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
> I was trying to distinguish memoization from dynamic programming --- in
> a technical way --- and I failed. Can you write something like a
> mathematical definition of each one?

Did you check Wikipedia?

https://en.wikipedia.org/wiki/Dynamic_programming

Dynamic programming is an "algorithmic paradigm" according to this page;
a nice term.

Memoization is a specific algorithmic trick, which is used in some
solutions that fall into the dynamic programming paradigm.
(It is used essentially, so that practically useful run-times
can be achieved: e.g. exponential time knocked down to polynomial.)

Dynamic programming breaks a larger problem into sub-problems which
can be solved separately and then integrated to solve the
larger problem.

Memoization helps when the recursion leads to overlapping subproblems
that lead to an exponential explosion if the duplication is not
identified and suppressed.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

On 2024-01-03, Kaz Kylheku <433-929-6894@kylheku.com> wrote:
> On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
>> I was trying to distinguish memoization from dynamic programming --- in
>> a technical way --- and I failed. Can you write something like a
>> mathematical definition of each one?
>
> Did you check Wikipedia?
>
> https://en.wikipedia.org/wiki/Dynamic_programming
>
> Dynamic programming is an "algorithmic paradigm" according to this page;
> a nice term.

By the way, this "programming" does not refer to writing a computer
program, but to finding a solution that can be used to schedule
a program of events.

That there is a dynamic programming algorithming paradigm doesn't
have anything to do with that we write programs to make it happen.

This explains the "programming" term:
https://en.wikipedia.org/wiki/Mathematical_optimization#History

There is another kind of "programming" in mathematical optimization:
https://en.wikipedia.org/wiki/Linear_programming

That one does not have a related algorithmic paradigm; the computer
version is just number-crunching over the math.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku <433-929-6894@kylheku.com> writes:

> On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
>> I was trying to distinguish memoization from dynamic programming --- in
>> a technical way --- and I failed. Can you write something like a
>> mathematical definition of each one?

[...]

> Dynamic programming breaks a larger problem into sub-problems which
> can be solved separately and then integrated to solve the
> larger problem.

I can't distinguish this definition from ``recursive''.

> Memoization helps when the recursion leads to overlapping subproblems
> that lead to an exponential explosion if the duplication is not
> identified and suppressed.

So it seems to be that memoization is a particular kind of strategy that
falls in the dynamic programming set of strategies. (Thanks for the
historical addendum in your other post.)

Why do they say ``overlapping subproblems'' when it seems that what is
meant is a duplicate problem? For instance, the interval [0, 10]
overlaps with the interval [5, 15], but they're not the same. AFAICT,
memoization is only useful when at least two of the subproblems are
exactly the same.

On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
> Why do they say ``overlapping subproblems'' when it seems that what is
> meant is a duplicate problem? For instance, the interval [0, 10]
> overlaps with the interval [5, 15], but they're not the same. AFAICT,
> memoization is only useful when at least two of the subproblems are
> exactly the same.

The famous example is Fibonacci. If you calculate fib(7) recursively,
fib(3), and others, will show up more than once in the recursion:

fib(7)
/ \
fib(6) fib(5)
/ \ / \
fib(4) fib(5) fib(4) fib(3)
/ \ / \
fib(4) fib(3)
/ \ / \

Why is that called overlapping? Because the left subtree fib(6)
and fib(5) are not the same, but they contain some common content
(nodes that are exactly the same like another copy of fib(5), and
multiple fib(4) and so on).

It's just in contrast to divide-and-conquer, where the problem
space is being strictly partitioned; no part or sub-part of the
left tree occcurs in the right or vice versa.

[0, 10] and [5, 15] overlap, and they have [5, 10] in common.
If that can be solved as a sub-problem, such that we can solve
[0, 4], [5, 10] and [11, 15], and put them together,
that would be better than solving [5, 10] twice and doing
the same thing.

--
TXR Programming Language: http://nongnu.org/txr
Cygnal: Cygwin Native Application Library: http://kylheku.com/cygnal
Mastodon: @Kazinator@mstdn.ca
NOTE: If you use Google Groups, I don't see you, unless you're whitelisted.

Kaz Kylheku <433-929-6894@kylheku.com> writes:

> On 2024-01-03, Julieta Shem <jshem@yaxenu.org> wrote:
>> Why do they say ``overlapping subproblems'' when it seems that what is
>> meant is a duplicate problem? For instance, the interval [0, 10]
>> overlaps with the interval [5, 15], but they're not the same. AFAICT,
>> memoization is only useful when at least two of the subproblems are
>> exactly the same.
>
> The famous example is Fibonacci. If you calculate fib(7) recursively,
> fib(3), and others, will show up more than once in the recursion:
>
> fib(7)
> / \
> fib(6) fib(5)
> / \ / \
> fib(4) fib(5) fib(4) fib(3)
> / \ / \
> fib(4) fib(3)
> / \ / \
>
> Why is that called overlapping? Because the left subtree fib(6)
> and fib(5) are not the same, but they contain some common content
> (nodes that are exactly the same like another copy of fib(5), and
> multiple fib(4) and so on).
>
> It's just in contrast to divide-and-conquer, where the problem
> space is being strictly partitioned; no part or sub-part of the
> left tree occcurs in the right or vice versa.
>
> [0, 10] and [5, 15] overlap, and they have [5, 10] in common.
> If that can be solved as a sub-problem, such that we can solve
> [0, 4], [5, 10] and [11, 15], and put them together,
> that would be better than solving [5, 10] twice and doing
> the same thing.

That's very clear now. Wonderful. Thank you.