9 ms·

Dynamic Programming: The Name (1984)

238 points by akanet 10y ago

QuercusMax 10y 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 https://en.wikipedia.org/wiki/Shellsort
taeric 10y ago
I was beginning to think it meant that the decision lookups of the algorithm were dynamically generated.
threepipeproblm 10y ago
That is hilarious.. I vaguely remember thinking, when I encountered this class of algorithms in college, that it was not particularly well named.
- chamakits 10y 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.
  - akanet 10y ago
    I am genuinely happy to bring you thus tiny closure, friend
    - chamakits 10y ago
      You really did! I never would have thought to check out the history behind it. Would have remained confused if not for you. Thanks!
- prashnts 10y 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. :)
- DonHopkins 10y 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 10y 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_property_core https://en.wikipedia.org/wiki/Semiconductor_intellectual_pro...
- Cyph0n 10y 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.
  - amelius 10y 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.
    - Cyph0n 10y ago
      And your point is?
      - amelius 10y ago
        That the term "IP core" is not sufficiently narrow.
        Cyph0n 10y ago
        Probably not, but this whole discussion is about a technical term whose origin does not reflect its usage or nature. To me, "IP core" reflects the nature of HDL libraries quite well, and is not at all similar to how the term "dynamic programming" was coined.
santaclaus 10y ago
Don't even get me started on memoization...
- brightball 10y ago
  I regret that I have but one up vote to give
- Cyph0n 10y ago
  - "You mean caching?" - "Nope, memoization." - "Uh ok."
  - tdb7893 10y 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
    - Cyph0n 10y ago
      Good point. Caching does usually refer to a temporary memory store.
  - wfunction 10y ago
    IMO: caching : memoization :: program performance : algorithm performance
- RussellDussel 10y 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.
  - Retra 10y ago
    I'm not actually sure that's a problem. You just have another way to fizz-buzz lay people.
userbinator 10y 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. :-)
- deleted 10y ago
  [deleted]
- echelon 10y 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 10y ago
  Dynamic constant? ;).
  - DonHopkins 10y ago
    I just hate it when variables won't, and constants aren't.
evincarofautumn 10y 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 10y ago
We updated the link from https://en.wikipedia.org/wiki/Dynamic_programming#History https://en.wikipedia.org/wiki/Dynamic_programming#History, and the title from ‘The term “Dynamic Programming” was chosen as a bureaucratic hack’.
- akanet 10y 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 10y 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 10y ago
  That's a much better name – I may start using that. Viva la revolucion!
- aban 10y 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_could_rename_dynamic_programming_to/ https://www.reddit.com/r/compsci/comments/3u3520/if_you_coul...
- eru 10y ago
  Alas, the weight of history is against reason here.
- stillworks 10y 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.
- jordigh 10y 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.
ttflee 10y 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 10y ago
  I would have liked examples of pejorative uses of "dynamic" that don't work.
pif 10y ago
OT: > Its impossible. Please, please, please: correct that "it's", please!
gbog 10y 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 10y 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
- Retra 10y 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.
DonHopkins 10y 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.PDF https://partners.adobe.com/public/developer/en/font/T1_SPEC.... [2] http://www.costena.com http://www.costena.com [3] http://www.costena.com/famous.html http://www.costena.com/famous.html
- wiredfool 10y 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.
DonHopkins 10y 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 http://dl.acm.org/citation.cfm?id=806463 [2] https://en.wikipedia.org/wiki/String-to-string_correction_problem https://en.wikipedia.org/wiki/String-to-string_correction_pr... [3] https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs [4] http://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt http://donhopkins.com/home/archive/emacs/skull-and-crossbone...
rfrey 10y 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 10y 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/#DynamicProgramming 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 10y 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#collections.Counter https://docs.python.org/3.5/library/collections.html#collect... [1] https://wiki.python.org/moin/PythonDecorators https://wiki.python.org/moin/PythonDecorators [2] https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize [3] https://docs.python.org/3/library/functools.html#functools.lru_cache https://docs.python.org/3/library/functools.html#functools.l...
praptak 10y 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 10y 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 http://www.wordplace.com/ap/ap_chap03.shtml
murbard2 10y ago
To add to the confusion, a good way to implement dynamic programming is lazy evaluation.
zde 10y 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.

