Red-Green-Code

Deliberate practice techniques for software developers

  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter

Book Review – Algorithmic Thinking: A Problem-Based Introduction, Second Edition

By Duncan Smith Mar 9 0

Algorithmic Thinking

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.

Algorithmic Thinking

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.

Categories: Competitive Programming

Prev
Next

Stay in the Know

I'm trying out the latest learning techniques on software development concepts, and writing about what works best. Sound interesting? Subscribe to my free newsletter to keep up to date. Learn More
Unsubscribing is easy, and I'll keep your email address private.

Getting Started

Are you new here? Check out my review posts for a tour of the archives:

  • 2022 in Review: Content Bots
  • 2021 in Review: Thoughts on Solving Programming Puzzles
  • Lessons from the 2020 LeetCode Monthly Challenges
  • 2019 in Review
  • Competitive Programming Frequently Asked Questions: 2018 In Review
  • What I Learned Working On Time Tortoise in 2017
  • 2016 in Review
  • 2015 in Review
  • 2015 Summer Review

Archives

Recent Posts

  • LeetCode Tip 11: How To Use Spaced Repetition (Part 1) March 22, 2023
  • LeetCode Tip 10: Planning a Spaced Repetition Schedule March 15, 2023
  • Book Review – Algorithmic Thinking: A Problem-Based Introduction, Second Edition March 9, 2023
  • LeetCode Tip 9: Spaced Repetition March 8, 2023
  • LeetCode Tip 8: Anatomy of a Model Solution March 1, 2023
  • LeetCode Tip 7: How to Write a Model Solution February 22, 2023
  • LeetCode Tip 6: Model Solutions February 15, 2023
  • LeetCode Tip 5: Choosing a Model Problem February 8, 2023
  • LeetCode Tip 4: Model Problems February 1, 2023
  • LeetCode Tip 3: A Goal for LeetCode Practice January 25, 2023
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2023 Duncan Smith