Susan Harkins (230) [Avatar] Offline
#1
Please post errors found in the published version of Grokking Algorithms here. We'll publish a comprehensive list for everyone's convenience. Thank you!

Susan Harkins
Errata Editor
Manning Publications
257075 (2) [Avatar] Offline
#2
The calculation of mid = (low + high)/2 on page 8 is subject to overflow errors if low and high are > than (max value for the numeric type)/2..
The calculation should be low + (high - low)/2. On the page 9, mid is even more wrong since /2 is missing.
224684 (2) [Avatar] Offline
#3
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.
318502 (1) [Avatar] Offline
#4
on page 9, in the full code of the binary_search function, line 6 of the listing is missing the " / 2" to get the middle element, as shown in the example at the bottom of page 8.
i.e it should read "mid = (low + high) / 2", but instead only shows "mid = (low + high)"
225035 (5) [Avatar] Offline
#5
In eBook version, Chapter 1, the binary search code just above the exercises has
mid = (low + high)
which is incorrect. It's missing the division by 2.
303763 (4) [Avatar] Offline
#6
In the epub and pdf versions, the Manning logos are lo-res in the front matter. The rat images in the front matter and chapter openers appear to be lo-res as well. Please check these elements across all platforms before reprint.
420104 (1) [Avatar] Offline
#7
Possible error on pg.147, first paragraph second sentence.

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

I believe that should read "2^n subsets".
Susan Harkins (230) [Avatar] Offline
#8
The current errata list is available at http://adit.io/errata.html. Thanks!

Susan Harkins
Errata Editor
356858 (1) [Avatar] Offline
#9
On the eBook, page 16 second line it says "it will take you 4 operations to draw a grid of 16 boxes (log 16 is 4)." It should be log2 (16) = 4 because log(16) =2.7

UltraBob (1) [Avatar] Offline
#10
Unless I'm misunderstanding, the bottom left box on both grids on page 182 should have a score of 1 in them.
SteveCarpenter (1) [Avatar] Offline
#11
In the Hash Table Recap section on page 94 of the eBook and physical book, I see it recommends resizing the Hash Table when the load factor is .07. This should be .7. Resizing at .07 would be cray.
443341 (1) [Avatar] Offline
#12
58.2 "Remember, recursion keeps track of state."

In my neophyte experience with computer programming, "state" [1] is one of those _big ideas_. The author said here that he spoke about it, but I can't find a specific reference using the term.

There are a few earlier references, but hardly definitive explanation to be "remembering".

44.3 "When you called the `greet2()` function, the `greet` function was `partially completed`. This is the big idea behind this section: _when you call a function from another function, the calling function is paused in a partially complete state_. All the values of the variables for that function are still stored in memory."

49.2 "The 'pile of boxes' is saved on the stack! This is a stack of half-completed function calls, wach with it's own half-complete list of boxes to look through. Using the stack is convenient because you don't have to keep track of a pile of boxes yourself--the stack does it for you.

[1]: https://en.wikipedia.org/wiki/State_(computer_science)
443832 (3) [Avatar] Offline
#13
Chapter 9 page 173 DP matrix error
In Chapter 9, page 173, the matrix at the top of the page, under matrix row #4, column #1 (the bottom left matrix entry) shows "$3500 I", it should show "$2000 I" instead.
443832 (3) [Avatar] Offline
#14
Chapter 3 page 41 diagram inconsistent with code
In chapter 3 page 41, the countdown() function is implemented with base case:
if i <= 0 <----- base case

The diagram in the same page at the bottom of the page shows the base cases instead as:
if i <= 1
we are done
443832 (3) [Avatar] Offline
#15
Chapter 5 page 82 has truncated code
In chapter 5 page 82, the code snippet is truncated by the overlay of the diagram.

The code snippet shows:
print "Kick them ou

instead of:
print "Kick them out"
444046 (1) [Avatar] Offline
#16
Pg 151 -

And you loop until states_needed is empty. Here's the full code for the loop:

while states_needed:
    best_station = None
    states_covered = set()
    ...

states_needed -= states_covered
final_stations.add(best_station)


These final two lines need to be indented such that they are within the while loop, otherwise you don't update your exit condition.
-----------------------
Pg 43

def greet2(name):
    print "how are you, " + name + "?"

    def bye():
        print "ok bye!"


The second function needs to be de-dented to the same level as the first. As shown, the second function is defined within the greet2 function which means you could not call it outside of the greet2 function.
----------------------
Pg 59

In chapter 2 the author consistently delineates between a linked list (AKA 'list' as he later refers to them) and an array. Then in exercises 4.2/4.3 he asks about writing recursive functions for a list, however, his solutions are for arrays. It may be important to explain that in python a 'list' is not a linked list, but an array. The nomenclature here is confusing as I wrote my solutions for a linked list based on his previous terminology.
aditya.bhargava (59) [Avatar] Offline
#17
Thanks everyone! I've added these items to the page at adit.io/errata.html
449728 (1) [Avatar] Offline
#18
the logic in the binary search algorithm is wrong

# this code is wrong 
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
          mid = (low + high)
          guess = list[mid]
          if guess == item:
               return mid
          if guess > item:
                high = mid - 1
          else:
               low = mid + 1
      return None



# this code is right
def binary_search(list, item):
    low = 0
    high = len(list) - 1
    while low <= high:
          mid = (low + high) // 2
          guess = list[mid]
          if guess == item:
               return mid
          if guess > item:
                high = mid - 1
          else:
               low = mid + 1
      return None
55685 (2) [Avatar] Offline
#19
These errors should really be corrected at least immediately in the electronic versions of the book. It's hard to trust a book about algorithms when at the very beginning of the book there is a so obvious error like the one you did about the binary search.
Magnum (6) [Avatar] Offline
#20
Set-covering time table in Greedy Algorithms, page 152
Hello guys,
Thank you to Adita Y. Bhargava and you for this amazing book.

Here, I propose a kind of fix for the Big O time in the Set-Covering table showed in Page 152, for the Greedy Algorithm.
Should say 2^n, not n!

Also, could be nice to mention that the Power Set "formula" 2^n is a given (to be trusted). I assumed the reader had to figure out why it was 2^n but I couldn't, and thus I thought I wasn't understating anything.

https://forums.manning.com/posts/list/35921.page#p113163
Magnum (6) [Avatar] Offline
#21
Chapter 2 & 5 - 2 more Errata
Hi, I add two more, probably, Errata:

1. Axis are Swapped in both graphs from page 74. Should say:
X-Axis: List-Size, Y-Axis: Time
See attached image. I looked at several graphs of O(log n) and O(n) in google images to confirm this.

2. Reasoning behind insertions and deletions being O(1) for Lists .Page 30

Quote from page 30:
It’s worth mentioning that insertions and deletions are O(1) time only if you can instantly access the element to be deleted. It’s a common practice to keep track of the first and last items in a linked list, so it would take only O(1) time to delete those.


When I read this, I get to understand that deletions take O(1) because the Liked-List Data Structure keeps a record of the first and last item of the list...
But that's not really the reason. Keeping track of the first and last item of the list is not the precise point.

The strongest reason it takes O(1) is because EACH AND EVERY "slot" (each element of the list) keeps track of let's say, 2 "pointers", one link that points to the previous element and another link that points towards the next element. Therefore, when deleting (or inserting) an element it is only a matter of changing the pointers in the previous and next elements. As mentioned in page 29.
It doesn't take much more time, because changing pointers/links is quick, as opposed to re-arranging/moving/shifting some or all elements of an Array.