Dynamic Programming: The Name (1984)

It's "IP" (intellectual property) because it's something the company designed, and it's a "core" because it's a circuit that performs a computation.

I don't really see how it's comparable to the linked example.

I dont mean to sound like coorperate but theres good reason to talk about things like this. With a term like "ip core" you know exactly what your selling and your target audience. Its not an intellectual property or product but the building blocks for it. When approaching other businesses you can view their "core" as weaker or stronger and you can specify how many resources are being spent on "ip core" vs "user experience".

Something like research may imply a length process of unknown length. Dynamic programming implies adaptable steps to reach a goal. In ways, bureacratic speak is a more perfect for of english considering its more descriptive in the context of money, time and action with the goal of maximizing profits and minimizing expenses.

IP cores are certainly more marketable than a software library. The standard Xilinx environment has a license key system that makes it easier to enforce terms of use.

That's a much better name – I may start using that. Viva la revolucion!

Cool name!

There was also a /r/compsci thread [0] a few months ago with some other interesting suggestions like "iterative recursion" and "divide-and-conquer with caching".

[0]: https://www.reddit.com/r/compsci/comments/3u3520/if_you_coul...

Alas, the weight of history is against reason here.

But the "programming" part of "dynamic programming" is the older synonym for "optimisation" like in linear or quadratic programming, not for writing general computer programs. It's not the same kind of "programming" as in OOP or FP.

On first impression, the name appears to imply a Paradigm which was not the original intent I believe ? EDIT: "the name" referring to the original name i.e. Dynamic Programming. What you recommended is closer to what happens actually.

I think I agree with people who call it "exhaustive search resulting in optimal solution where search space is generated incrementally in deterministic polynomial time"

Hmm :-/... I guess I'll stick with the conventional acronym, sounds less daunting and even somewhat cool that way.

> It also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible.

> Dynamic memory allocation, in the context of realtime/embedded systems. :-)

Dynamic typing in the context of writing, maintaining, or refactoring large scale code bases.

Dynamic constant? ;).

Oh my me too. Every time I come across the concept, I get bothered and feel like I must have missed a core concept of it, as the naming never made any amount of sense for me.

For some reason, this truly brings me some amount of peace. Both that the name was applied for non-obvious reasons, and that I'm not the only one to find the name misfitting.

Oh I wish I'd learned this last year when I had a Dynamic Programming module in Systems' Biology course. The name never particularly made sense to me, and seemed like memoizing was the core principle -- which is definitely smart, but I didn't see a reason how it was dynamic. :)

Me to. It's such a vague general purpose complement you could apply to anything, like "elegant programming" or "usefulness oriented". And it turns out that was just why it was chosen!

I regret that I have but one up vote to give

- "You mean caching?"

- "Nope, memoization."

- "Uh ok."

The problem with "memoize" is people always think I'm trying to say "memorize" with a speech impediment, especially because both words usually (kind of) make sense in the context.

That was my first thought too. I thought the page was referring to DP/Memoization[1], initially. Thats the most useful concept I learnt about a decade back, and was fortunate to be able to find a case in real-life to apply it.

I have often a hard time explaining it though. But very simply (the way I explain) it is, you compute and keep lot of results for lower values e.g. value of f(x,y) where x,y are less than some larger n,m respectively. And for computing f(n,m) you would need to compute f(x,y) a number of times for varying values of x,y. So if you keep it in memory. You save hell lot of a computing time. And your program runs in a fraction of time of what it would take other wise.

[1] https://www.topcoder.com/community/data-science/data-science...

Edit: minor correction

There was a large blob in the installers for System 7 (mac) that was named Cerulean Data. I wonder if that was truetype related data.

A dynamic building A dynamic highway Though those may give connotations of resistance to earth quakes.

Dynamic accounting can sound like accounting that is done fast, so maybe still

Anything put in scare quotes can be used pejoratively.

>dynamic" application of the Law? Some things (not a lot) should really be static.

We have human judges precisely because a statically enforced law would be unfair and inappropriate to handling the complexity of human lives.

