May 12, 2022

Grokking Algorithms review

Grokking Algorithms review
TLDR: If you are new to algorithms and data structures, I highly recommend Grokking Algorithms. This was the first book that I read on the topic, and I still reference it to quickly refresh my understanding of some of the algorithms/data structures.

Link to the book: https://www.manning.com/books/grokking-algorithms

Quick Overview

This is a great intro to algorithms for any developer that has no previous experience with learning algorithms and data structures, but it is also great for those who have read one or two other books on the topic, but who still don't understand some of the concepts.

This book is not about in depth explanations with regards to the topics covered, however it does provide a good foundational understanding for the topics covered that will help you when reading other books on the topic, or when reading other content on the topic.

As mentioned in the tldr, I would highly recommend this book in general, but if you haven't ever done algorithms before, I think this is one of the best starting points.

  1. Chapter 1: Introduction to Algorithms
  2. Chapter 2: Selection sort
  3. Chapter 3: Recursion
  4. Chapter 4: Quicksort
  5. Chapter 5: Hash tables
  6. Chapter 6: Breadth first search
  7. Chapter 7: Dijkstra's algorithm
  8. Chapter 8: Greedy algorithms
  9. Chapter 9: Dynamic programming
  10. Chapter 10: k-nearest neighbors
  11. Chapter 11: Where to go next

Chapter 1: Introduction to Algorithms

This chapter starts off with a quick intro of what is in the book and then jumps into binary search. The author uses a lot of images which complements the text, this combination makes it incredibly easy to understand the binary search algorithm. Another great part of this is the quick note on logarithms, which again, is concise and well explained.

Just after the binary search code has been provided, the author talks about the runtime of simple search compared to binary search. This leads nicely into the next part of the chapter, which is Big O notation.

The section on Big O notation follows the same text with images convention to help convey concepts as quickly and as easily as possible. It provides just enough information about Big O so that the reader has a good enough foundational understanding to carry on with the rest of the book, and understand what makes some algorithms more efficient than others at the same type of task.

Critique

I think binary search and Big O notation should have been two separate chapters, even if that meant they would only be 5-10 page chapters.

Chapter 2: Selection Sort

The first 11 or so pages of the selection sort chapter is focused on a 10000 foot overview of memory, as well introducing the reader to linked lists and arrays.

Nothing too in depth, but it is a great primer for these data structures, and it covers the behaviours of insertion, deletion and reading. At the end of the intro to arrays and linked lists, the author also provides a simple table showing the run times for reading, insertion and deletion for these two data structures.

Even though I have a few years of development experience, this chapter reminded how arrays require contiguous memory. While this is great to have rediscovered, it made me realise how in my day to day work, this type of thing isn't thought about and how it is taken for granted.

The last few pages of the chapter are dedicated to selection sort itself, and the author provides a great explanation of how it works. Once again, the author provides some images that really reinforce what they are saying. At the end of the explanation, run time and a code example is provided.

As an introduction to sorting algorithms, this is my favourite. I cannot emphasise enough how well the author conveys these concepts.

Chapter 3: Recursion

This chapter is my favourite chapter of this entire book, I would go so far as to say I think I would buy the book purely for this chapter. The reason I say that, is because this chapter made me like recursion, I used to hate it, it always seemed quite confusing and weird. Yes, it can still be confusing and weird, but in some cases I find that it can be easier to read.

The recursion part of this chapter is actually quite small, the majority of the chapter revolves around the call stack, which introduces the stack data structure.

The author uses two examples of a stack, the first is a simple stack, the next is showing how a call stack works. After this, the author dives into how the call stack works with recursion, and has a great graphic where they run through each step of a factorial function.

After going through the call stack with recursion, the author goes back to one of the first examples of recursion that they used, and uses that to reinforce how recursion works and shows a small example of the call stack with that.

As I mentioned before, a great chapter, the way the author articulates the ideas of recursion and how they effortlessly work stacks into, it's fantastic.

Chapter 4: Quicksort

This is quite a big chapter, and another favourite. The first half is used to explain the concept of divide and conquer, and provides and example of how to sum an array with recursion.

The quicksort algorithm is explained quite well, however, I do have an issue where the language and the code are different. Not to go into too much detail, but the author talks about the elements to the left of the pivot are smaller(`<`) than the pivot, and even in code, the author uses this as a comment, however, the code uses <= which is very different to <. Just something to note, not a massive deal breaker since the code snippet is what you need to follow, but it is something to keep in mind, because it can trip one up.

One other thing I am not a fan of in this chapter is the use of list comprehension. Every now and then I write a small script using Python, but I strongly dislike list comprehension, I find that it makes things very difficult to read. As this book is for beginners, I think using a regular for loop would have made more sense.

Using list comprehension here also "hides" the partitioning logic. While the author has explained the partitioning logic before, I think it would have made it more clear if this was moved into a separate function.

