Errata 3rd Edition Introduction to the Analysis of Algorithms

Pg x, line -5 (quote), roof(top)s not root(top)s


Pg 4, line 3 of Section 1.1.2: q=3 should be replaced by q=8.
(January 24, 2019, by Roberto Ramirez Casas)


Pg 7, line 5 (Problem 1.9(c)): instead of min{m,n}, it should be min{(m)_b,(n)_b}, that is, the running time ought to be bound in terms of the length of the binary encoding of the inputs, not their values.


Pg 7, line 1 of section 1.1.4 “Palindromes”: the last word on the line should be reads not read.


Pg 12, consider paragraph above Figure 1.1. The sentence that starts “Consider Figure 1.2…” should be replaced with “Consider Figure 1.1…”


Pg 21, modified the formula in the solution to Problem 1.7, and clarified it. More precisely, deleted the last two lines of the centered equations that start: $latex r_{i+1}=\text{rem}(m_{i+1},n_{i+1})$


Pg 190, the introductory three paragraphs of section 8.4 have been rewritten as a single paragraph:

[Chomsky (1965)] is concerned with the problem of defining a “generative” grammar for the English language, that is, with the syntax that defines strings which are well-formed sentences of the English language. Even though this approach did not fully work in linguistics, it had collosal consequences in Computer Science, as it provided the techniques needed to define preciesly the syntax of a programming language.

The first language to be designed according to those principles was ALGOL (the great grand-parent of C, C++, Pascal, etc.). ALGOL was based on Chomsky grammars, and hence unreadable for humans; this is why first ALGOL programmers introduced the notion of indentation.

as well as a paragraph in the Notes for chapter 8.


Pg 205, line -6, Thus, to propose, rather than have


Pg 217, first line of Problem 8.1, k not k (math italics)


Pg 297, 2nd entry from top, Franceschet, PageRank, not Pagerank