[x^2 for x in lst]

Grokking Algorithms

Author: Aditya Y. Bhargava

Review created: 2019-08-09

Grokking Algorithms by Aditya Y. Bhargava is a beginners book on algorithms. It explains in detail, and I really mean in detail, the algorithms it covers.

It is a fantastic book.

The books is aimed at beginners but can be read with pleasure by anyone that is not an absolute algorithms expert. It is richly illustrated and explains the algorithms in a really pedagogical way.

The code examples in the book are written in Python, so a working knowledge of that language is required in order to get the most out of the book. Don't be discouraged if you don't know Python however. The main focus of the book is to explain the algorithms, not implement them. The explanations given in the book are so detailed that you should be able to implement the algorithms in any language of your own choosing.

Having said that, it must be pointed out that the book does not include a lot of code. Implementations are listed for some, but not all of the algorithms covered in the book. E.g the chapter on dynamic programming does not include a full implementation of a solution for the Knapsack problem. It only includes a, really good, explanation of how a solution using dynamic programming works. In my opinion however, this is not a problem. The explanations contained in the book are so detailed and pedagogical that it is extremely easy to translate them into code.

The book starts off in the first chapter with going through what an algorithm is and why algorithms are important. It then introduces the Big O notation for describing the runtime characteristics of an algorithm as its input grows in size. Big O is then used consistently throughout the book in the discussions of the covered algorithms.

The following chapters covers the following algorithms:

  • Linear search
  • Binary search
  • Breadth-first search
  • Selection sort
  • Quick sort
  • Dijkstra
  • Dynamic programming
  • K-nearest neighbours

The books ends with a chapter discussing several interesting algorithms: bloom filters, SHAs, map-reduce and so on. The algorithms are not described in detail, you will only get an overview of them. The chapter is more of a teaser for further studies; it does not include any code at all.

Each chapter includes a number of exercises. The exercises are not only located in the end of each chapter, but also after certain subsections where the author has explained something important. There are answers to all exercises in an appendix to the book.

In the exercises you are not asked to implement something. Instead you are asked to explain something in text or to dry run an algorithm in order to produce a result. This does not mean that all of the exercises are easy, although some are. Sometimes you have to think really hard to be able to give a relevant answer to an exercise.

The following famous problems are discussed in the book:

  • Computing factorials
  • discussing salesman
  • Knapsack problem/li>
  • Set covering
  • Longest common substring
  • Longest common subsequence

...and the data structures covered or at least mentioned in this book are:

  • Array
  • List
  • Stack
  • Queue
  • Hash table
  • Graph
  • Tree
  • Binary search tree

So who should read this book? Of course you have to be interested in algorithms, reading a book about algorithms otherwise is somewhat pointless, but if you are: should you then read this book? Yes, you absolutely should. Unless you fit into one of the following categories:

  1. You are already an expert on the algorithms covered by the book.
  2. You don't want to have a detailed explanation of an algorithm, you only want to see the final listing of the program implementing it.
  3. You don't think you could implement an algorithm in any programming language without seeing a code listing even if you got a really good explanation of how it works.

Most of the programmers/hobbyists that I know, do not fit into one of the categories above. Ergo, they should read the book ;)

I have one thing to complain about though: Why write n^2, 2^n, ... when it is possible to print proper exponents (n2, 2n)? This is a minor pain point, but still irritating.

Summary: Grokking Algorithms is a really, really good introductory book on algorithms. I recommend that you read it if you are at least a little interested in algorithms and can stand that there aren't implementations listed in code for all covered algorithms.