Errata

This is the errata page for Grokking Algorithms. If you see an error, please send me an email.

Chapter 1

The full code for binary search includes this line:

mid = (low + high)

It should actually be:

mid = (low + high) / 2


For binary search, you have to check log n elements in the worst case. For a list of 8 elements, log 8 == 3, because 2^3 == 8. So for a list of 8 numbers, you would have to check 3 numbers at most.

For 8 numbers we actually need to check 4 numbers in the worst case.


In the rocket example, I say:

Bob runs binary search with 1 billion elements, and it takes 30 ms (log~2~ 1,000,000,000 is roughly 30 because 2^30 = ~1 billion). "32 ms!"

I use 30ms first, and 32ms the second time. It should be 30ms both times.


The running times for O(n!) are wrong:

  • 8.6 x 10^505 should be 2.7 x 10^498
  • 5.4 x 10^2638 should be 1.72 x 10^2631.

Chapter 3

On Page 41, this snippet:

def countdown(i):
print i
countdown(i-1)

Should be formatted as:

def countdown(i):
  print i
  countdown(i-1)

On Page 41, in the countdown function the base case is if i <= 0, but in the illustration below I say if i <= 1. It should be if i <= 1 in both cases.

Chapter 4

On Page 56, I show how the farm can be divided up into 80x80 plots. But the grid I've shown is a 14x8 grid. It should be 21x8.


I talk about partitioning an array in quicksort, with an array of five elements: "Here are all the ways you can partition this array, depending on what pivot you choose." Right after that line, I have a big image showing the various ways the array can be partitioned. The first partition should be: [ ] <1> [ 3, 5, 2, 4 ].


In this chapter at different times I mention:

  • it is better to choose a random element as the pivot
  • it is better to choose the middle element of the array as the pivot.

Obviously they can't both be correct. The O(n lg n) avg case runtime of quicksort only applies if you choose a random element as the pivot. So choose a random element as the pivot.

Chapter 5

On Page 94, I say "once your load factor is greater than .07". That should be "0.7".

Chapter 7

Dijkstra's algorithm, page 132.

The top half of the page sets up the weights such that start -> A is 6 and start -> B is 2. However, the section at the middle of the page shows the weights being swapped:

>>> print graph['start']['a']
2
>>> print graph['start']['b']
6

The values above should be swapped.

Chapter 8

It takes O(2^n) time, because there are 2^n stations.

That should read "2^n subsets", not stations.


On page 149, the arrow for "New syntax! This is called a set intersection." should point to the first line, not the second line.


In the code snippet on the bottom of page 151, the last two lines should be indented so that they are inside the while loop:

while states_needed:
  ....
  states_needed -= states_covered
  final_stations.add(best_station)

Chapter 9

On page 173, the bottom left square of the grid should contain "$2000", not "$3500".


On page 182, the bottom left square in both grids should contain a "1", not a "0", since H == H in both cases.