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

The text states ‘O (N^2) is considered to be a relatively inefficient algorithm, since as the data increases, the steps increase exponentially.’

Actually this is a polynomial increase. An exponential increase would follow 2 ^ N.
Note the significant difference between N^2 and 2^N.

In the 2nd paragraph of A Third Kind of Algorithm, last sentence starts with “So binary serach seems…”. Should be “search”.

Because there will always be some amount of data in which the tides turn,
and O (N) takes more steps from that point until infinity, O (N) is considered
to be, on the whole, less efficient than O (N).

Shouldn’t this read:
… O (N) is considered to be, on the whole, less efficient than O (1).

Third paragraph, second sentence: “For example, the process for preparing a bowl of cereal is can be called an algorithm.”
Shouldn’t this be something like:
“For example, the process for preparing a bowl of cereal can be called an algorithm.”
or
“For example, the process for preparing a bowl of cereal is called an algorithm.”
or
“For example, the process for preparing a bowl of cereal is an algorithm.”

Second paragraph, second sentence: “This is becaus the number of steps that an algorithm takes cannot be pinned down to a single number.”

The word “becaus” is misspelled. The sentence should read:

“This is because the number of steps that an algorithm takes cannot be pinned down to a single number.”

The last sentence of the page is “The following graph bears this out:”

What “follows” is a table, not a graph.

Second sentence from top of the page:

“ACE hashes into 15, since ACE = 1 * 3 * 5, so ”star" gets placed into 15:"

The illustration of the cells below this sentence shows cell 15 contains the word “stat”, it should contain the word “star.”

The illustration of the cells near the top of the page shows cell 15 contains the word “stat”, it should contain the word “star.”

The last line:

“becuase it can’t handle the load.”

“In this chapter, we’ll analyze how fast each of these operations when applied
to an array.”

“are” should be placed after “operations”

“For example, the process for preparing a bowl of cereal is can be called an algorithm.”

“is” needs to be removed.

“O (1) is the way to describe
any algorithm is that doesn’t change its number of steps even when the data
increases”

“is” needs to be removed after algorithm.

The sentence right above step 7:

“We compare the left pointer(2) to our pivot. Is the value the value less than the pivot? It is, so the left pointer moves on.”

Should be:

“We compare the left pointer(2) to our pivot. Is the value less than the pivot? It is, so the left pointer moves on.”

In the section about “Insertion Sort in Action”, some of the images are wrong.

- In Passthrough #1, Step #3 there is 4823, instead of 24713.

- In Passthrough #3, Step #12 there is 24713, instead of 12473.

- In Passthrough #4, Step #18 there is 12473, instead of 12347.

First paragraph, last sentence:

“The final node’s link is contains null since the linked list ends there.”

Should be:

“The final node’s link contains null since the linked list ends there.”

Second paragraph under Reading:

“After all, the each node of a linked list can be anywhere in memory!”

Should be:

“After all, each node of a linked list can be anywhere in memory!”

3rd paragraph:

“There are a number of ways that a graph can be implemented, but one of the simplest ways is using a hash table (see <titleref linkend=”chp.hashes“).”

Instead of “see <titleref linkend=”chp.hashes", I think you want a link title displayed.

2nd paragraph:

“This is because the database maintains the rows in order their ids, and the database can then use binary search to find each row.”

Shouldn’t this be:

“This is because the database maintains the rows in order of their ids, and the database can then use a binary search to find each row.”

“And indeed - between if given the choice between those two options, Selection Sort is the better choice.”

should read

“And indeed - if given the choice between those two options, Selection Sort is the better choice.”

“When examining at this pattern, ….”

should read

“When examining this pattern, …”

Chapter 6 - Page 71 (PDF)

Image after “Step #3.”

Should be [2 4 7 1 3]
Actual [4 8 2 3]

Image after “Step #12”

Should be [1 2 4 7 3]
Actual [2 4 7 1 3]

Step 18’s diagram doesn’t show the ‘3’ being inserted in the gap.

Chapter 6
The image in step 3 is from an example mentioned earlier in the same chapter. Also, there is a mistake in step 12’s image regarding the result.

Step 3 image:
Correction [2 4 7 1 3]
Mistake in the book [4 8 2 3]

