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.
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.
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.
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.
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.
Providing a service to others? Looking to fill a nitch in society? What is the "actual goal"? A companies/organizations survival and success is based off profits, so that is its actual goal. The government disensentives crime and insentives providing products and services to the world. "Research" can be considered "planning for reality" because thats what it is in the context of a company. Often, you are looking for ways to bring an imaginitive concept to life.
If your working alone on your own personal project, you can call it anything you like. You can use your own language. But when you are providing your services for something bigger than yourself, ensuring people understand what your doing in regards to the companies success/failure is better.
"Dynamic Programming" as a joke can be considered a two way joke. Perhaps the individual doesnt understand why discriptive vocabular (such as latin and programming) is better than just "words". And they chose words to influence and subdue higher ups rather than understanding why the boss has a seemingly irrational distaste for things he doesnt understand.
What we get to enjoy is the common perspective "lol, stupid companies". But somehow these giant organizations provide far more successful than the unorganized peanut gallery.
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.
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".
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.
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."
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. :-)
> 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.
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!
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.
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.
Yes, I can think of a case where how it may be used to solve some problems on a M x N grid, where in you could move in either directions top-left to bottom-right Or vice-versa.
I perhaps used smaller where subproblem may be a more optimal use.
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
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.
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).
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.
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).
"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...
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.
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
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.
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:
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.
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.
https://en.wikipedia.org/wiki/Semiconductor_intellectual_pro...