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

By Duncan Smith Leave a Comment Sep 14 0

Algorithmic Thinking: A Problem-Based Introduction

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:

  • Should I learn all DS and Algos first to start competitive programming? Or I can just start practicing from CodeChef, learn the DS and Algos with it?

Or to put it another way:

  • What basic data structures and algorithms should one learn before starting competitive programming?

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.

A Project for 2020

By Duncan Smith Leave a Comment Jan 1 0

Ada

People often use the term competitive programming to refer to any activity (besides homework) where programmers create solutions to made-up puzzles rather than real-world problems. For example, consider this Quora question: Which is the best online judge for competitive programming, HackerRank, HackerEarth or LeetCode? As Bohdan Pryshchenko points out in his answer, these three sites focus on interview practice, not competitive programming in the traditional sense. Their questions cover topics likely to come up in an interview. And although some of them host contests, those contests don’t consistently attract the strong contestants who regularly show up for Codeforces and Topcoder events.

When I’m writing Quora answers, I sometimes point out the difference between competitive programming and interview preparation if it’s relevant to the question. But while I’m always in favor of using terms correctly, I’m not sure how important this distinction is in the scheme of things. Consider that:

  • Coding interview questions require knowledge of topics like graphs, trees, and dynamic programming algorithms, all of which are used in competitive programming.

  • Participation in competitive programming tapers off quickly as the problems require more advanced algorithms. For example, see the bottom graph in this Quora answer. Red coders on Topcoder are a long tail at the high end of the rating distribution, while the bulk of the contestants are clustered in the large gray-green-blue area. At these levels, competitive programming questions use well-known algorithms, just like interview questions do.

  • Competitive programming owes most of its popularity to its association with coding interviews. If it was just about coders solving puzzles, it would be a niche activity even within the software engineering world.

« Continue »

Red-Green-Code: 2016 in Review

By Duncan Smith Leave a Comment Dec 28 0

NM Desert

Year two of this blog has come to an end. Let’s review the topics and posts from 2016.

« Continue »

The Purpose of Technical Q&A Sites

By Duncan Smith Leave a Comment Dec 14 0

QandA

With discussions in progress about creating a competitive programming site on Stack Exchange, I have been thinking about what we get out of technical Q&A sites.

« Continue »

Do We Need a Stack Exchange Site for Competitive Programmers?

By Duncan Smith Leave a Comment Dec 7 0

Area51

This week, another attempt is underway to create a competitive programming site on the Stack Exchange network.

It’s been tried before. In early 2013, a similar proposal was put forward. But a year later, the proposal still hadn’t met the minimum activity requirements defined by Area 51, the part of Stack Exchange where new sites are proposed and discussed. In keeping with Area 51 policy against keeping old proposals around, the 2013 proposal was deleted. It lives on as a snapshot at the Internet Archive, and as a Codeforces blog post.

Will things turn out differently this time around? It’s not clear that popular demand for a Competitive Programming Stack Exchange (CP.SE) site has increased in the last few years. And if a new site is going to make it past the Definition phase on Area 51, there will need to be demand. Stack Exchange rules require that a potential new community demonstrate that it can sustain question and answer activity. That’s to prevent underused sites from hanging around the network but not providing any value.

So we’ll see what happens as people start following the CP.SE proposal. In the meantime, it’s worth considering what other sites are out there to fulfill the need for competitive programming Q&A, and whether we need another option. That’s the topic for today.

« Continue »

Review: How to Win Coding Competitions by ITMO University

By Duncan Smith Leave a Comment Nov 30 2

ITMO

Last month, ITMO University launched an edX course called How to Win Coding Competitions: Secrets of Champions. With this first iteration of the course coming to an end, I thought I would discuss my experience with it.

« Continue »

How Many Problems Do You Need to Solve?

By Duncan Smith Leave a Comment Nov 16 0

HowManyProblems

