Historical errata for A Common-Sense Guide to Data Structures and Algorithms, Second Edition

print x[0] y [1] z[2] ==> print array[0] + array[1] + array[2]

This is actually in the preface. Preface • xii
This sentence doesn’t flow right with me. It’s a good sentence but you’re ending a powerful paragraph with that you could make use of today.
“I specifically go out of my way to make these concepts real and practical with ideas that you could make use of today.”
Idk maybe remove ‘that’ or rephrase with ideas that will help you today.

The function on the bottom of PDF page 148 is not supposed to be recursive yet. That will be shown on page 149/150

Remove the following line from the code:
find_directories(“#{directory}/#{filename}”)

In question 3 on this page, “square” is spelled “sqaure” in the following sentence:

“On the third sqaure, you put 4 grains.”

The JavaScript implementation of `Selection Sort` initializes a variable named `lowestNumberIndex` but references an undeclared `smallestNumberIndex` instead on Line 5.

In the last sentence of the first paragraph, “exception” is spelled “execption”.

Another instance of ‘sqaure’ instead of ‘square’:

The next row has N - 1 squares shaded, gray, and the one after than has N - 2 gray sqaures.

I’m not sure how the number of steps of Scenario #1 in the following sentence comes out to be N / 2 ^ 2. It looks like it’s a simple N ^ 2:

“In Scenario #1, our code takes 25 (5 * 5) steps. This is equivalent to N / 2 ^ 2
steps, which is considered O (N 2 ).”

In the first paragraph:

1. “indentify” looks like it should be “identify”
2. “effiency” looks like it should be “efficiency”

In the first paragraph of Queue Implementation, “implemented” appears once as “implemeneted”.

In solution #3, “the” appears twice: “…after having dequeued the the 1 and the 2.”

“The” is duplicated in the following sentence: “While
we previously demonstrated the the bottom-up approach using a classic loop…”

“Subproblem” is spelled as “subprolem” once.

In the function for Chapter 4’s Exercise #4, the first line of the function body, greatestNumberSoFar = array[0], is redundant.

There’s an off-by-1 error in this top-down recursive method for computing factorials:

def factorial(n, i=1, product=1)
return product if i == n
return factorial(n, i + 1, product * i)
end

This gives:

factorial(1) 1 factorial(2) 1
factorial(3) 2 factorial(4) 6
factorial(5) == 24

The method should instead be:

def factorial(n, i=1, product=1)
return product if i > n
return factorial(n, i + 1, product * i)
end

In exercise #1, the ‘select_less_than_100(array[1, array.length - 1])’ function call, though executed twice, doesn’t actually cause any inefficiency, since the 2 calls happen in the 2 branches of an if-else statement i.e. only 1 of those calls will ever be executed each time the ‘select_less_than_100’ method is invoked.

So the method is O (N) whether or not we make the refactoring.

There’s no technical error with this exercise, although it’s probably not the most suitable example for what the exercise is trying to illustrate.

Need a preface that states clearly that binary search idea is represented by the code on page 26, but a real binary search algorithm is more complex — it needs to handle returning the first location of a series of identical values, for example. Practical Programming third edition (also from Pragmatic Bookshelf) notes:
“There are a lot of tests because the algorithm is quite complicated and we wanted to test pretty thoroughly. Our tests cover these cases:
• The value is the first item.
• The value occurs twice. We want the index of the first one.
• The value is in the middle of the list.
• The value is the last item.
• The value is smaller than everything in the list.
• The value is larger than everything in the list.
• The value isn’t in the list, but it is larger than some and smaller than others. • The list has no items.
• The list has one item.” Their code foillows (from page 245)
def binary_search(L, v):
# Mark the left and right indices of the unknown section.
i=0
j = len(L) - 1
while i != j + 1:
m = (i + j) // 2
if L[m] < v:
i=m+1
else:
j=m-1
if 0 <= i < len(L) and L[i] == v:
return i
else:
return –1

I’d suggest tossing in the real code in something like an appendix; the author nicely illustrates the central idea, but the actual code has a number of subtle but highly important points.

In the example implementation for Exercise #2, the method should be

def find_missing_number(array)
(0..array.length).each do |n|
return n if !array.include?(n)
end
end

rather than

def find_missing_number(array)
(0..array.length - 1).each do |n|
return n if !array.include?(n)
end
end

Chapter 7, Exercise #2

“…It merges two sorted arrays together to create a new sorted array containing all the values from both arrays:”

The Ruby implementation of the merge function does not fulfill the stated purpose. Because of the while loop condition, this function could return before all of the elements have been merged into the new array. This could happen if the arrays differ in length or if one of them has a majority of lesser values than the other. Either case will cause the loop to end before all values have been merged into the new array. Consequently it leads to conflicting Big-O notation than what is actually provided in the answers.

The answers section however says that this is basically a O (N + M) situation. I have not found this to be the case for a few different situations.

The link in the “Online Resources” section is to the first edition (pragprog.com/book/jwdsal/a-common-sense-guide-to-data-structures-and-algorithms) rather than the second edition (pragprog.com/titles/jwdsal2)

In the Kindle version of the book, the Exercise solutions are organized in a numerical nested way (1-1, 1-2, etc), but the exercises themselves are organized in a number and letter manner: (1-A, 1-B, etc) which makes it hard to reason about. I noticed that the PDF version of the book has a consistent number and letter organization, so it’s only the Kindle version that has the issue.

The Exercise Solution for Chapter 11, exercise 4 states:

"
Since we need to return the index at which we find the “x”, we can use the trick of passing the index as an extra parameter:

def index_of_x(string, i=0)
return i if string[i] == “x” return index_of_x(string, i + 1)
end
"

Following the “Thinking process” outlined in this chapter, the solution I came to…or that came to me… was:

"
def i_of_x str
return str[0] == ‘x’ ? 0 : i_of_x(str[1, str.length]) + 1
end
"
We don’t actually need an index tracker as this solution adds to the index with each recursive call. Perhaps it would be helpful to use or include this alternative?

In response to issue #86159 + Jay’s response:

"In the function for Chapter 4’s Exercise #4, the first line of the function body, greatestNumberSoFar = array[0], is redundant.—Kelvin Wong

Jay Wengrow says: Thanks, Kelvin - can you please explain why it’s redundant? The code throws an error if we remove that line."

The variable ‘greatestNumberSoFar’ isn’t referenced anywhere else in the remainder of the function’s body, and the function seems to behave as expected for simple test cases without that line:

def greatestNumber(array):

1. remainder of the function’s body

for i in array:

isIValTheGreatest = True

for j in array:

if j > i:

isIValTheGreatest = False

if isIValTheGreatest:

return i

“If recursion presents an elegant and understable…”

“Understable” should be “understandable”?

Chapter 15, missing “we” (“Now when we make these recursive calls…”):

“Now, when make these recursive calls on the current node’s children, note that we didn’t check whether the current node even has any children. That’s where the first base case comes in:”

Should this be step as well ?
On page 74: “Setup: we temporarily remove the 2, and keep it inside a variable called temp_value.” On this page it is stated as “setup” does it means it is step automatically ? And on page 79. there is a sentence which says: “There are four types of steps that occur in Insertion Sort: removals, comparisons, shifts, and insertions” so I made a conclusion that “setup” is step as well which make sense but somehow it confuses me because I was expecting it to be like step#1 on page 74.

Thank you.

Predrag Karic

In the Fibonacci Sequence Code, I believe in the base case it has to be “return 1” instead of “return n”, since it’d be wrong to return 0 if n is 0 (I think)

Okay nevermind my previous comment, returning 0 for n when n is 0 is correct, but since I’m a beginner I was a little bit confused by the line “This indicates that the result of fib(2) is the number 2.”. But when I ran the code in your book, fib(2) gave me 1 until I changed the base case to returning 1 when n is 0.

The first sentence describes the code block as Ruby when it is actually Python.

At Exercise 4 when you presented the code for the preorder traversal I think you copied the code for the inorder traversal and forgot to put the print statement above the first recursive call.

This is one I’m not a 100% sure about, but shouldn’t logn of 3 be between 1 and 2 and not 3? :0 (basically the same as the row count)

It’d be awesome to have just a few sentences about a scenario in which we would use preorder and postorder traversal in the exercises of chapter 15, since you also presented one for inorder traversal (printing out book titles in alphabetical order)

In the bottom section “Implementing Heap Deletion” you wrote:

“we’ve created two helper methods, has_left_child and calculate_larger_child_index”

but in the code you called the method “has_greater_child” instead of “has_left_child”

I’m sorry it seems I incidentally put the wrong page number for my last errata comment:

“This is one I’m not a 100% sure about, but shouldn’t logn of 3 be between 1 and 2 and not 3? :0 (basically the same as the row count)” - Page 243

It could very well be that I simply misunderstood something, but I’m a little confused by the diagram and more precisely by the first “l” (lower case L) node. Why does it display {“*”, “t”}? From my understanding I thought it’d have to be {a, “d”: Trienode, “l”: Trienode, “t”: Trienode}, or simply blank like the boxes above.

The formatting is a little off on the left side of the tree in the first exercise and the “k” node for the tank is not displayed.

You accidentally wrote “b” in the solution Trie instead of “h”

I’m not sure if this is indeed a technical error, maybe I’m simply not familiar enough with Ruby or just didn’t get the code itself fully, but two questions emerged regarding the dfs function:

- Are we trying to get the vertex value or the vertex itself? Because I think the code says the vertex value but I thought we’re trying to get the vertex itself
- What if the very first vertex we’re passing to the function actually already contains the search value? Do we account for that? :0

Again, I might just have misunderstood the code or the concept but still wanted to share my thoughts

ABCDE should be VWXYZ

At Point 3 there is a missing closing brace and at Point 3.b the word “the” is doubled

You put the same code twice for the exercise solution in chapter 18 four and five

Appendix 1: Exercise Solutions; Chapter 17; Question 2

The text of the answer to question 2 states:
> Here is a trie that stores the words “get”, “go”, “got”, “gotten”, “hall”, “ham”, “hammer”, “hill”, and “zebra”

The displayed trie does not have the letter ‘h’ but instead has ‘b’, changing the contained words to “ball”, “bam”, “bammer”, and “bill”.

On the trie diagram a change of the letter ‘b’ in the first nodes children to ‘h’ is required to correct the error.

In the first paragraph of page 400 you wrote: “If the next_player loses in both scenarios, that means that the current_player will win.”

I hope I’m not embarrassing myself here, but doesn’t || operator mean “or”? :0 So shouldn’t the sentence be: “If the next_player loses in one of those scenarios, that means that the current_player will win.”

Chapter 20. Techniques for Code Optimization, Recognizing Patterns, page 403, image of 3 different before/after swap examples.

In the third example the before swap array_1 is [10, 15, 20], and array_2 is [5, 30]. After swap shows that ‘10’ from array_1 has been swapped with ‘15’ from array_2. The error is that ‘15’ was not in array_2 but there is ‘5’.

The correction is to replace the swapped ‘15’ with ‘5’ in the after swap section.

Chapter 20, Exercises, page 428, question 2.

The first example given has the following text: “For example, this array has all the integers from 0 to 5, but is missing the 4:”

The displayed array has the integers from 0 to 6 (excluding 4) but the text states that it is 0 to 5. The correction is to replace 5 with 6, or remove 6 from the displayed array image.

In the comments of the anagram code you call the firstString “firstArray” although you never converted it to a list

Excellent book.wondering if there is any plan of adding section on backtracking and but manipulation?

Not sure, but can’t we technically get an IndexError/Out of bounds error in “def has_greater_child”?

The two solutions to exercise #4 are identical. It seems like two different solutions are supposed to be presented, but the “bottom up” solution is presented twice.

“The second verson…” should be “version”

Right under block of code author writes
In this function, we iterate through each element of the array using var i.
and ‘var’ is in monospaced font as if it was part of the code, but above variable ‘i’ is declared with a keyword ‘let’ not ‘var’. I suggest to either change it to ‘of the array using let i’, where ‘let’ is in monospaced font’ or ‘of the array using variable i’

Author writes
>For example, if the given array is [3, 5, 8], by the time the loop is finished, the existingNumbers array
>will look like this:
>[undefined, undefined, undefined, 1, undefined, 1, undefined, undefined, 1]

but actually array will looks like this:
[ <3 empty items>, 1, <1 empty item>, 1, <2 empty items>, 1 ]
In Javascript arrays are objects with a length property, and when you do
existingNumbers = []
existingNumbers[3] = 1
you actually don’t populate all the slots before 3 with undefined, you just create a new property ‘3’ on an array object.

Sentence says “While hash tables are a perfect fit for paired data, they can also be used to
make your code faster—even if your doesn’t exist as pairs.”, which doesn’t make sense. Maybe it should be “While hash tables are a perfect fit for paired data, they can also be used to
make your code faster—even if your data doesn’t exist as pairs”

This page says that ‘return number * factorial(number - 1)’ is the computation of ‘number’ multiplied by the subproblem of ‘factorial(number - 1)’.

This would make more sense if it said that ‘return number * factorial(number - 1)’ is the computation of ‘number’ multiplied by the subproblem of ‘factorial(number)’, which is equivalent to ‘factorial(number - 1)’, given that right before it says that factorial(5) is the subproblem of factorial(6).

Thanks!

Both bottom-up and top-down solutions for Chapter 11 Problem 4 show code for the bottom-up solution.

In the last comment section of the search function at the bottom of the page - instead of “If the value is less than the current node” (which applies to the elif condition just above), it should read “If the value is greater than the current node”.

2nd full paragraph:

change “throught” to “throughout”

“Connected data that is dispersed throught memory are known as nodes. In a linked list, each node represents one item in the list.”

For exercise 4, the doubleArray3 is supposed to recursively call itself, but a typo makes it so that it calls the doubleArray1 function:

function doubleArray3(array, index=0) {
if (index >= array.length) { return; }
array[index] *= 2;
doubleArray1(array, index + 1); // Should be doubleArray3(array, index + 1);
return array;
}

The second row of cells, where we add [“ace”] => “star” to the hash, it is shown as “stat” in the cell, instead of “star”

Minor typo: first sentence, second paragraph under the ‘Heaps’ section - “The binary heap is a specific kind binary tree” should be “The binary heap is a specific kind of binary tree”

The graph at the bottom of the page has both vertices labelled as ‘Toronto’ - the lower vertex should be labelled ‘Dallas’

Technical error in 2nd paragraph. “Said another way: insertion into the beginning of a set …” should be the end of the set since at that point the text is still discussing the best case scenario for a set.

Spelling: “orignial” in sentence “Let’s ditch our orignial approach and start again from scratch.”

Also, would it be possible to please always keep code examples from splitting across pages? Like widows and orphans, it would be easier to read code if there were never page breaks inside the code blocks.

Spelling: “technially” in sentence “Using iteration (that is, loops) instead of recursion is, technially, a way to achieve this.”