3 ms·

The traditional way of teaching dynamic programming worked well in the traditional CS curriculum that had a lot more mathematics than today. It leveraged what t

The traditional way of teaching dynamic programming worked well in the traditional CS curriculum that had a lot more mathematics than today. It leveraged what the students had already learned at that point. Take the definition of the problem. Transform it into an equivalent definition that looks like the inductive step in a proof by induction. Look at the partial order defined by the dependencies between the subproblems in the inductive step. Solve the subproblems in an order that is consistent with the partial order. (For bonus points, find an order that is asymptotically faster in easy situations, such as when the edit distance is small. You may have to rule out paths that cannot be part of an optimal solution.) That's first or second year mathematics in the traditional curriculum. Today, and actually since the 90s or maybe even earlier, many CS students have no particular interest in mathematics. Classes that rely on mathematics have to spend less time on the actual content, as they have to cover the prerequisites and find alternate ways of explaining things.

qsantos 3y ago
I think my own education followed the “traditional” way of learning computer science, albeit after years of tinkering with computers and programming as a kid. But I often felt that some concepts were much simpler when you made the connection with something concrete. Of course, you would not use analogy for formal proofs, but it helped build a mental model incrementally instead of having to conjure various concepts out of thin air and draw connections between them.
- jltsiren 3y ago
  The key part was studying enough mathematics. When your homework involves several proofs by induction every week, you get used to a certain way of thinking. If someone then shows you a dynamic programming algorithm, you will probably notice that the same process you are using all the time can also be used for designing algorithms. You were doing the hard work in the mathematics classes, while dynamic programming was a simple topic you could understand after a single lecture. Definitely simpler than balanced search trees. But once the average CS student was no longer comfortable with mathematical proofs, they had to do the hard work while they were learning dynamic programming.

qsantos 3y ago

I think my own education followed the “traditional” way of learning computer science, albeit after years of tinkering with computers and programming as a kid. But I often felt that some concepts were much simpler when you made the connection with something concrete. Of course, you would not use analogy for formal proofs, but it helped build a mental model incrementally instead of having to conjure various concepts out of thin air and draw connections between them.

jltsiren 3y ago
The key part was studying enough mathematics. When your homework involves several proofs by induction every week, you get used to a certain way of thinking. If someone then shows you a dynamic programming algorithm, you will probably notice that the same process you are using all the time can also be used for designing algorithms. You were doing the hard work in the mathematics classes, while dynamic programming was a simple topic you could understand after a single lecture. Definitely simpler than balanced search trees. But once the average CS student was no longer comfortable with mathematical proofs, they had to do the hard work while they were learning dynamic programming.