238 points by akanet 10y 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 https://en.wikipedia.org/wiki/Shellsort

taeric 10y ago

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

threepipeproblm 10y ago

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

chamakits 10y 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.
- akanet 10y ago
  I am genuinely happy to bring you thus tiny closure, friend
  - chamakits 10y ago
    You really did! I never would have thought to check out the history behind it. Would have remained confused if not for you. Thanks!
prashnts 10y 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. :)
DonHopkins 10y 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 10y 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_property_core https://en.wikipedia.org/wiki/Semiconductor_intellectual_pro...

Cyph0n 10y 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.
- amelius 10y 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.
  - Cyph0n 10y ago
    And your point is?
    - amelius 10y ago
      That the term "IP core" is not sufficiently narrow.
      - Cyph0n 10y ago
        Probably not, but this whole discussion is about a technical term whose origin does not reflect its usage or nature. To me, "IP core" reflects the nature of HDL libraries quite well, and is not at all similar to how the term "dynamic programming" was coined.

santaclaus 10y ago

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

brightball 10y ago
I regret that I have but one up vote to give
Cyph0n 10y ago
- "You mean caching?" - "Nope, memoization." - "Uh ok."
- tdb7893 10y 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
  - Cyph0n 10y ago
    Good point. Caching does usually refer to a temporary memory store.
- wfunction 10y ago
  IMO: caching : memoization :: program performance : algorithm performance
RussellDussel 10y 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.
- Retra 10y ago
  I'm not actually sure that's a problem. You just have another way to fizz-buzz lay people.

userbinator 10y 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. :-)

deleted 10y ago
[deleted]
echelon 10y 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 10y ago
Dynamic constant? ;).
- DonHopkins 10y ago
  I just hate it when variables won't, and constants aren't.

evincarofautumn 10y 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 10y ago

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

akanet 10y 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 10y 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 10y ago
That's a much better name – I may start using that. Viva la revolucion!
aban 10y 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_could_rename_dynamic_programming_to/ https://www.reddit.com/r/compsci/comments/3u3520/if_you_coul...
eru 10y ago
Alas, the weight of history is against reason here.
stillworks 10y 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.
jordigh 10y 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.

ttflee 10y 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 10y ago
I would have liked examples of pejorative uses of "dynamic" that don't work.

pif 10y ago

OT: > Its impossible. Please, please, please: correct that "it's", please!

gbog 10y 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 10y 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
Retra 10y 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.

DonHopkins 10y 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.PDF https://partners.adobe.com/public/developer/en/font/T1_SPEC.... [2] http://www.costena.com http://www.costena.com [3] http://www.costena.com/famous.html http://www.costena.com/famous.html

wiredfool 10y 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.

DonHopkins 10y 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 http://dl.acm.org/citation.cfm?id=806463 [2] https://en.wikipedia.org/wiki/String-to-string_correction_problem https://en.wikipedia.org/wiki/String-to-string_correction_pr... [3] https://en.wikipedia.org/wiki/Gosling_Emacs https://en.wikipedia.org/wiki/Gosling_Emacs [4] http://donhopkins.com/home/archive/emacs/skull-and-crossbones.txt http://donhopkins.com/home/archive/emacs/skull-and-crossbone...

rfrey 10y 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 10y 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/#DynamicProgramming 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 10y 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#collections.Counter https://docs.python.org/3.5/library/collections.html#collect... [1] https://wiki.python.org/moin/PythonDecorators https://wiki.python.org/moin/PythonDecorators [2] https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize https://wiki.python.org/moin/PythonDecoratorLibrary#Memoize [3] https://docs.python.org/3/library/functools.html#functools.lru_cache https://docs.python.org/3/library/functools.html#functools.l...

praptak 10y 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 10y 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 http://www.wordplace.com/ap/ap_chap03.shtml

murbard2 10y ago

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

zde 10y 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.