January 4, 2021

A Common-Sense Guide to Data Structures and Algorithms – Part 6

This week we covered chapter 12 of A Common-Sense Guide to Data Structures and Algorithms, 2nd ed. by Jay Wengrow (link). I’ve been coding along in Python on my Github.

Our topic today was dynamic programming.

  • The book gave an example of saving state instead of using recursion to recompute known solutions, stating “avoiding extra recursive calls is key to keeping recursion fast.” Sure, but I’d take a step back and ask whether recursion is really the best tool for the job. I can’t see an advantage of having a recursive function to find the maximum number in a list, when a simple loop will work.
  • I think memoization should have been written memo-ization, given its etymology is based on storing (i.e., making a memo of) already known answers to subproblems.
  • Languages (Python) and tools (PostSharp) have ways to help you cache results so that you don’t have to implement memoization yourself.
  • The example of computing the Fibonacci sequence by passing a hash table as a function argument is an example of when you allocate data structures on the call stack vs. the heap. In this instance, you allocate the hash table on the heap, then pass the pointer to that table around (instead of having the table itself on the call stack).
  • Good advice: “If recursion presents an elegant and intuitive solution to a given problem, you may want to stick with it and use memoization to deal with any overlapping subproblems. However, if the iterative approach is equally intuitive, you may want to go with that.”
  • I get that the author wanted to start with the basics, but he didn’t touch on any real-world examples of where dynamic programming is used (link to Wikipedia section): shortest path between points, word-wrapping, DNA string sequence matching, knapsack packing optimization, scheduling problems.
  • More info about the topic:
    • Dynamic programming involves recursively breaking a larger problem into sub-problems that overlap, so that you can find the optimal solution.
    • There are top-down and bottom-up approaches. It’s definitely beyond the scope of this book, but this Stack Overflow answer goes into more detail.