Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.programming > #16710 > unrolled thread

on distinguishing memoization and dynamic programming

Back to article view | Back to comp.programming

Contents

  on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 16:53 -0300
    Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 20:06 +0000
      Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 20:16 +0000
      Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 17:55 -0300
        Re: on distinguishing memoization and dynamic programming Kaz Kylheku <433-929-6894@kylheku.com> - 2024-01-03 22:58 +0000
          Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-01-03 20:19 -0300
    Re: on distinguishing memoization and dynamic programming Tim Rentsch <tr.17687@z991.linuxsc.com> - 2024-01-12 16:41 -0800
    Re: on distinguishing memoization and dynamic programming HenHanna <HenHanna@devnull.tb> - 2024-07-23 12:15 -0700
      Re: on distinguishing memoization and dynamic programming Julieta Shem <jshem@yaxenu.org> - 2024-07-23 21:06 -0300
        Re: on distinguishing memoization and dynamic programming HenHanna <HenHanna@devnull.tb> - 2024-07-24 01:04 -0700

#16710 — on distinguishing memoization and dynamic programming

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?

[toc] | [next] | [standalone]

#16711

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.

[toc] | [prev] | [next] | [standalone]

#16712

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.

[toc] | [prev] | [next] | [standalone]

#16713

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.

[toc] | [prev] | [next] | [standalone]

#16714

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.

[toc] | [prev] | [next] | [standalone]

#16715

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.

[toc] | [prev] | [next] | [standalone]

#16723

Julieta Shem <jshem@yaxenu.org> writes:

> 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?

Memoization is a stand-alone technique for improving the performance
of pure functions, which is to say functions whose result depends
only on their inputs.  The idea is when a result is calculated for a
particular set of inputs, the result is saved so that it needn't be
calculated again for the same set of inputs.  If lookup is cheaper
than recomputing, it's a win to save the result (up to some amount
of saved results, obviously) so it doesn't have to be calculated
again.  By analogy, memoization is more or less a software cache at
the level of individual functions.

Note that there needn't be any particular relationship between the
inputs and the results.  A function might be recursive, like the
fibonacci function, or the different results might be completely
independent, with no recursion at play.  Memoization doesn't care -
the only things that matter is that the output is a pure function
of the inputs, and that lookup is cheaper than recalculation.  When
those two conditions hold, memoization can improve performance (as
before, depending on how much storage is needed to accomplish that).

Dynamic programming is used when there is a single large-scale
problem for which it is necessary to solve a significant number of
smaller-scale problems, and there are relationships between the
smaller problems such that there are dependencies on those smaller
problems that force some to be solved before others.  The key idea
of dynamic progamming is to determine, based on an analysis of the
overall problem, an ordering for the smaller problems that allows
each smaller problem to be solved exactly once.  It is common for
dynamic programming problems that the smaller problems make up a
regular array (of whatever dimensionality) so that results can be
stored in a regular structure, and looking up previously solved
subproblems can be done just by doing a normal indexing operation.

An abstract example of a dynamic programming problem is calculating
a function F of three arguments I, J, K, where computing F depends
on several values of F( {i values}, {j values}, {k values} ), where
each {i value} is <= I, each {j value} is <= J, and each {k value}
is <= K.  By tabulating F in increasing order of I+J+K, we arrange
for the earlier values to be available when computing F(I,J,K).

Incidentally, it can happen that F(I,J,K) is a function of lesser
values of i, j, or k, and also on F(I,J,K) itself.  When that
happens we get an /equation/ that must be solved for F(I,J,K), and
the equation can be solved because values for all the dependent
(smaller) sub-problems are already known.

I wanted to answer your question because memoization and dynamic
programming are really nothing like each other, I thought it would
be good to clarify the two concepts.  Hopefully you got some value
out of my explanations here.

[toc] | [prev] | [next] | [standalone]

#16761

On 1/3/2024 11:53 AM, Julieta Shem 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?



Memoization and dynamic programming are both techniques used to improve 
the efficiency of algorithms, but there are some key differences between 
them:

--------------Memoization:

Focus: Caching previously computed results
Approach: Top-down (usually implemented with recursion)
Applicability: Any function with repeated computations for the same inputs



Example: Imagine a function that calculates the nth Fibonacci number. 
Recursive calls to calculate smaller Fibonacci numbers happen 
repeatedly. Memoization remembers these calculations and avoids 
redundant computations.





--------Dynamic Programming:

Focus: Solving problems with overlapping subproblems iteratively

Approach: Bottom-up (often uses tables or arrays)

Applicability: Problems where solutions to subproblems contribute to the 
solution of larger problems


Example:        Counting the number of ways to climb stairs.
        You can find the number of ways to climb 1 or 2 stairs, and then 
use those to find the number of ways to climb 3 stairs, and so on.


The Relationship:

Memoization can be considered a tool used within dynamic programming.


Dynamic programming doesn't necessarily require memoization, it can 
solve problems bottom-up directly.



Here's an analogy:

