3 ms·

I think the point of GP is that saying it's basically “smart caching”, or “filling the cache in the correct order” helps connect with a concept many people are

I think the point of GP is that saying it's basically “smart caching”, or “filling the cache in the correct order” helps connect with a concept many people are already very familiar with, which grounds the concept immediately. In contrast, going through each step you have outlined introduces several new concepts that are generally new and counter-intuitive to most people, so many will just give up.

dataflow 3y ago
> In contrast, going through each step you have outlined introduces several new concepts that are generally new and counter-intuitive to most people What's new there? The concept of a DAG? I dare say it's important to learn DAGs before learning DP. Trying to teach them in the opposite order is like trying to teach multiplication before addition. (I also have no idea what you find counter-intuitive here. How is solving complex problems by solving simpler problems counter-intuitive? Do you normally solve hard problems by solving harder problems?!)
- qsantos 3y ago
  Please, take the perspective of an average computer science student, who might have had some interest in computers, but maybe did not look too deep in the theory. In the past few years, they just had to learn graphs, automata and Turing machines, complexity classes, computer architecture, compilation theory, and possibly a programming language they never used before, maybe two. And they might prefer having social life than doing all-nighters on computer-assisted proof assignments :-) . In short, I am not saying you cannot learn dynamic programming straight away from the theory, just that you are going to lose many people with this approach. In fact, it makes me think of “New Math” [1], an effort to teach math from the ground-up starting in junior high. I am not familiar with how it worked in the US, but at least in France, it was definitely not a success. I would definitely have had a lot of fun, but many more did not, and failed to get a basic mathematical education at all as a result. [1] https://en.wikipedia.org/wiki/New_Math https://en.wikipedia.org/wiki/New_Math
  - dataflow 3y ago
    Would you mind pinpointing where exactly you feel I would lose students in the above approach? Would I lose people at the mention of "DAG"? in which case... isn't it easy enough to jog their memory in a few seconds ("it's like a tree, except a node can have multiple parents" <drawing>) if they've forgotten what that is? Or is it with the N-hop example? In which case, aren't there plenty of simpler ones (like Fibonacci) you can use instead? Or do you see somewhere else where people would get overwhelmed, and if so, where? Like, I would understand where you're coming from if I'd used the pumping lemma or something like you're imagining, but that's not what's happening here? All I did was merely mention the words "subproblems", "trees", and "DAGs"... that's it. No theorems, no proofs, not even any need to remember what caching is... just descriptions with vivid examples and diagrams. All of which you can re-explain in a few minutes if they've forgotten them. I have a hard time seeing why that should scare someone away who's otherwise in a position to learn DP. Also, isn't the audience kinda important here? It's not like this was intended for 10-year-olds like New Math. It was intended for college-level CS students and above. They can and should be expected to have a greater understanding (and attention span) than elementary school students.
    - qsantos 3y ago
      The point is that dynamic programming builds on various abstract concepts that many college students only understand to a level deep enough to pass exams. Making the connection with caching, which is a mostly-unrelated, and much more concrete concept, give them the basis to build a mental framework. Sure, they might do without, but why make it harder?
      - dataflow 3y ago
        I don't agree it's making it harder though. Nothing I just built it on above required any deep understanding at all, and you could even re-explain all the shallow bits (like what a DAG is) in a few minutes if not seconds. I simply don't buy that this is too onerous. As to "why explain it this way regardless", because I believe it gives them a better understanding once they hear it?

dataflow 3y ago

> In contrast, going through each step you have outlined introduces several new concepts that are generally new and counter-intuitive to most people What's new there? The concept of a DAG? I dare say it's important to learn DAGs before learning DP. Trying to teach them in the opposite order is like trying to teach multiplication before addition. (I also have no idea what you find counter-intuitive here. How is solving complex problems by solving simpler problems counter-intuitive? Do you normally solve hard problems by solving harder problems?!)

qsantos 3y ago
Please, take the perspective of an average computer science student, who might have had some interest in computers, but maybe did not look too deep in the theory. In the past few years, they just had to learn graphs, automata and Turing machines, complexity classes, computer architecture, compilation theory, and possibly a programming language they never used before, maybe two. And they might prefer having social life than doing all-nighters on computer-assisted proof assignments :-) . In short, I am not saying you cannot learn dynamic programming straight away from the theory, just that you are going to lose many people with this approach. In fact, it makes me think of “New Math” [1], an effort to teach math from the ground-up starting in junior high. I am not familiar with how it worked in the US, but at least in France, it was definitely not a success. I would definitely have had a lot of fun, but many more did not, and failed to get a basic mathematical education at all as a result. [1] https://en.wikipedia.org/wiki/New_Math https://en.wikipedia.org/wiki/New_Math
- dataflow 3y ago
  Would you mind pinpointing where exactly you feel I would lose students in the above approach? Would I lose people at the mention of "DAG"? in which case... isn't it easy enough to jog their memory in a few seconds ("it's like a tree, except a node can have multiple parents" <drawing>) if they've forgotten what that is? Or is it with the N-hop example? In which case, aren't there plenty of simpler ones (like Fibonacci) you can use instead? Or do you see somewhere else where people would get overwhelmed, and if so, where? Like, I would understand where you're coming from if I'd used the pumping lemma or something like you're imagining, but that's not what's happening here? All I did was merely mention the words "subproblems", "trees", and "DAGs"... that's it. No theorems, no proofs, not even any need to remember what caching is... just descriptions with vivid examples and diagrams. All of which you can re-explain in a few minutes if they've forgotten them. I have a hard time seeing why that should scare someone away who's otherwise in a position to learn DP. Also, isn't the audience kinda important here? It's not like this was intended for 10-year-olds like New Math. It was intended for college-level CS students and above. They can and should be expected to have a greater understanding (and attention span) than elementary school students.
  - qsantos 3y ago
    The point is that dynamic programming builds on various abstract concepts that many college students only understand to a level deep enough to pass exams. Making the connection with caching, which is a mostly-unrelated, and much more concrete concept, give them the basis to build a mental framework. Sure, they might do without, but why make it harder?
    - dataflow 3y ago
      I don't agree it's making it harder though. Nothing I just built it on above required any deep understanding at all, and you could even re-explain all the shallow bits (like what a DAG is) in a few minutes if not seconds. I simply don't buy that this is too onerous. As to "why explain it this way regardless", because I believe it gives them a better understanding once they hear it?