Programmers get better at competitive programming mainly by solving competitive programming problems. It’s true that there are other activities that go along with problem-solving practice. Reading about algorithms, data structures, and problem-solving techniques is useful to avoid re-inventing the wheel. And it’s even more important to read solutions after you solve a problem, so you can learn from other practitioners and fix your mistakes. But the core of the learning process is solving problems. Without that core, reading textbooks and solutions won’t get you very far.

« Continue »

Review: Awesome Competitive Programming by Jasmine Chen

By Duncan Smith Leave a Comment Nov 9 0

Awesome

In January of this year, Jasmine Chen (lnishan) published a Codeforces blog post called An awesome list for competitive programming! Since then, she and a few collaborators have been editing and expanding the list on GitHub.

Awesome list in this context doesn’t just mean “a really great list.” It refers to a project started by Sindre Sorhus in which people create lists of links to useful and/or interesting resources, and publish them on GitHub. There is of course a list of these lists.

Here’s what the Awesome Competitive Programming list offers.

« Continue »

How Long Should You Spend on a Problem?

By Duncan Smith Leave a Comment Nov 2 0

Hourglass

To get better at programming or math, it’s not enough to read about a topic. You have to solve problems. And solving problems is a lot more beneficial if you have access to solutions, especially ones with detailed explanations. But as useful as solutions are, they also present another problem: when is the best time to look at them?

Solving a problem yourself improves your understanding of a concept more than reading someone else’s solution. If that wasn’t true, then it would be possible to learn a technical subject just by reading about it. That would be easier, but it doesn’t work. So you need to struggle with problems.

However, you can’t avoid looking at the solution forever. Problems in textbooks or online judges are intended to be solved in hours or days. They aren’t unsolved research problems that take months or years to solve. (Or if they are, they’re clearly marked as such — e.g., some of the problems in Knuth’s books).

So part of your job as a problem-solver is to settle on the best time to look at each solution.

« Continue »

Why is Competitive Programming Hard?

By Duncan Smith Leave a Comment Oct 26 0

Difficulty

When I came up with 12 Reasons to Study Competitive Programming, I picked the following for reason #3: Studying competitive programming gives you a way to practice solving hard problems.

(As I pointed out in the article, this is also a reason that some people give for not studying competitive programming. They claim that most software developers work only on trivial problems. So they don’t see any reason to practice solving hard problems. That has always seemed to me like a backwards argument).

What does it mean for a problem to be hard? To answer that, I’ll borrow part of the definition of deep work: a problem is hard if it requires specific training and experience to solve. While some ad-hoc competitive programming problems can be solved by any programmer willing to spend an hour or so thinking and coding, modern contests contain problems that only programmers who have spent considerable effort practicing can solve in a reasonable amount of time.

That’s the type of hard problem that I’m talking about. To be hard, a programming problem doesn’t have to involve an unsolved research question. But it does need to provide a challenge to people who spend a lot of time solving puzzles.

What makes competitive programming hard? Here are some factors.

« Continue »

  • 1
  • 2
  • 3
  • …
  • 7
  • Next Page »

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:

  • 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 1288: Remove Covered Intervals January 20, 2021
  • LeetCode 227: Basic Calculator II January 13, 2021
  • A Project for 2021 January 6, 2021
  • Lessons from the 2020 LeetCode Monthly Challenges December 30, 2020
  • Quora: Are Math Courses Useful for Competitive Programming? December 23, 2020
  • Quora: Are Take-Home Assignments a Good Interview Technique? December 17, 2020
  • Quora: Why Don’t Coding Interviews Test Job Skills? December 9, 2020
  • Quora: How Much Time Should it Take to Solve a LeetCode Hard Problem? December 2, 2020
  • Quora: Quantity vs. Quality on LeetCode November 25, 2020
  • Quora: LeetCode Research November 18, 2020
Red-Green-Code
  • Home
  • About
  • Contact
  • Project 462
  • CP FAQ
  • Newsletter
Copyright © 2021 Duncan Smith