Path: ...!news.mixmin.net!eternal-september.org!feeder3.eternal-september.org!news.eternal-september.org!.POSTED!not-for-mail
From: Julieta Shem <jshem@yaxenu.org>
Newsgroups: comp.programming,comp.lang.lisp,sci.lang
Subject: Re: on distinguishing memoization and dynamic programming
Followup-To: comp.programming
Date: Tue, 23 Jul 2024 21:06:15 -0300
Organization: A noiseless patient Spider
Lines: 104
Message-ID: <87plr3ejrc.fsf@tudado.org>
References: <87frzembwb.fsf@yaxenu.org> <v7ovh6$1b339$1@dont-email.me>
MIME-Version: 1.0
Content-Type: text/plain
Injection-Date: Wed, 24 Jul 2024 02:06:21 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="693a02952c46e6280c6a8549f9de3501";
	logging-data="1495996"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19XCRa0KZ/y/1TqdW0iM3LPfKtSndJFr08="
Cancel-Lock: sha1:NfmdWYaKkqxh3+OA2VXPVTX+ChY=
	sha1:EJFl+j8JRRNMQ2P5Yqpw9px1JkU=
Bytes: 4892

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.