7 ms·

Possibly the worst named thing in computing? Not only is "programming" not referring to programming, but "dynamic" is meaningless and just there to try to make

Possibly the worst named thing in computing? Not only is "programming" not referring to programming, but "dynamic" is meaningless and just there to try to make it sound fancy. I prefer "cached recursion".

eru 1y ago
Well, cached recursion is a bit too generic. Almost anything can be done with both caches and recursion. We had a different characterisation in one of our mathematical optimisation classes: dynamic programming is basically every problem that isomorphic to finding the longest path in a graph, with suitable 'overloading' of 'maximum' (for picking among multiple alternative paths) and 'addition' (for combining multiple sub-paths). First, to illustrate what I mean by this overloading: matrix multiplication usually has multiplication () and addition (+). However, in the min-plus-algebra you overload (+) with minimum and () with plus, and then multiplying matrices becomes equivalent to hopping two paths in the adjacency matrix of a graph. (Sorry, if this is a bit confusing.) Specifically, taking an adjacency matrix A and calculating A* := 1 + A + AA + AAA + ... is equivalent to taking the transitive closure of edge hopping in your graph, ie the shortest paths between all pairs of vertices. If you overload (+) with maximum and () with plus instead, you can find longest paths. For that to make sense, you should not have cycles in your graph. Now let's go back to dynamic programming: the shared optimal sub-structure property of dynamic programming is exactly the same as what you have in finding longest paths. The structure might sound overly restrictive, but you'll find that it works for all (most?) examples of dynamic programming. P.S. My recollection was a bit vague, so I asked ChatGPT for some help, and apparently I wasn't completely wrong: https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c10b https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c1... P.P.S. Despite everything I said above, I agree that 'cached recursion' is still a better name than dynamic programming.
tgma 1y ago
I actually think overly focusing on the memoized recursion undermines the core conception of dynamic programming. Remember, as noted in the post, the term programming refers to a tabular method of planning, i.e. specifically, the bottom-up calculation to solve a problem. The emphasis here is on a predetermined order on how to tabulate the plan to get to the desired result which will be the solution to the broader problem. The memoized recursive function is an implementation methodology on a digital computer that specifically side-steps the question of in which order one should do the tabulation. I would argue that recursive memoization is a possible solution technique to dynamic programming problems (defined as the universe of problems that admit a dynamic programming solution,) but strictly speaking, in and of itself, is not dynamic programming.
- eru 1y ago
  I'd actually go the other way round: figuring out a suitable recurrence relation is usually the first step in any dynamic programming solution. As a next step, sure, you can explicit construct a table to fill in, but that's not actually a requirement: dynamic programming also works when your parameters aren't things like numbers that you can easily use to enumerate rows in a table. Memoisation is a more general tactic that hands more of the busy work over to the computer.
317070 1y ago
I think "cached recursion" is too broad. I tend to go with "Minimal Memory Memoization". 1) the recursion solution is often too slow, but uses little memory. 2) the memoization solution can make the algorithms from 1 a lot faster, but blows up memory use. 3) the dynamic programming solution only keeps the previous partial solutions in memory that will be needed for future partial solutions. Therefore it is the "Minimal Memory Memoized" solution. It often requires a smart ordering of partial solutions that allows for the earliest cache eviction. Your "cached recursion" sounds like number 2 to me, and the crux about dynamic programming is to figure out when to remove an entry from your cache.
- deleted 1y ago
  [deleted]
- zelphirkalt 1y ago
  Even just keeping the partial solutions in memory that will later be needed can use much more memory than a bottom up solution. Recursion being slow depends on the implementation of your programming language.
  - 317070 1y ago
    > Even just keeping the partial solutions in memory that will later be needed can use much more memory than a bottom up solution. Can you give an example of this? I don't think that is correct. But we might be saying the same thing, because in practice by the time you achieve minimal memory, you will have a bottom-up solution.
    - zelphirkalt 1y ago
      This problem is an example: https://projecteuler.net/problem=18 https://projecteuler.net/problem=18 (assuming you are not brute-forcing it).
      - 317070 1y ago
        At a quick glance, the minimal memory requirement is the O(N) partial solutions you need to keep, with N being the number of rows. Is your comment that this is higher than the memory requirement of the recursive solution, because that doesn't seem correct to me? The recursive solution also has O(N) memory, which is the depth of the tree it is searching.
