Dynamic Programming: The Name (1984)

http://learning.cis.upenn.edu/cis520_fall2009/index.php?n=Notes.DP

by akanet • 10 years ago

238 61 10 years ago

learning.cis.upenn.edu

taeric• 10 years ago

I was beginning to think it meant that the decision lookups of the algorithm were dynamically generated.

That is hilarious.. I vaguely remember thinking, when I encountered this class of algorithms in college, that it was not particularly well named.

chamakits2• 10 years ago

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.

akanet2• 10 years ago

I am genuinely happy to bring you thus tiny closure, friend

prashnts• 10 years ago

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. :)

DonHopkins4• 10 years ago

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!

zik• 10 years ago

Another example of bureaucratically named concepts is one used heavily in FPGAs - what programmers would call a library or a package in FPGA-land is called an "IP core". I don't know where the naming comes from but it really smacks of some bureaucrat telling his bosses "We create IP! We create IP cores!". I guess to bosses it sounds more valuable and marketable than a library.

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

Cyph0n5• 10 years ago

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.

amelius3• 10 years ago

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.

The same can be said for software.

formula12• 10 years ago

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.

Retra3• 10 years ago

maximizing profits and minimizing expenses

This is always a sub-goal. You should be using the language that supports your actual goal, otherwise you're just end up lost in the weeds optimizing in circles.

cardinalfang• 10 years ago

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.

santaclaus• 10 years ago

Don't even get me started on memoization...

brightball• 10 years ago

I regret that I have but one up vote to give

Cyph0n5• 10 years ago

- "You mean caching?"

- "Nope, memoization."

- "Uh ok."

tdb7893• 10 years ago

I like that it's not called caching because caching for me makes me think that there is some sort of eviction policy. I generally talk about "storing" data in "lookup tables" if I'm talking to someone not familiar with the jargon

wfunction2• 10 years ago

IMO:

caching : memoization :: program performance : algorithm performance

RussellDussel• 10 years ago

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.

Retra3• 10 years ago

I'm not actually sure that's a problem. You just have another way to fizz-buzz lay people.

YeGoblynQueenne• 10 years ago

Also, some spellcheckers will surreptitiously auto-"correct" memoization to "memorization" (as, e.g. Word, and I happen to know it does that because it did it in my Master's dissertation; luckily, just a footnote but probably made me look like an idiot trying to show off with terms I don't understand).

aws_ls2• 10 years ago

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

wfunction2• 10 years ago

The thing is, there is no stipulation that the subproblems be any "smaller" than the original problem. They just need to be instances of the same problem combining together in a manner that solves the original problem.

userbinator• 10 years ago

I wonder how many, who never heard of the original concept, would think it simply means using languages like JavaScript, Python, PHP, etc.

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. :-)

echelon• 10 years ago

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.

TeMPOraL• 10 years ago

Dynamic constant? ;).

DonHopkins4• 10 years ago

I just hate it when variables won't, and constants aren't.

evincarofautumn• 10 years ago

Try thinking of some combination that will possibly give it a pejorative meaning. Its impossible.

“Dynamic typing”, to some! But it was definitely a clever move to use terminology with positive and concrete connotations.

sctb• 10 years ago

We updated the link from https://en.wikipedia.org/wiki/Dynamic_programming#History, and the title from ‘The term “Dynamic Programming” was chosen as a bureaucratic hack’.

akanet2• 10 years ago

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.

Strilanc• 10 years ago

I try to call it inductive programming whenever possible. Because that's what it is: a programmatic form of proof by induction.

The analogy isn't exact (e.g. it could also refer to just recursion), but it's a lot more apt than "dynamic".

StefanKarpinski• 10 years ago

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

aban• 10 years ago

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

eru• 10 years ago

Alas, the weight of history is against reason here.

jordigh• 10 years ago

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.

AstralStorm• 10 years ago

In fact, many linear and quadratic programming problems are solved using dynamic programming. Go figure.

stillworks• 10 years ago

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.

ttflee• 10 years ago

It also has a very interesting property as an adjective, and that is its impossible to use the word, dynamic, in a pejorative sense.

Such a wise consideration!

copperx• 10 years ago

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

QuercusMax• 10 years ago

In a similar category is Shellsort[1]. When I learned about it, they helpfully neglected to mention it was created by some guy named Shell; unlike bubble sort, insertion sort, mergesort, etc., the name has nothing to do with the technique. I spent way too long trying to figure out what it had to do with shells.

1. https://en.wikipedia.org/wiki/Shellsort