Dynamic programming is when you break a problem into sub problems and then cache the solutions of the sub problems so the work is only done once.

Some common situations where dynamic programming is useful are when you need to do anything involving finding combinations or permutations of a series of possible actions.

My recommendation for you if you really want to get it is to read and program for yourself the problems on this website

http://www.geeksforgeeks.org/fundamentals-of-algorithms/#Dyn...

Try solving them both recursively and iteratively and by the time you reach the 5th or 6th problem you should have built something of an intuition for when to use dynamic programming.

You know how when you try to implement a function to compute Fibonacci numbers naively with recursion you end up with a minor performance problem?

In Python:

    def fib(n):
        if n < 2:
            return n
        else:
            return fib(n - 1) + fib(n - 2)

This is pretty close to a literal transcription of the definition of a Fibonacci number.

The problem is that we end up recomputing intermediate results quite a bit. Here's a slightly modified version of the above function, which counts the number of times that fib() is called with each n as an argument:

    numbercounts = dict()
    def fib(n):
        global numbercounts

        numbercounts[n] = numbercounts.get(n, 0) + 1
	
        if n < 2:
            return n
        else:
            return fib(n - 1) + fib(n - 2)

Calling fib(20) and then printing the values of numbercounts gives us the following. This shows for each value of n, how many times it was evaluated. I have cleaned it up a bit below for display.

    n: number_times_evaluated

    0: 4181
    1: 6765
    2: 4181
    3: 2584
    4: 1597
    5: 987
    6: 610
    7: 377
    8: 233
    9: 144
    10: 89
    11: 55
    12: 34
    13: 21
    14: 13
    15: 8
    16: 5
    17: 3
    18: 2
    19: 1
    20: 1

The key observation is that fib(low_number) gets called many, many times for fib(high_number). You may notice an interesting trend in the number of times fib(n) is called. The number of invocations for n is fib(1), for n - 1 is fib(2) and so on. That's not important, but just cool.

Anyway, we will have to evaluate the same intermediate result many times. We can optimize this with memoization, which is really at the core of dynamic programming. Rather than recalculating fib(n) every time we see n, we can calculate the value of fib(n) once and store the value. Then when we see fib(n) again, we can simply look up the value (cheap) rather than go to the trouble of recalculating it (expensive).

Below is a very simple implementation of this in Python:

    numbercounts = dict()
    fibs = {0: 0, 1: 1}
    def fib(n):
        global numbercounts, fibs

        numbercounts[n] = numbercounts.get(n, 0) + 1

        if n in fibs:
            return fibs[n]
        else:
            fibs[n] = fib(n - 1) + fib(n - 2)
            return fibs[n]

Now, if we run fib(20) again and inspect the value of numbercounts, we get the following:

    n: number_times_evaluated

    0: 1
    1: 2
    2: 2
    3: 2
    4: 2
    5: 2
    6: 2
    7: 2
    8: 2
    9: 2
    10: 2
    11: 2
    12: 2
    13: 2
    14: 2
    15: 2
    16: 2
    17: 2
    18: 2
    19: 1
    20: 1

This shows how storing the intermediate values, fib(low_n), we can greatly reduce the number of operations necessary to calculate fib(n).

This is the essence of dynamic programming, storing oft-used, expensive-to-calculate intermediate values in a structure that supports fast lookups.

The Python samples above are the minimum to make the examples work. You may want to look at the Counter datatype[0], and a more general purpose memoizing decorator[1][2]. Of course, if you were going to start using dynamic programming, you may want to utilize functools' lru_cache[3].

I am sure there will be plenty of comments below to help both of us to learn from all of the mistakes I have made above.

[0] https://docs.python.org/3.5/library/collections.html#collect...

[1] https://wiki.python.org/moin/PythonDecorators

[2] https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize

[3] https://docs.python.org/3/library/functools.html#functools.l...

I would have liked examples of pejorative uses of "dynamic" that don't work.

How DARE you tone down my click bait headline. This would have never flown when pg was in charge. He would have just banned me immediately, like God intended.