In September 2020, I published a review of Algorithmic Thinking: A Problem-Based Introduction by Daniel Zingaro. This is an update for the forthcoming second edition of the book.
Solving Problems With Algorithms
Computers are great at evaluating programmers’ algorithmic problem-solving skills. Hence the proliferation of online judges used for screening job candidates, running coding contests, or helping programmers practice their skills. But when we read books about algorithms, we’re often stuck with traditional paper-based exercises. A textbook chapter wraps up, and the author gives us a list of problems to solve. If we’re lucky, there’s an answer key with sample solutions. If not, we’re on our own unless someone has posted the answer online.
In Algorithmic Thinking, Daniel Zingaro doesn’t rely on traditional textbook exercises. Instead, he organizes each chapter around several algorithmic coding problems. And rather than inventing problems for the book, Zingaro uses problems that have appeared in competitive programming contests. This provides two advantages: The competitive programming community has already tested the problems, and you can use online judges to evaluate your solution. In fact, you can use the tried and true three-step process for competitive programming and coding interview training: Write your own solution, read the editorial (the book chapter, in this case), and improve your solution. Repeat as needed until you know the problem well.
I wish every algorithms textbook included a companion online judge that readers could use to check their understanding of each topic. For reasons known only to technical book authors, that practice hasn’t caught on. Fortunately, we have Algorithmic Thinking, which provides the mix of instruction and hands-on coding practice we need to learn to learn fundamental algorithms and data structures.
Second Edition Updates
The second edition of the book has updates throughout the text, plus these two new chapters:
Chapter 4: Advanced memoization and dynamic programming
The new Chapter 4 covers advanced memoization and dynamic programming, expanding on the material in the original memoization and dynamic programming chapter from the first edition. There are new competitive programming problems to illustrate the new advanced material.
Dynamic programming as a mathematical optimization method has been around since the 1950s. In computer programming, authors sometimes position it as an advanced technique. Sedgewick’s Algorithms 4th edition mentions it only briefly, and CLRS gives it a chapter in its Advanced Design and Analysis Techniques section. But in the world of competitive programming and coding interviews, it is entirely mainstream. LeetCode has over 400 dynamic programming problems, which makes that topic the #4 tag on the site.
The “Advanced memoization and dynamic programming” chapter in Algorithmic Thinking explains how to solve a dynamic programming either by working forward from the starting conditions or backward from the ending conditions. It also introduces dimensions higher than two, and situations where adding more subproblems can make a dynamic programming algorithm faster.
Chapter 10: Randomization
The new Chapter 10 covers randomized algorithms, a problem-solving method that you won’t see nearly as often as dynamic programming. Using the pseudo-random number generator that all mainstream programming languages offer, randomized algorithms provide a kind of shortcut to solving certain problems. A randomized approach can enable you to solve problems when a deterministic algorithm would be too slow for a typical online judge time limit. It can also offer a way to implement a less complicated algorithm than the corresponding deterministic algorithm. Although there’s a chance that a randomized algorithm might fail to solve the problem, either by producing an incorrect answer or by running too slowly, there are ways to design your algorithm to reduce the probability of this occurring to an acceptable level.
Although large language models are gaining on us, we human programmers still need to understand how to solve problems using algorithms. Algorithmic Thinking provides the theoretical background and detailed problem explanations required to stay ahead of our human and robotic competitors.