pif• 10 years ago

OT:

Its impossible.

Please, please, please: correct that "it's", please!

gbog• 10 years ago

"dynamic" cannot be used in a pejorative way? That's a nice challenge. What about "dynamic" accounting (similar to "creative" accounting)? or "dynamic" application of the Law? Some things (not a lot) should really be static. Not talking about typing...

arithma• 10 years ago

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

Retra3• 10 years ago

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.

DonHopkins4• 10 years ago

The story I heard was that Adobe's Type 1 font encoding [1] used obscure names like BlueValues, OtherBlues, FamilyBlues, FamilyOtherBlues, BlueScale, BlueShift, and BlueFuzz, so that Adobe employees could discuss their proprietary font hinting algorithms in public while they were in line for burritos at La Costeña [2]. That way nobody from Apple or Sun or SGI who was standing in line next to them could understand what they were talking about.

Yes THAT World Famous La Costeña: Guiness Record Holder for the World's Largest Burrito! [3] On May 3rd, 1997 La Costeña of Mountain View, California created the world's largest burrito. The burrito weighed in at 4,456.3 pounds and was measured at 3,578 feet long. It was created at Rengstorff Park in Mountain View.

[1] https://partners.adobe.com/public/developer/en/font/T1_SPEC....

[2] http://www.costena.com

[3] http://www.costena.com/famous.html

wiredfool• 10 years ago

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.

DonHopkins4• 10 years ago

James Gosling published a 1981 SIGPLAN paper titled "A Redisplay Algorithm" [1], that used dynamic programming to solve the string to string correction problem [2], which he implemented in Gosling Emacs [3].

Wikipedia: "Gosling Emacs was especially noteworthy because of the effective redisplay code, which used a dynamic programming technique to solve the classical string-to-string correction problem. The algorithm was quite sophisticated; that section of the source was headed by a skull-and-crossbones in ASCII art [4], warning would-be improver that even if they thought they understood how the display code worked, they probably did not."
Abstract: "This paper presents an algorithm for updating the image displayed on a conventional video terminal. It assumes that the terminal is capable of doing the usual insert/delete line and insert/delete character operations. It takes as input a description of the image currently on the screen and a description of the new image desired and produces a series of operations to do the desired transformation in a near-optimal manner. The algorithm is interesting because it applies results from the theoretical string-to-string correction problem (a generalization of the problem of finding a longest common subsequence), to a problem that is usually approached with crude ad-hoc techniques."

In essence, it finds the shortest path through a twisty little maze of text and terminal escape code sequences (so different terminals would have different optimal routes to updating the display, depending on what was already on the screen, the length of their escape sequences, if they supported features like character/line insert/delete, cleol, extra padding for slow terminals and commands, etc).

[1] http://dl.acm.org/citation.cfm?id=806463

[2] https://en.wikipedia.org/wiki/String-to-string_correction_pr...

[3] https://en.wikipedia.org/wiki/Gosling_Emacs

[4] http://donhopkins.com/home/archive/emacs/skull-and-crossbone...

rfrey• 10 years ago

Dynamic programming is, embarrassingly, one of those topics I've never quite grokked. Any recommendations for a "OH... I get it now" explanation?

friendlygrammar• 10 years ago

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.

greggyb• 10 years ago

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

praptak• 10 years ago

I remember an interview with Alan Kay where he described what are the conditions to enable the kind of innovations he is known for. Quote:

"The shortest lived group at Xerox PARC was `Office of the Future,` because Xerox executives would not leave them alone. I chose the most innocuous name for my own group, the Learning Research Group. Nobody knew what it meant, so they left us alone to invent-object oriented programming and the GUI."

richard_todd• 10 years ago

The part about it being impossible to deride anything labelled 'dynamic' reminded me of the story about naming WordPerfect in the "Almost Perfect" book[1]:

Despite its initial unpopularity, the name proved to be a good one. It was so positive sounding that it made any criticism sound untrue. It was like naming a soap, "Makes You Look Younger," so the competition would have to say something like "Use our soap instead of the Makes You Look Younger soap." "WordPerfect" also sounded like a very good product.

[1] http://www.wordplace.com/ap/ap_chap03.shtml

murbard2• 10 years ago

To add to the confusion, a good way to implement dynamic programming is lazy evaluation.

zde• 10 years ago

its impossible to use the word, dynamic, in a pejorative sense

The Times They Are A-Changin'.. No bullshit bingo is complete without mentioning "dynamic" few times.

Dynamic Programming: The Name (1984)

Related Stories