I've always hated the term “dynamic programming”. It's big and imposing, making a simple concept sound far more intimidating than it should. And it's completely opaque: if you didn't know the term, would you ever guess that it meant memo functions? (Yes, memoization is the right concept; see the followup.)
I always supposed it was historical, and must have made sense, in some context, at some point. Groping for some way to remember the term, I came up with a fable: if you see the cached results as part of the program, then dynamic programming involves augmenting the program at runtime. So I imagined memoization had initially been seen (or even implemented) as a form of self-modifying code, and that explained the term.
But it turns out it never made even that much sense. Richard Bellman, who coined it, explains:
An interesting question is, ‘Where did the name, dynamic programming, come from?’ The 1950s were not good years for mathematical research. We had a very interesting gentleman in Washington named Wilson. He was Secretary of Defense, and he actually had a pathological fear and hatred of the word, research. I’m not using the term lightly; I’m using it precisely. His face would suffuse, he would turn red, and he would get violent if people used the term, research, in his presence. You can imagine how he felt, then, about the term, mathematical. The RAND Corporation was employed by the Air Force, and the Air Force had Wilson as its boss, essentially. Hence, I felt I had to do something to shield Wilson and the Air Force from the fact that I was really doing mathematics inside the RAND Corporation. What title, what name, could I choose? In the first place I was interested in planning, in decision making, in thinking. But planning, is not a good word for various reasons. I decided therefore to use the word, ‘programming.’ I wanted to get across the idea that this was dynamic, this was multistage, this was time-varying—I thought, let’s kill two birds with one stone. Let’s take a word that has an absolutely precise meaning, namely dynamic, in the classical physical sense. It also has a very interesting property as an adjective, and that is it’s impossible to use the word, dynamic, in a pejorative sense. Try thinking of some combination that will possibly give it a pejorative meaning. It’s impossible. Thus, I thought dynamic programming was a good name. It was something not even a Congressman could object to. So I used it as an umbrella for my activities.
“Dynamic programming” never meant anything; it was nothing but a political euphemism. But somehow it became attached to one of the useful concepts Bellman discovered, and to this day, students of computer science struggle to learn that simple idea, because it's burdened with a nonsense name.
Please call it “memoization” instead. And tell your students.
(Via Wikipedia, of all places. It's not usually a good source for CS information, but it's pretty good about linking to historical sources, or at least, as in this case, to an article quoting one.)
(“Dynamic” does have some negatively connoted uses nowadays, in particular in the static type theory community — partly from the perennial flamewar rivalry with dynamic typing, and partly because the main practical purpose of static analysis is to eliminate dynamic uncertainty, so “dynamic” suggests failure.)
Several people have quoted Russell and Norvig: “This cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.” Perhaps the antipathy to research did not originate with Wilson, or perhaps Bellman initially intended the term to make sense, and only later adopted it as camouflage.
Memoization != dynamic programming
ReplyDeleteI am glad that I saw this post. It is informative blog for us and we need this type of blog thanks for share this blog, Keep posting such instructional blogs and I am looking forward for your future posts. Python Projects for Students Data analytics is the study of dissecting crude data so as to make decisions about that data. Data analytics advances and procedures are generally utilized in business ventures to empower associations to settle on progressively Python Training in Chennai educated business choices. In the present worldwide commercial center, it isn't sufficient to assemble data and do the math; you should realize how to apply that data to genuine situations such that will affect conduct. In the program you will initially gain proficiency with the specialized skills, including R and Python dialects most usually utilized in data analytics programming and usage; Python Training in Chennai at that point center around the commonsense application, in view of genuine business issues in a scope of industry segments, for example, wellbeing, promoting and account. Project Center in Chennai
DeleteTo be more precise, memoization is a part of dynamic programming, but not all of it. Dynamic programming is 1) taking a naive recursive algorithm, 2) memoizing it, 3) building a data structure to hold the memo efficiently (often an array or matrix), and 4) unfolding the recursion to remove the remaining overhead. Memoization is the important step here, of course. Regardless of precise definitions, I agree that the term "dynamic programming" is a poor one -- and now I know why, thanks.
ReplyDeleteWow that makes sense
ReplyDeleteLou
www.anon-vpn.se.tc
Also, 'static analysis' refers to what can be done without running the code with a set of inputs. To make it clearer: in digital circuit design, there's 'static timing analysis', which just traces propagation delays on the graph, picking the maximum; this may be pessimistic versus simulations with realistic inputs.
ReplyDeleteThe 'programming' bit comes from earlier Operations Research terminology, namely Linear Programming: http://en.wikipedia.org/wiki/Linear_programming
In Artificial Intelligence: A Modern Approach, page 685, Russell and Norvig claim:
ReplyDeleteThis cannot be strictly true, because his first paper using the term (Bellman, 1952) appeared before Wilson became Secretary of Defense in 1953.
In my opinion, dynamic programming refers to things such as:
ReplyDelete- dynamically allocating memory
- using dynamic data structures such as double-linked lists which can grow (vs. memory arrays which are fixed in size)
- dynamically creating functions, objects, etc.
Pascal = (mostly) static programming
Python = dynamic programming
Of course the name shouldn't change. The meaning of the phrase has already shifted accordingly.
ReplyDelete- Paddy.
I don't think so. It should be changed to more appropriate phrase. All new students have been confusing, including me myself as a graduate student about 10 years ago.
DeleteGreedy Algorithms + Memoization = Dynamic Programming
ReplyDelete"Dynamic programming" has a wide range of meanings (which I suppose should not be surprising, since the name does nothing to anchor itself to one meaning), and none of them are identical to memoization. But the most interesting of its meanings — storing results of subproblems in a recursive computation — is a simple application of memoization. Isn't it less confusing to describe it that way — in terms of a simple concept with a specific and mnemonic name — than to use a confusing historical name which doesn't even reliably identify the concept?
ReplyDeleteMountains appear small from a distance.
ReplyDeletehttp://en.wikipedia.org/wiki/Dunning_kruger_effect
Dynamic programming is much more than memoization. People please read before you spread misinformation. DP is a algorithm derivation problem solving method.
http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdf
You have written an excellent blog.keep sharing your knowledge.
ReplyDeletePerl Training in Chennai
Selenium with C# Training
Perl Course in Chennai
Selenium with C# Online Training
Awesome blog. Thanks for sharing such a worthy information...
ReplyDeleteRPA Training in Bangalore
RPA Training in Pune
RPA Training in Hyderabad
RPA Training in Gurgaon
RPA Training in Delhi
Very Informative post about programming,Keep sharing such type of post.
ReplyDeleteDevops training in pune
Thank you for the useful blog. It's very interesting. Share more updates.
ReplyDeleteSpoken English Classes In T Nagar
Spoken English Classes In Porur
Good Article , keep writing and sharing such content
ReplyDeleteDevOps Training in Pune
This post is so usefull and informative.keep updating with more information...
ReplyDeleteSoftware Testing Courses in Mumbai
Software Testing Training in Ahmedabad
Software Testing Courses in Kochi
Software Testing Courses in Trivandrum
Software Testing Courses in Kolkata
Wonderful Blog.... Thanks for sharing with us...
ReplyDeleteWhat is Hadoop?
What is Hadoop used for
This post is so interactive and informative.keep updating more information...
ReplyDeleteAWS Cloud Technologies
AWS Application Services
Wonderful Post!!! Thanks for sharing this great blog with us.
ReplyDeleteAndroid Course in Chennai
Android Online Course
Android Course in Coimbatore
This post is so useful and informative. Keep updating with more information.....
ReplyDeleteSoftware Testing Course in Bangalore
Best Software Testing Institute in Bangalore
Great Blog!!! thanks for sharing this wonderful information with us.
ReplyDeleteMachine Learning Course in Chennai
Machine Learning Online Course
Machine Learning institute in Chennai
ReplyDeleteThis article is a creative one and the concept is good to enhance our knowledge.
DevOps Training in Chennai
Devops Online Training
DevOps Training in Bangalore
kawhi leonard shoes
ReplyDeletekobe byrant shoes
kyrie irving shoes
golden goose outlet
curry 8
a bathing ape
bape
off white jordan 1
steph curry shoes
ggdb