Home Blog Index Search Articles Books Contact Me About Rod
Follow me on Twitter RSS Feed
Essential Algorithms: A Practical Approach to Computer Algorithms

Overview Table of Contents Downloads
Info at Wiley.com Barnes & Noble Amazon
Errata P2P Forum
 

During the writing of this book, I wrote and rewrote it several times and more than half a dozen technical and non-technical editors looked it over to try to make it the best book possible. Unfortunately no project this large is ever completely free of errors and this one is certainly no exception. It's sort of like writing a 300,000 word program without the benefit of a compiler to check your logic, spelling, and grammar.

Below is a list of errors that have been found in various editions of the book. Note that some errors appear in one edition and not others. For example, some errors seem to have been introduced during the process of converting the book from its initial print and pdf form into the ePub form used by the iPad. Errors in the print edition probably occur in all editions.

Also note that page number doesn't apply to electronic formats because the page numbering depends on the size of your book reader and the fint you are using.

If you find other errors, please let me know.

ChapterPageEditionDetails
- - ePub/iPad The formulas that are not contained in paragraphs seem to be fuzzy. I think this is a technical issue. I suspect eReader devices cannot render complex formulas so the formulas are included as images. That means they may get fuzzy if you zoom in or out. Aorry about that but I don't think there's anything we can do about this.
1 na ePub/iPad While discussing Big O notation, the italicized restatement of Rule #4 says:
... the algorithm's total performance is O(f(N) + g(N)).
That should read:
... the algorithm's total performance is O(f(N) × g(N)).
1 12 Print The end of the first paragraph after the "Logarythms" box says:
It's a sorted tree because every node's value lies between the values of its left and right child nodes.
It is true that a sorted tree has this property but more precisely the text should say:
It's a sorted tree because every node's value is at least as large as its left child and no larger than its right child.
1 14 Print The fourth paragraph says:
A full complete binary tree of height H has 2H nodes.
This text was trying to be approximate so it should have said the tree has approximately 2H nodes. More precisely a full complete binary tree of height H has 2H+1 - 1 nodes. (This fact is mentioned in the second bullet point on page 232.)

Given this change, the sentence that follows on page 14 should also be corrected. Again if you're lookign at Big O notation, a full complete binary tree containing N nodes has height roughly log2(N). More precisely the height is log2(N + 1) - 1. (See the third bullet point on page 232.)
1 14 Both The middle of the page says:
Setting B = 2, you can use this formula to convert the value O(Log2(N) into any other log base A:
This should be:
Setting B = 2, you can use this formula to convert the value O(Log2(N)) into any other log base A:
1 17 Print The column of values for the factorial function N! is wrong. The correct values are:

NN!
11
5120
103.6×106
151.3×1012
202.4×1018
503.0×1064
1009.3×10157
1000
10000
100000
2 40 Print The fourth paragraph in the section "Testing for Primality" says:
Fermat's "little theorem" states that if p is prime and 1 ≤ n p, np-1 Mod p = 1.
This should say:
Fermat's "little theorem" states that if p is prime and 1 ≤ n < p, np-1 Mod p = 1.
2 36 Print The fourth paragraph on the page begins:
More generally, for the exponent P, the algorithm calculates log(P) powers of A. It then examines the binary digits of A to see which of those powers it must multiply together to get the final result.
This should read:
More generally, for the exponent P, the algorithm calculates log(P) powers of A. It then examines the binary digits of P to see which of those powers it must multiply together to get the final result.
2 39 Print The FindPrimes algorithm uses this code:

    While (next_prime < stop_at)

This should be:

    While (next_prime <= stop_at)

You should make the corresponding correction to example program SieveOfEratosthenes. (To see the problem, enter 9 for the maximum number.)
2 53 Print Exercise 14 says:
In an infinite set of composite numbers called Carmichael numbers, every relatively prime smaller number is a Fermat liar. In other words, p is a Carmichael number if every n where 1 n p and GCD(p, n) = 1 is a Fermat liar.
This should read:
In an infinite set of odd composite numbers called Carmichael numbers, every relatively prime smaller number is a Fermat liar. In other words, p is a Carmichael number if p is odd and every n where 1 < n < p and GCD(p, n) = 1 is a Fermat liar.
2 53 Print The solution to Exercise 14 (the CarmichaelNumbers program) can be improved. This code:

    // Check for Carmichael numbers.
    for (int i = 2; i < maxNumber; i++)

Should be the following (to check for only odd Carmichael numbers):

    // Check for Carmichael numbers.
    for (int i = 3; i < maxNumber; i += 2)

Inside the IsCarmichael method, this code:

    // Check all possible witnesses.
    for (int i = 1; i < number - 1; i++)

Should be this:

    // Check all possible witnesses.
    for (int i = 2; i < number; i++)
10 243 Print Throughout that section, depth-first traversal should be breadth-first traversal. A breadth-first traversal visits all of the nodes across the breadth of one level before moving down to the next level in the tree. All of the other algorithms (preorder, inorder, and postorder) are actually depth-first traversals.
30 na ePub/Kindle I think this may have been a translation error when the eBook edition was created. I think the text is a bit different in the print edition. The eBook version looks something like this:
For example, to get a value between 1 and 100, you would calculate the following:
result = Min + (Number / M) * (Max - Min)
The problem with this is that it may make some results more likely than others.

In the print edition, that text looks like this:
Usually a program needs a random number within a range other than 0 to M. An obvious but bad way to map a number produced by the generator into a range Min to Max is to use the following equation:
result = Min + number Mod (Max - Min + 1)
For example, to get a value between 1 and 100, you would calculate the following:
result = 1 + number Mod (100 - 1 + 1)
The problem with this is that it may make some results more likely than others.

The key difference is the parts of the equation highlighted in red.

I think with that change it makes sense. Please let me know if it doesn't make sense to you.
App B 488 Print The solution to exercise 1-3 has the roles of the two algorithms are reversed. The correct solution should be:
The question is, "For what N is 1,500 × N > 30 × N2?" Solving for N gives 50 < N, so the second algorithm is slower if N > 50. You would use the second algorithm if N ≤ 50 and the first if N > 50.