After all this, the author brings up Big O again and also adds a new graphics that really emphasises how different the Big O run times can be.

This section of Big O goes into much more detail, and compares merge sort to quicksort, as well as the difference between average case and worst case.

While this is not the best written chapter, it is a fantastic chapter and is packed full of information.

Chapter 5: Hash tables

The hash table chapter is an interesting read, I learned a lot when I was going through it the first time, but there is no real code in this chapter. Mainly due to the fact that most languages have some kind of hash table built in. Also, you would never really want to write one yourself(well, maybe as a project it could be fun).

This is a great chapter as it is the first introduction to graph algorithms. Being the first chapter on graph algorithms, the author also explains what a graph is in a simple and concise way.

Once we know what a graph is, the author shows us how breadth first search works, and how we can use it to search for a node in a graph. The explanation is accompanied by a good few images that helps one visualise how BFS works in a friendly and approachable manner.

This chapter also contains a short, but excellent explanation of what a queue is, as well as quickly showing the difference between FIFO and LIFO queues.

Once all the foundational theoretical knowledge has been explained, the author starts with the implementation of the graph, again, with use of images to show how it relates to what was discussed before. There is also a quick mention of directed and undirected graphs at this point.

After implementing the graph, the author starts with the implementation of the algorithm. The author first shows the steps of the algorithm, and then they provide the code implementation.

The author provides a great graphic showing the algorithm in action which really provides some clarity on how it works.

After this, a few issues with the algorithm are brought up, and a final one is presented that deals with the provided issues.

Critique

My main critique with this chapter is with the ordering of the explanation of what a graph is. The author gives and example of a graph by showing a few pictures, but they only tell us what a graph is after they give this example. I think in some situations this makes sense, but I think that these images could have been worked into the explanation of "What is a graph".

Chapter 7: Dijkstra's Algorithm

This chapter, for some reason, required me to let it simmer in my mind for a few months. I read it multiple times but for some reason every time I read it, I couldn't make sense of it. It almost felt like a different person wrote this chapter.

After a few months, I re-read this chapter, and for some reason it now makes a lot more sense and follows similar patterns to the other chapters in this book, and now I think this chapter is mostly well written and clear. The author compares Dijkstra's algorithm with breadth first search, the previous chapter, and provides a few different examples to explain the algorithm, and I think it is done well.

There are one or two annoyance's in this chapter however. Midway through one of the examples of Dijkstra's algorithm, the author introduces a new example and then jumps back to the example they were talking about before. I found this to be confusing and unnecessary.

Chapter 8: Greedy Algorithms

This is one of the two most challenging chapters in this book in my opinion. Greedy algorithms might not be super difficult to understand, but the problems that they can solve can be very difficult to solve if not impossible to solve without greedy algorithms.

The author start's off the chapter with an incredibly simple example of what a greedy algorithm is, by using a school class scheduling problem, which really helps one understand the issue. They slowly work their way into far more complex problems(conceptually, not code wise) and giving good high level explanations of the problems.

This is a chapter that I have read a few times, and I still need to read it is a few more times to start getting a basic grasp of the problems that this chapter talks about. As mentioned before, this is one of the more difficult chapters in this book.

Chapter 9: Dynamic Programming

This is the most challenging chapter of the book, but, it is a fascinating chapter. Definitely a chapter that requires multiple read throughs. This chapter shows how well the author can articulate a complex topic. The first example draws on from your experience from the greedy algorithm chapter so the example is familiar, and while the solution to the example is very different compared to a greedy algorithm, the author makes use of this example so that it "flows" well from one chapter to the next.

The other examples are also well explained and the author goes through each step with detailed and well thought out explanations. I would try and give a high level explanation, but it is out of the scope of this review.

Dynamic programming really gets one thinking a bit differently, and the solutions are often different depending on the problem.

Chapter 10: K-nearest neighbors

Another fantastic chapter on something that seems complex before it is explained. The author breaks the concept down and shows how simple k-nearest neighbors is at a basic level, by giving an example where they compare grape fruit and oranges.

The author then goes into more complex examples and talking about some of the things that you need to look at when implementing KNN.

Great chapter because it introduces a simple machine learning algorithm in a simple way which allows the reader to take it further on their own.

Chapter 11: Where to Go Next

This chapter isn't really about teaching anything, but the author is more pointing the reader to look at other algorithms/data structures that might be more advanced or algorithms/data structures that are very interesting or used often.

Still a good chapter to read, it has some great topics for deeper learning.

Conclusion

One of my favourite books or bits of content that I have ever read. Considering each chapter as a blog article, some of these chapters are some of my favourite content, purely because of how the author explains the topics. The way that they can simply the concept/idea so that the reader can have a solid simplified base that will allow them to build on top of. Amazing book, 9.5/10, highly highly recommended.

Link to the book: https://www.manning.com/books/grokking-algorithms