As any student pursuing a technical degree knows, problem sets are a big part of math, physics, and engineering classes. Computer science works a bit differently. While CS theory classes use problem sets similar to those in math and science, other classes often require CS students to turn in code that compiles and runs. Some of these programs are for major projects related to networking, operating systems, or graphics, while others are solutions to short algorithm problems.
Because of the way coding interviews work, programmers must be able to solve short algorithm problems even after they graduate and enter the workforce. As a result, coding assignments in these areas have escaped the campus and are available to the public on websites like Codeforces and LeetCode. Anyone who wants to learn these topics can submit their programs to an online judge, which runs them against dozens of test cases that verify correctness, performance, and resource usage.
Despite the popularity of interview prep sites, not all algorithms textbooks have bought into the online judge approach. Introduction to Algorithms (CLRS to those in the know) famously uses pseudocode in its examples. Good luck compiling and running those. Robert Sedgewick’s algorithms books offer actual code in multiple programming languages. But the exercises at the end of each chapter are traditional textbook problems, graded manually by the student (if they can find an answer key) or by an instructor. Even Cracking the Coding Interview, the popular prep book by Gayle Laakmann McDowell, is mostly paper-based. The book includes solutions, which you can compare with your own code. But the only way to find out for sure that your solution works is to come up with test data and run your program against it. (A few years ago, CtCI had an arrangement with HackerRank to host questions in an online judge format, but apparently it wasn’t a permanent deal).
Paper and pencil are good for sketching binary trees, working out the details of an asymptotic analysis, or planning a solution approach. But if you want to verify that you can implement an algorithm correctly and efficiently, the gold standard is running it against a suite of test cases that an expert has carefully chosen. That’s the philosophy behind Algorithmic Thinking: A Problem-Based Introduction, a new book by Daniel Zingaro, Associate Professor of Mathematical and Computational Sciences at the University of Toronto Mississauga.
Algorithms for Competitive Programming
Algorithmic Thinking is not a competitive programming manual. In the introduction, Dr. Zingaro writes, “My goal is not to turn you into a competitive programmer, though I’d take that as a happy side benefit.” But all the problems in the book come from online judges and programming competitions, which means they are self-grading.
The book also isn’t an encyclopedia of algorithms, like CLRS or Sedgewick. It doesn’t cover every algorithm you might need in a class or contest. Instead, it explores a selection of classic algorithms, data structures, and techniques to find out what they can teach about solving problems with computers.
Try the Problem First
Here’s a question from Quora:
Or to put it another way:
These are popular questions, maybe because of how technical classes traditionally work: First you attend a lecture to learn some ideas, and then you work on a problem set that uses what you learned in the lecture. Repeat with the next lecture and the next problem set.
Algorithmic Thinking takes the opposite approach: The first thing you encounter in each chapter is a description of the first problem to be solved in that chapter. Algorithms, data structures, and techniques appear only when they’re needed for the problem. For example, Chapter 3 (“If you’re going to read one chapter in this book, read this one”) introduces UVa 10465, the Homer Simpson problem, and uses it to explain memoization and dynamic programming.
Reading Editorials
The best way to read Algorithmic Thinking is to treat it like a problem set that comes packaged with the world’s most detailed answer key. Here’s the plan: Don’t spoil the surprise by reading the answer key first. Instead, before starting the introduction, skip straight to Appendix C, which lists the 25 problems covered in the book’s 359 pages. (That’s over 14 pages per problem. I wasn’t kidding when I said it was detailed). The problems are all available online, so search for the first one (Food Lines from DMOJ) and submit a solution, or spend a reasonable amount of time trying. Once you get everything you can out of the problem, start reading the introduction. If you weren’t able to solve the problem on your own, read just enough to get a hint, which might unblock you. If you did solve the problem on your own, you might still find ideas to make your solution more efficient or elegant.
In competitive programming jargon, an editorial explains how to solve a programming problem. It covers how to approach the problem, which algorithms and data structures to use, and how to write the code to solve it. So you could interpret the chapters in Algorithmic Thinking as editorials for 25 competitive programming problems. But there are a few ways in which this book is preferable to editorials one might find online:
Problem selection: There are thousands of contest problems out there, but only 25 in this book. As Dr. Zingaro explains in Chapter 1, he didn’t select the problems arbitrarily. Each one had to use one of the algorithms or data structures selected for the book, and it had to be “algorithmically complex” enough to be challenging but also “sufficiently simple” to avoid confusing the reader with irrelevant details. That’s the value that an expert provides when selecting the right set of practice problems. And when those problems are collected in a book, they can be ordered so that subsequent problems build on lessons learned from earlier ones.
Level of detail: As I mentioned earlier, the book devotes quite a few pages to each problem. There’s enough space to solve the problem in multiple ways, showing how different data structures affect runtime. The text explains each line of code, so that once you finish reading the explanation, you really know what the problem is about.
Quality control: While you can find an editorial for many contest problems, there’s no guarantee that it will be understandable. In contrast, Algorithmic Thinking offers clear writing and professional editing. Even the problem descriptions have been rewritten to eliminate the notoriously obfuscated prose that competitive programming problems use, so the reader can focus on learning the algorithms.
Topics
Dr. Zingaro chose the 25 problems in Algorithmic Thinking to support the set of algorithms, data structures, and techniques that he thought would best serve the goals of a problem-based introduction to algorithmic thinking. Here are the principal topics in each chapter:
0: Arrays; introduction to the online judge problem format
1: Hash tables
2: Trees and recursion
3: Memoization and dynamic programming
4: Graphs and breadth-first search
5: Shortest paths in weighted graphs
6: Binary search
7: Heaps and segment trees
8: Union-find
Other algorithms, data structures, and techniques also appear when needed. For example, a stack (implemented from scratch) shows up in Chapter 2, and greedy algorithms are used in Chapters 3, 5 (Dijkstra’s algorithm), and 6. But the goal is not comprehensive coverage. There are a lot of algorithm books out there. As explained in the introduction, each topic made it into the book because it was broadly applicable, could be implemented in at most 150 lines of C code, and because a concise argument could be made about correctness without getting into a formal proof. That’s the niche occupied by this book.
The C Programming Language
150 lines of what kind of code? Yes, the only programming language you’ll find in Algorithmic Thinking is the C programming language. Not C++, just C. It’s been a while since I have done any C programming, but according to one measurement, it’s the #1 most popular language as of September 2020, so there you go. (Stack Overflow puts it at number 11. It all depends how you measure).
The choice of C is intentional. Dr. Zingaro says in the Introduction that he wants “to teach you data structures and algorithms from the ground up. When we want a hash table, we’ll build it ourselves.” I understand this decision. Algorithms are a fundamental topic in programming. They’re at a lower level than topics like databases or networking. So building your own data structures and handling your own memory management isn’t out of place in a discussion of algorithms. (And it’s not like we’re being asked to go full Knuth and write all the algorithms in assembly language for a theoretical CPU). The book isn’t even excessively dogmatic about building every tool: A few solutions use the built-in C qsort function rather than implementing a custom sort algorithm from scratch.
In my work, I spend most of my time with languages at a Java level of abstraction. When I’m solving competitive programming problems, I like to have a wide range of built-in collection classes and other facilities available. But I didn’t have any problem following the C code in the book or the explanations. For example, it was interesting to review how hash functions work (Chapter 1) even though I usually rely on library functions to implement them.
Food for Thought
“While there may be millions of problems out there, there are far fewer algorithms. The best algorithms are often the ones that rest on ideas so flexible that they can ooze beyond their intended purpose” (Chapter 5). Programming contests are all about starting with a limited set of standard algorithms and inventing wacky scenarios to see if contestants can tweak the algorithms they’re familiar with to solve each problem in the allotted time.
“Hold on! Why are we letting these officious test cases bully us into producing these awful trees?” (Chapter 8). It’s true. If you aren’t careful, test data can mean the difference between Accepted and TLE in a contest.
“Binary search turns a ‘solve this’ problem into a ‘check this’ problem” (Afterword). I’ll bet you didn’t know that about binary search.
Should You Read It?
If you need to solve coding interview questions on demand (and who doesn’t), you might have to practice with a few hundred problems. If you’re serious about competitive programming, the target is more like a few thousand. Either way, adding the 25 problems from Algorithmic Thinking into the mix should fit into any practice schedule. In return, you get a handpicked set of problems covering fundamental topics. Each solution is explained in considerable detail and has a model implementation that you can translate into your favorite programming language. And if you spend time with a problem before reading about it in the book, the explanation is easy to follow. It’s a good choice for anyone who needs to understand and implement algorithms.