Step 12 image:
Correction [1 2 4 7 3]
Mistake in the book [2 4 7 1 3]

These mistakes totally break the flow, and I noticed that this mistake hasn’t been fixed sine B4 of the book as it was reported by another reader.

Step #8: We being by comparing
=>
We begin by comparing

In addition to the errors already reported by another reader at step #3 and step #12,
at “Insertion Sort in Action” step #18:
Correction [1 2 3 4 7] and the arrow should point at the “3” in the middle of the sequence.
Mistake in book [1 2 4 7 3] and the arrow is pointing at “1”.

In SortableArray#partition!

while @array[right_pointer] > pivot do right_pointer -= 1 end

The right pointer could go negative, it still works in Ruby, but could be improved.

LinkedList#insert_at_index

Insert at index 0 does not seem to work.

Super minor, it looks like the arrays examples were swapped between topics.
On page 65, Insertion Sort in Action, the example array corresponds to the previous example ‘Insertion Sort’

Great book! Thanks!

This is more a question, shouldn’t this line of code “for index in range(1, len(array)):”be len(array) –1 instead?. When it reaches to the last index temp_value = array[index] will be nil and it will blowup in the comparison.

Should we post in the forum questions like this? or is it okay for me to send it through this form?

Thanks!

(Towards the middle of the page)
“So, when our algorithm begins, our queue look like this:”
should be
“So, when our algorithm begins, our queue looks like this:”

(Bottom of the page)
“… since we create a new node and modify the links of the blue and green nodes …”
The link of the green node is not modified. Perhaps you meant the purple (new)
node’s link?

(towards the bottom of the page)
delete_at_index(0) does not seem to work either, even though this case is correctly
described in the text on page 140:
“… we change the first_node of the linked list to now point to the second node.”
i.e., first_node = first_node.next_node

The page has wrong picture at `Step 3`

Step 12 has wrong picture

Step 18 has wrong picture

Print version of book. I’m not sure of the exact version. Bought from Amazon on the 8th September 2018.

Contains numerous characters in the diagrams that are printed as little boxes, where they should be number and letters. Most prominent in the first 2 chapters, and at the end the discount code is also printed a just empty boxes.

I took some pictures - 10, 23, 25 but they mostly don’t include the page number.

Would you please send me a PDF version? I’m sending it back but I’d expect this to be a flaw in the print run and not a one off, so it doesn’t make sense to ask for a replacement print copy.

andrew.lowcock@gmail.com

I can send you the images if you like.

Many thanks
Andrew

“Let’s see how this plays out for even larger arrays. With an array of 10,000
elements, a linear search can take up to 10,000 steps, while binary search
takes up to a maximum of just thirteen steps.”

Shouldn’t that be fourteen steps?

2 to the power of 13 is just 8192 and that is less than 10_000.

Throughout the entire book the diagrams are misprinted, many of the images/characters in the diagrams are displayed as boxes. Correctly printed diagrams are very rare.

A real shame, because apart from this I love this book! Unfortunately this renders the book rather useless….

Text says “There right pointer is pointing to the 6 as well, so would theoretically move on to the next cell on the left. However, there are no more cells to the left of the 6, so the right pointer stops moving.”

I don’t think the pointer stops moving? Nothing in the def partition implementation on page 117 says the right pointer will stop moving and the code there does not check index out of bounds of the array. The whole code was indexing into the same original array, so there are indeed cells to the left of 6, contrary to what the text says. The right pointer should move left 1 more time to point at 3 in the sequence of 012365 and stop because 3 < pivot of 5.

In the “what’s in this book?” Section there is this phrase:

“We unveil Big O Notation and explain it in terms that my grandmother could understand”

I’d suggest to refrain to using this analogy. Even if his grandmother might have a hard time understanding Big O there are very smart grandmothers out there. It’d be great if we could change our view in this industry and be more supportive of women and seniority.

Thanks, love your books!

Quick sort code enters an infinite loop with input [8, 8, 8, 8, 8, 8, 2]

Missing the word “search” from the second-half of the following sentence:
“While ordered arrays have O (log N) search and O (N) insertion, binary trees have O (log N) and O (log N) insertion.”

I believe it should have been:
“…binary trees have O (log N) search and O (log N) insertion.”