rochak 1y ago
Yup. I don’t mind it though as this field is riddled with names that convey absolutely nothing about the actual thing.
Certhas 1y ago
Dynamic is definitely not meaningless. I am familiar with dynamic programming from the optimal control theory point of view, and it's squarely focused on dynamical systems. The central equation of dynamic programming is the Hamilton-Jacobi-Bellmann equation, a generalization of the Hamilton-Jacobi equations of classical mechanics. And the terminology programming in this context also exists in linear programming and stochastic programming. It's definitely confusing today, but these terms simply predate the modern use of programming, as well as modern computers. I am honestly a bit puzzled by everyone in this comment section talking about recursion + memoization (as a way to efficiently implement backward induction I presume?). It seems like computer science teaches a particular application and implementation of dynamic programming ideas and people mistake that for the whole thing?
- tgma 1y ago
  Well, to be fair, you are questioning terminology bastardization in "computer science," a field that is named after "computers" and "science" but has little to do with either. One should temper their expectations :) Informatics, a commonly used term in Europe, would have been a much better name.
  - eru 1y ago
    Well, just pretend that the whole discussion happened in German, where despite using your preferred term of Informatik, they still talk about Dynamische Programmierung.
    - zelphirkalt 1y ago
      Some of these terms sound sooo awkward in German. I vote for calling it memoization.
      - deleted 1y ago
        [deleted]
      - eru 1y ago
        Well, memoisation ain't exactly the same as dynamic programming. You can use memoisation to do dynamic programming, but you can also use it in other contexts (and you can implement dynamic programming in different ways, too).
emmelaich 1y ago
It's deliberately obscure. Per the article it's for promotion not description.

eru 1y ago

Well, cached recursion is a bit too generic. Almost anything can be done with both caches and recursion. We had a different characterisation in one of our mathematical optimisation classes: dynamic programming is basically every problem that isomorphic to finding the longest path in a graph, with suitable 'overloading' of 'maximum' (for picking among multiple alternative paths) and 'addition' (for combining multiple sub-paths). First, to illustrate what I mean by this overloading: matrix multiplication usually has multiplication () and addition (+). However, in the min-plus-algebra you overload (+) with minimum and () with plus, and then multiplying matrices becomes equivalent to hopping two paths in the adjacency matrix of a graph. (Sorry, if this is a bit confusing.) Specifically, taking an adjacency matrix A and calculating A* := 1 + A + AA + AAA + ... is equivalent to taking the transitive closure of edge hopping in your graph, ie the shortest paths between all pairs of vertices. If you overload (+) with maximum and () with plus instead, you can find longest paths. For that to make sense, you should not have cycles in your graph. Now let's go back to dynamic programming: the shared optimal sub-structure property of dynamic programming is exactly the same as what you have in finding longest paths. The structure might sound overly restrictive, but you'll find that it works for all (most?) examples of dynamic programming. P.S. My recollection was a bit vague, so I asked ChatGPT for some help, and apparently I wasn't completely wrong: https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c10b https://chatgpt.com/share/687de24c-c674-8009-9984-0fda56d1c1... P.P.S. Despite everything I said above, I agree that 'cached recursion' is still a better name than dynamic programming.

tgma 1y ago