Think of memoization as a to-do list app. You write down tasks you've 
already completed to avoid doing them again.

Dynamic programming is like a recipe.          You break down a complex 
dish into smaller steps, ensuring you only perform each step once.

[toc] | [prev] | [next] | [standalone]

#16762

Follow-up to comp.programming only.

HenHanna <HenHanna@devnull.tb> writes:

> On 1/3/2024 11:53 AM, Julieta Shem 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?
>
>
>
> Memoization and dynamic programming are both techniques used to
> improve the efficiency of algorithms, but there are some key
> differences between them:
>
> --------------Memoization:
>
> Focus: Caching previously computed results
> Approach: Top-down (usually implemented with recursion)
> Applicability: Any function with repeated computations for the same inputs
>
>
>
> Example: Imagine a function that calculates the nth Fibonacci
> number. Recursive calls to calculate smaller Fibonacci numbers happen 
> repeatedly. Memoization remembers these calculations and avoids
> redundant computations.
>
>
>
>
>
> --------Dynamic Programming:
>
> Focus: Solving problems with overlapping subproblems iteratively
>
> Approach: Bottom-up (often uses tables or arrays)
>
> Applicability: Problems where solutions to subproblems contribute to
> the solution of larger problems
>
>
> Example:        Counting the number of ways to climb stairs.
>        You can find the number of ways to climb 1 or 2 stairs, and
>        then use those to find the number of ways to climb 3 stairs,
>       and so on.
>
>
> The Relationship:
>
> Memoization can be considered a tool used within dynamic programming.
>
>
> Dynamic programming doesn't necessarily require memoization, it can
> solve problems bottom-up directly.
>
>
>
> Here's an analogy:
>
> Think of memoization as a to-do list app. You write down tasks you've
> already completed to avoid doing them again.
>
> Dynamic programming is like a recipe.          You break down a
> complex dish into smaller steps, ensuring you only perform each step
> once.

It does match my understanding of dynamic programming that it's usually
the term used when the speedups are computed inside the procedure being
optimized, while memoization and caching can be done with complete
disregard for how the procedure internal details.

So, the top-down-bottom-up comparison is pretty interesting, but it also
seem to imply a certain distinction based on perspective.  Science is
usually trying to find things that are there no matter from where you
look.

(*) What's the point of this discussion?  

Understanding.  If there is a very clear distinction and I can't see,
then my understanding can be greater.  Some things are just vague and
that's not really a problem.  For example, what is an operating system?
Very difficult to define with arbitrary precision, but the very people
who study them don't have any problems with that lack of precision.  Is
a high-precision distinction between memoization and dynamic programming
very difficult to get to?  It's not clear to me.  But it's clear that
there are contexts in which we clearly use one word and not the other.

``Cache'' is another word.  Every time we memoize a function, we're
using a cache for it.  So why call it memoization?  Fruits sometimes go
by various names, but that's likely because various peoples named it
independently, which is why ``chocolate'' is typically the same word in
every culture I've seen it---perhaps because each culture imported it
from the same source.

Perhaps that's the case with cache and memoization.  It is true that
``dynamic programming'' was coined by a researcher trying to get money
for his project.  The project had to use buzz words that would attract
the money.  In other words, maybe ``cache'' would replace it just fine.

If these paragraphs are missing out something deeply important about
dynamic programming, then I would like to know.

Thanks for the analogy.

[toc] | [prev] | [next] | [standalone]

#16763

>>
>> Here's an analogy:
>>
>> Think of memoization as a to-do list app. You write down tasks you've
>> already completed to avoid doing them again.
>>
>> Dynamic programming is like a recipe.          You break down a
>> complex dish into smaller steps, ensuring you only perform each step
>> once.


----------- Not a great Analogy....

DP is just a broader term...  one of the methods used is Memoization.




> 
> Thanks for the analogy.


DP= “recursion + memorization”    is  better.




  i  have just  watched most of it (20 min)...  Very good!

https://www.youtube.com/watch?v=Hdr64lKQ3e4

              19:40

Mastering Dynamic Programming - How to solve any interview problem (Part 1)

Tech With Nikola  -- 45.2K subscribers


636,861 views           ( Aug 19, 2023 )

🎬 Mastering Dynamic Programming: An Introduction 🎬

          Are you ready to unravel the secrets of dynamic programming? 
🤔 Dive into the world of efficient problem-solving with this 
comprehensive introduction to dynamic programming. Whether you're a 
budding programmer or an algorithm aficionado, this video is your 
gateway to understanding the magic behind DP.

🔑 Key Takeaways:

📌 Demystifying the concept of dynamic programming.
📌 Understanding the core principles behind dynamic programming.
📌 Unleashing the power of recursion and memoization.
📌 Step-by-step breakdown of dynamic programming problem-solving.

Dynamic programming is like a puzzle-solving technique, and this video 
is your ultimate guide to fitting the pieces together. Get ready to 
elevate your coding skills and witness the art of optimization in action.

[toc] | [prev] | [standalone]

Back to top | Article view | comp.programming

csiph-web