161–163 of 163 posts
Earlier quoted context omitted.
If Python is the king, C is the court jester juggling knives. Done well it looks amazing, elegant, and efficient, but in the wrong hands you'll lose your hands.
There's a great book title that plays off this idea: "Enough Rope to Shoot Yourself in the Foot: Rules for C and C++ Programming" [0] It's also perhaps the best mixed metaphor I've ever encountered. [0]: https://www.amazon.com/Enough-Rope-Shoot-Yourself-Foot/dp/00...
Earlier quoted context omitted.
It's literally the two things which are mentioned on the opening phrase on wikipedia: recursion and caching. Maybe you could explain better...?
The Wikipedia article is incorrect. The caching, or memoization, is a technique heavily utilized in dynamic programming. Page 183 of Algorithms [0] has an explanation of what memoization is and how it is used in dynamic programming. This StackOverflow answer [1] also has a good explanation of the differences between DP and memoization. Any decent algorithms textbook will also have a section dedicated to DP. [0] https…
> Then why did recursion work so well with divide-and-conquer? The key point is that in divide-and-conquer, a problem is expressed in terms of subproblems that are substantially smaller, say half the size. For instance, mergesort sorts an array of size n by recursively sorting two subarrays of size n/2. Because of this sharp drop in problem size, the full recursion tree has only logarithmic depth and a polynomial number of nodes.
> In contrast, in a typical dynamic programming formulation, a problem is reduced to subproblems that are only slightly smaller—for instance, L(j) relies on L(j − 1).
I think I got it. The distinction isn't that clear cut anyway. For example, I could implement a mergesort with caching and say that I'm technically doing dynamic programming, even though the cache would get hit exactly zero times. It would sort of be "trivially" dynamic programming. On the other hand, the first time I calculated fibonacci numbers recursively, I've added a cache. This would be "memoization". Or in other words, wikipedia article is correct, but some problems don't benefit from the caching.
Thanks for the references.
The Coursera Stanford [0] and Princeton [1] courses start again soon, February 20 to be exact. Not sure which one is better, but to refresh my atrophied CS skills of 10 years I've joined the Stanford course. Not sure how it compares to the Khan Algorithms course. Anyone have any feedback? [0] https://www.coursera.org/learn/algorithm-design-analysis/ [1] https://www.coursera.org/learn/algorithms-part1/
This is just my opinion and I'm sure it differs from others... Roughgarden's class is advance and expects mathematical maturity. You may find his course quite fast and rough if you are a beginner. Sedgwick's class is much easier. He is a bit boring and tries to use "real life" examples (in some instances) from the physical sciences to make the material relatable. This in my opinion detracts from the material. Also, h…