tag:blogger.com,1999:blog-6454006.post2549061806767384681..comments2024-01-16T14:32:49.175+00:00Comments on Arcane Sentiment: Why “dynamic programming”?Arcane Sentimenthttp://www.blogger.com/profile/04144052171693893368noreply@blogger.comBlogger11125tag:blogger.com,1999:blog-6454006.post-22677744289590487682016-02-04T04:35:48.059+00:002016-02-04T04:35:48.059+00:00I don't think so. It should be changed to more...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.S.Yunehttps://www.blogger.com/profile/10174459489514154697noreply@blogger.comtag:blogger.com,1999:blog-6454006.post-9250565374239540952010-04-24T19:07:41.008+00:002010-04-24T19:07:41.008+00:00Mountains appear small from a distance.
http://e...Mountains appear small from a distance. <br />http://en.wikipedia.org/wiki/Dunning_kruger_effect<br /><br />Dynamic programming is much more than memoization. People please read before you spread misinformation. DP is a algorithm derivation problem solving method. <br /><br />http://www.aw-bc.com/info/kleinberg/assets/downloads/ch6.pdfAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6454006.post-40108958043082500672010-04-24T18:11:45.467+00:002010-04-24T18:11:45.467+00:00"Dynamic programming" has a wide range o..."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?Arcane Sentimenthttps://www.blogger.com/profile/04144052171693893368noreply@blogger.comtag:blogger.com,1999:blog-6454006.post-90850120875614794172010-04-24T15:41:54.294+00:002010-04-24T15:41:54.294+00:00Greedy Algorithms + Memoization = Dynamic Programm...Greedy Algorithms + Memoization = Dynamic ProgrammingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6454006.post-84875399357458121772010-04-24T15:25:23.484+00:002010-04-24T15:25:23.484+00:00Of course the name shouldn't change. The meani...Of course the name shouldn't change. The meaning of the phrase has already shifted accordingly.<br /><br />- Paddy.Paddy3118https://www.blogger.com/profile/06899509753521482267noreply@blogger.comtag:blogger.com,1999:blog-6454006.post-75125838172260879712010-04-24T13:10:26.834+00:002010-04-24T13:10:26.834+00:00In my opinion, dynamic programming refers to thing...In my opinion, dynamic programming refers to things such as:<br /><br />- dynamically allocating memory<br /><br />- using dynamic data structures such as double-linked lists which can grow (vs. memory arrays which are fixed in size)<br /><br />- dynamically creating functions, objects, etc.<br /><br />Pascal = (mostly) static programming<br /><br />Python = dynamic programmingAnonymousnoreply@blogger.comtag:blogger.com,1999:blog-6454006.post-18320691337048624352010-04-24T11:52:27.588+00:002010-04-24T11:52:27.588+00:00In Artificial Intelligence: A Modern Approach, pag...In <a href="http://aima.cs.berkeley.edu/" rel="nofollow">Artificial Intelligence: A Modern Approach</a>, page 685, Russell and Norvig claim:<br /><br />This cannot be strictly true, because his first paper using the term (<a href="http://www.ams.org/mathscinet-getitem?mr=50856" rel="nofollow">Bellman, 1952</a>) appeared before Wilson became Secretary of Defense in 1953.Carlhttps://www.blogger.com/profile/12472048557599823717noreply@blogger.comtag:blogger.com,1999:blog-6454006.post-31069675548959321332010-04-24T10:35:01.960+00:002010-04-24T10:35:01.960+00:00Also, 'static analysis' refers to what can...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.<br /><br />The 'programming' bit comes from earlier Operations Research terminology, namely Linear Programming: http://en.wikipedia.org/wiki/Linear_programmingA.B.Lealnoreply@blogger.comtag:blogger.com,1999:blog-6454006.post-15883000213209070532010-04-24T10:21:49.839+00:002010-04-24T10:21:49.839+00:00Wow that makes sense
Lou
www.anon-vpn.se.tcWow that makes sense<br />Lou<br />www.anon-vpn.se.tcUltimate Privacyhttps://www.blogger.com/profile/07932164481700812568noreply@blogger.comtag:blogger.com,1999:blog-6454006.post-89350476605348223792010-04-24T08:06:36.964+00:002010-04-24T08:06:36.964+00:00To be more precise, memoization is a part of dynam...To 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.Anonymousnoreply@blogger.comtag:blogger.com,1999:blog-6454006.post-51310947901030656712010-04-24T06:56:26.957+00:002010-04-24T06:56:26.957+00:00Memoization != dynamic programmingMemoization != dynamic programmingAnonymousnoreply@blogger.com