I actually think overly focusing on the memoized recursion undermines the core conception of dynamic programming. Remember, as noted in the post, the term programming refers to a tabular method of planning, i.e. specifically, the bottom-up calculation to solve a problem. The emphasis here is on a predetermined order on how to tabulate the plan to get to the desired result which will be the solution to the broader problem. The memoized recursive function is an implementation methodology on a digital computer that specifically side-steps the question of in which order one should do the tabulation. I would argue that recursive memoization is a possible solution technique to dynamic programming problems (defined as the universe of problems that admit a dynamic programming solution,) but strictly speaking, in and of itself, is not dynamic programming.

eru 1y ago
I'd actually go the other way round: figuring out a suitable recurrence relation is usually the first step in any dynamic programming solution. As a next step, sure, you can explicit construct a table to fill in, but that's not actually a requirement: dynamic programming also works when your parameters aren't things like numbers that you can easily use to enumerate rows in a table. Memoisation is a more general tactic that hands more of the busy work over to the computer.

317070 1y ago

I think "cached recursion" is too broad. I tend to go with "Minimal Memory Memoization". 1) the recursion solution is often too slow, but uses little memory. 2) the memoization solution can make the algorithms from 1 a lot faster, but blows up memory use. 3) the dynamic programming solution only keeps the previous partial solutions in memory that will be needed for future partial solutions. Therefore it is the "Minimal Memory Memoized" solution. It often requires a smart ordering of partial solutions that allows for the earliest cache eviction. Your "cached recursion" sounds like number 2 to me, and the crux about dynamic programming is to figure out when to remove an entry from your cache.

deleted 1y ago
[deleted]
zelphirkalt 1y ago
Even just keeping the partial solutions in memory that will later be needed can use much more memory than a bottom up solution. Recursion being slow depends on the implementation of your programming language.
- 317070 1y ago
  > Even just keeping the partial solutions in memory that will later be needed can use much more memory than a bottom up solution. Can you give an example of this? I don't think that is correct. But we might be saying the same thing, because in practice by the time you achieve minimal memory, you will have a bottom-up solution.
  - zelphirkalt 1y ago
    This problem is an example: https://projecteuler.net/problem=18 https://projecteuler.net/problem=18 (assuming you are not brute-forcing it).
    - 317070 1y ago
      At a quick glance, the minimal memory requirement is the O(N) partial solutions you need to keep, with N being the number of rows. Is your comment that this is higher than the memory requirement of the recursive solution, because that doesn't seem correct to me? The recursive solution also has O(N) memory, which is the depth of the tree it is searching.

rochak 1y ago

Yup. I don’t mind it though as this field is riddled with names that convey absolutely nothing about the actual thing.

Certhas 1y ago

Dynamic is definitely not meaningless. I am familiar with dynamic programming from the optimal control theory point of view, and it's squarely focused on dynamical systems. The central equation of dynamic programming is the Hamilton-Jacobi-Bellmann equation, a generalization of the Hamilton-Jacobi equations of classical mechanics. And the terminology programming in this context also exists in linear programming and stochastic programming. It's definitely confusing today, but these terms simply predate the modern use of programming, as well as modern computers. I am honestly a bit puzzled by everyone in this comment section talking about recursion + memoization (as a way to efficiently implement backward induction I presume?). It seems like computer science teaches a particular application and implementation of dynamic programming ideas and people mistake that for the whole thing?

tgma 1y ago
Well, to be fair, you are questioning terminology bastardization in "computer science," a field that is named after "computers" and "science" but has little to do with either. One should temper their expectations :) Informatics, a commonly used term in Europe, would have been a much better name.
- eru 1y ago
  Well, just pretend that the whole discussion happened in German, where despite using your preferred term of Informatik, they still talk about Dynamische Programmierung.
  - zelphirkalt 1y ago
    Some of these terms sound sooo awkward in German. I vote for calling it memoization.
    - deleted 1y ago
      [deleted]
    - eru 1y ago
      Well, memoisation ain't exactly the same as dynamic programming. You can use memoisation to do dynamic programming, but you can also use it in other contexts (and you can implement dynamic programming in different ways, too).

emmelaich 1y ago

It's deliberately obscure. Per the article it's for promotion not description.