Errata

Algorithms in a Nutshell

Errata for Algorithms in a Nutshell, Second Edition

Submit your own errata for this product.

The errata list is a list of errors and their corrections that were found after the product was released. If the error was corrected in a later version or reprint the date of the correction will be displayed in the column titled "Date Corrected".

The following errata were submitted by our customers and approved as valid errors by the author or editor.

Color key: Serious technical mistake Minor technical mistake Language or formatting error Typo Question Note Update

Version Location Description Submitted By Date submitted Date corrected
Page 115
pseudocode for 'search' function

The Bloom Filter Summary on page 115 uses the wrong Boolean operator in the search() function. The psuedocode shows the following line:

if checkbit | bits = 0 then

This line should instead read:

if checkbit & bits = 0 then

The corresponding Python code shown on page 117 has the correct Boolean operator.

Note from the Author or Editor:
The summary code has the typo, and the actual Python code is correct.

Benjamin Thompson  Sep 10, 2018 
Page 122
Example 5-12

The function "contains" in example 5-12 returns true no matter what.

"True" should be within the while loop as a condition of node == node.value (instead of outside). It should also be uppercase.

The function should explicity return False if it exits the while loop.

Minor typo "ielif" instead of elif in the same section.

Note from the Author or Editor:
The code in the repository is correct, and wasn't printed properly in the book. It should be:

def __contains__(self, target):
"""Check whether BST contains target value."""
node = self.root
while node:
if target < node.value:
node = node.left
elif target > node.value:
node = node.right
else:
return True
return False

Hannah Lazarus  Jul 30, 2017 
Printed
Page 148
Algorithm summary

The summary (pseudo-code) of Dijkstra's algorithm does not keep track of processed/visited nodes.

Note from the Author or Editor:
Here, Dijkstra's algorithm uses a priority queue, PQ, to keep track of all nodes to be processed. Once a node, u, is removed using the getMin(PQ) method, then the shortest distance to the source node, s, is computed in dist[u], and u will not be processed again. There is no need to keep track separately of processed/visited nodes since PQ keep tracks of all the unvisited/yet-to-be-processed nodes.

Anonymous  Jun 26, 2016 
Printed
Page 155
Bellman-Ford Summary

The pseudo-code in the summary does not explain that 'n' actually represents the number of verticies.

Note from the Author or Editor:
Correct. 'n' refers to |V| or the number of vertices in the graph.

Anonymous  Jun 27, 2016 
Page 195
Example 7-6. Depth-First Search implementation

Typos:
OpenStateFactory.STACK and OpenStateFactory.HASH
(should be StateStorageFactory.STACK and StateStorageFactory.HASH respectively)

Note from the Author or Editor:
Correct. The class "OpenStateFactory" appearing on p. 195 is replaced with "StateStorageFactory" in the repository

Serhii Io  Nov 13, 2017 
Page 1899

At location 1899 in the MOBI version of the book, in the Grahamscan implementation, the code computes polar angles using the formula Math.atan2( pts[ n-2]. getY() - lowest, pts[ n-2]. getX() - pts[ n-1]. getX());. However, the variable lowest indexes the pts array. The variable used here should be lowestY or the code should instead use pts[lowest].getY().

Note from the Author or Editor:
Yes, change code so it reads:

double firstAngle = Math.atan2(pts[0].getY() - lowestY, pts[0].getX() - pts[n-1].getX());
double lastAngle = Math.atan2(pts[n-2].getY() - lowestY, pts[n-2].getX() - pts[n-1].getX());

lpowell  Jan 08, 2017