ERRATA for Introduction to the Theory of Computation,
first printing

Errata for the second printing are now available.

Ordered by appearance in the text. Also available in order of discovery.
Last updated 1/28/98. Don't forget to reload this page to get the most current version.
Send additional errors and comments to: sipserbook@math.mit.edu


Page 4, fourth line.
Add "to" before "take".
Reported 2/3/97 Soeren Rolander Mogensen of Aalborg University, Denmark.
Page 11, fifth line from bottom.
Change "has a path" to "have a path".
Reported 9/7/97 by Raj D. Iyer of MIT.
Page 14, fourth text line from bottom.
Change "are 1" to "is 1".
Reported 9/7/97 by Raj D. Iyer of MIT.
Page 15, third line of second display.
Change "(Q -> Q)" to "(Q -> P)".
Reported 1/31/97 by Robert Prince of UC Santa Barbara.
Page 16.
Remove unnecessary "."s at end of lines 4, 5, 11, 12, and 17.
Reported 9/7/97 by Raj D. Iyer of MIT.
Erratum corrected 1/6/98 by Mike D. Jones of the University of Utah.

Page 27, Problem 0.10, first line.
For clarity, change "1=2" to "2=1".
Reported 9/11/97 by Mack Hendricks of Oakland University.
Page 40 , line 2.
Insert "the" before "language".
Reported 6/5/97 by Rudolf de Haan of the University of Stellenbosch, South Africa.
Page 40, fourth line.
The term "regular language" should not be used before it is defined at the bottom of this page in Definition 1.7.
Reported 2/11/97 by Michael Hoehle of Aalborg University, Denmark.
Page 46, last line of footnote 3.
Change "are" to "is".
Reported 2/4/97 by Michael Halper of Kean College.
Page 48, lines 5 and 6.
Exchange the first occurrences of "1" and "0" in the sentence beginning "State q1 . . . " .
Reported 1/9/97 by Joseph E. Fitzgerald of Dartmouth College.
Page 48, line 14.
The "0" should be a "1".
Reported 3/20/97 by Brad Ballinger of UC Davis.
Erratum corrected 5/15/97 by Thomas Janzen.

Page 50, Figure 1.16.
This figure is incorrect. Here is a (large) postscript corrected version a (still pretty big) compressed postscript version, and a pdf version.
Reported 1/16/97 by Jerry Grossman of Oakland University.
Erratum corrected 1/22/97 by John J. Crashell of the State University of New York at Buffalo.

Page 50, 2nd paragraph, 4th line.
Change "and split the finger on q1 into fingers on q1, q2 and q3" to "and the finger on q1 stays on q1".
Reported 4/15/97 by Kobus Vos of Stellenbosch University, South Africa.
Page 51, line 2.
Change "i.e." to "e.g.".
Reported 9/12/97 by Louis Barton of Harvard University.
Page 54, Example 1.18, table for \delta in part 3.
Exchange the entries ("{q1,q2}" and "{q1}") in columns 0 and 1 in the q1 row.
Discovered 1/16/97.
Page 55, Theorem 1.19, Proof Idea, second from last line.
Change "accept states of the NFA" to "accept states of the DFA".
Reported 8/6/97 by Joao Carlos Setubal of the University of Campinas, Brazil.
Page 56, 2nd paragraph before Corollary 1.20.
2nd line: Add "it" before "works".
4th line: Add "do" before "not".
Reported 1/21/97 by Michael Halper of Kean College.
Page 57, fourth sentence of the third paragraph.
Change "M's accept state {1}" to "N_4's accept state 1".
Reported 2/4/97 by Michael Halper of Kean College.
Page 68, first line.
Change "forward direction" to "easier direction".
Reported 2/11/97 by Michael Hoehle of Aalborg University, Denmark.
Page 69, Caption of Figure 1.28.
Change "(0 U 1)* 010" to "(a U b)* aba".
Reported 2/6/97 by John Clausen of Aalborg University, Denmark.
Page 71, first line.
Change GNFA into to DFA into a GNFA in.
Reported 10/26/97 by Geoff Davis of Otterbein College.
Page 77, first line after displayed equation for D.
Change "an recognizing" to "a recognizing".
Discovered 2/2/97.
Page 77, 4th line from the bottom.
Replace longer than by at least as long as to be consistent with the usage of the term "pumping length" in Theorem 1.37.
Reported 3/20/97 by Brad Ballinger of UC Davis.
Page 79, fifth from last line.
Change "s_{p-1}" to "s_{l-1}".
Reported 2/11/97 by Michael Hoehle of Aalborg University, Denmark.
Page 79, second from last line.
Change "j \neq p" to "j \neq l".
Reported 3/13/97 by Michael Hoehle of Aalborg University, Denmark and 3/16/97 by Giora Unger of the Hebrew University, Israel.
Page 80, line 3.
Change "of of" to "of".
Reported 2/26/97 by Kevin Fu of MIT.
Page 82, third paragraph, second sentence.
Remove the of in front of repetition.
Reported 3/20/97 by Timothy Yuen of UC Davis.
Page 84, Exercise 1.5, first line.
Insert "of" before "the following".
Reported 6/8/97 by Wojciech Marchewka of York University, Toronto.
Page 86, Exercise 1.17b.
The exercise as stated already appears as Example 1.40 on page 81, so change Exercise 1.17b to be {www| ... } .
Reported 9/17/97 by Jerry Grossman of Oakland University.
Erratum corrected 10/2/97 by David Stucki of Otterbein College.

Page 87, picture associated to Exercise 1.19.
Remove the double circles (indicating states as final).
Reported 3/20/97 by Phil Rogaway of UC Davis.
Page 88, Problem 1.23d.
Change "{0,1}" to "{0,1}^*".
Reported 9/20/97 by Christi Rockwell of Indiana University at Bloomington.
Page 88, Problem 1.27, third line.
Change "top bottom" to "bottom row".
Reported 8/12/97 by Owen Ozier and Mary Obelnicki of MIT.
Page 89, Problem 1.31.
Change "recognizes" to "accepts".
Reported 2/4/97 by Jerry Grossman of Oakland University.
Page 89, Problem 1.34, 3rd line.
Change "are members" to "is a member".
Reported 8/6/97 by Donald Nelson of Western Michigan University.
Page 89, Problem 1.37.
This problem is incorrect. Language F does not satisfy the pumping lemma (though showing that it does not is itself an interesting exercise). To correct the problem change F to be the language:

{ ai bj ck | i, j, k > 0, and if i = 1 then j = k }.

Reported 1/25/97 by Jerry Grossman of Oakland University.
Erratum corrected 9/26/97 by Jerry Grossman of Oakland University.


Page 93, first sentence following the CFG.
Grammar $g_2$ should be Grammar $G_2$.
Change nine terminals (the lower case words) to 27 terminals (the standard English alphabet plus a space character) (for consistency with line 6 from the bottom of page 94).
Reported 3/20/97 by Phil Rogaway of UC Davis.
Page 94, definition 2.1.
State that S is an element of V.
Reported 3/20/97 by Phil Rogaway of UC Davis.
Page 95, Figure 2.2, right-hand part.
Link is between for "a+a" and for "a".
Reported 12/14/97 by Daichi Mizuguchi of Indiana University, Bloomington.
Page 109, caption of Figure 2.10.
Replace equation by "(r,xyz) \in \delta(q,a,s)".
Reported 12/1/96 by Michael Halper of Kean College.
Erratum corrected 1/13/97 by Jerry Grossman of Oakland University.

Page 110, Figure 2.12.
Add an incoming arrow to the node labeled q_start.
Reported 7/6/97 by Wojciech Marchewka of York University, Toronto.
Page 115, first sentence following the statement of Theorem 2.19
"both v and y may not be the empty string" is poorly worded.
Change to "it is not the case that both v and y are the empty string."
Reported 3/20/97 by Phil Rogaway of UC Davis.
Page 117, paragraph 3, line 4
Change "\tau to be" to "that path to be".
Reported 3/20/97 by Phil Rogaway of UC Davis.
Erratum corrected 9/30/97 by Mauro A. Bonatti of Unisys.

Page 117, line 7 of Example 2.20.
Change have to be how .
Reported 3/20/97 by Eric Tria of UC Davis.
Page 118, Example 2.21.
Part 1, line 8: Change "doesn't appear in x or y" to "doesn't appear in v or y".
Part 2, line 3: Change "of B" to "of C".
Reported 9/14/97 by Baekjun Lim at Indiana University at Bloomington.
Page 120, Exercise 2.2 part a.
"Example 2.21" should say "Example 2.20".
Reported 11/4/96 by David M. Martin Jr. of Boston University.
Erratum corrected 1/22/97 by John J. Crashell of the State University of New York at Buffalo.

Page 120, Exercise 2.3c.
Change "tree" to "three".
Reported 2/6/97 by Jerry Grossman of Oakland University.
Page 122, Problem 2.20.
Change "more than b" to "at least 2^b".
Reported 3/13/97 by Michael Hoehle of Aalborg University, Denmark and 3/19/97 by Lyle McGeoch of Amherst College.
Erratum corrected 1/7/98 by Guy St-Denis of the Universite de Montreal.

Page 128, Definition 3.1, part 3.
Remove the braces around the blank symbol.
Reported 2/5/97 by Jerry Grossman of Oakland University.
Page 129, fifth line after Figure 3.3.
Change a and b in to a, b, and c in.
Reported 11/2/97 by Travis Gebhardt of Brandeis University.
Page 131 middle and page 132 middle.
Change "Q = ( . . . )" to "Q = { . . . }".
Reported 5/10/97 by Michael Halper of Kean College.
Page 131, 9th line from the bottom.
Change "state q4" to "state q3."
Reported 3/20/97 by Arash Madani of UC Davis.
Page 132, Example 3.5, second bullet.
Change "\Gamma = {0,1,#,blank}" to "\Gamma = {0,1,#,x,blank}".
Reported 9/23/97 by Michael Hoehle of Aalborg University, Denmark.
Page 135, line 4.
In the definition of language E, add "l > 1" (because algorithm M4 doesn't accept the empty string.)
Reported 5/13/97 by Suk Y. Lee of UC Santa Barbara.
Page 137, Theorem 3.8, first line.
Add "machine" after "Turing".
Reported 9/23/97 by Luca Aceto of Aalborg University, Denmark.
Page 140, Corollary 3.12.
Add if after if and only.
Reported 11/17/97 by Kong Lei of Queens College of the City University of New York.
Page 140, second line before Figure 3.8.
Add "of" before "an enumerator".
Reported 4/28/97 by Brian Sanders of Oakland University.
Page 148, Exercise 3.7.
Add p after polynomial.
Reported 11/3/97 by Jerry Grossman of Oakland University.
Page 149, Problem 3.12.
Add Turing machine after ordinary .
Reported 9/23/97 by Luca Aceto of Aalborg University, Denmark.
Page 149, problem 3.13, line 4.
Add Turing machine after ordinary .
The word to is missing after equivalent .
Reported 3/20/97 by Brad Ballinger of UC Davis.
Erratum corrected 5/15/97 by Thomas Janzen.

Page 153, second line from bottom.
Change as in a to as a.
Reported 10/10/97 by Raj D. Iyer of MIT.
Page 154, first line after proof of Theorem 4.3.
Change "and 4.2" to "4.2, and 4.3".
Reported 10/8/97 by Louis Barton of Harvard University and 10/10/97 by Raj D. Iyer of MIT.
Page 156, proof of Theorem 4.6.
Need to handle w = \emptystring as a special case, because derivations of length 2n-1 = -1 do not make sense.
Reported 4/14/97 by Jerry Grossman of Oakland University.
Page 156, line 1 after proof of theorem 4.6.
Should be "CFG" not "CFL".
Reported 11/21/96 by Isam M. Abdelhameed of the University of Illinois at Chicago.
Page 156, fourth line from bottom.
Add period to end of paragraph.
Reported 10/10/97 by Raj D. Iyer of MIT.
Page 156 last paragraph and page 158 line 3.
Change occurrences of "CFL" to "CFG" (total of three occurrences).
Reported 5/10/97 by Michael Halper of Kean College.
Page 162, last line in first paragraph.
Add "of" before "all".
Reported 1/21/97 by Michael Halper of Kean College.
Erratum corrected 5/15/97 by Thomas Janzen.
Erratum corrected 9/14/97 by Nicholas Riley of Brandeis University.

Page 169, Exercise 4.5.
Add that A is a DFA inside the braces.
Reported 3/20/97 by Arash Madani of UC Davis.
Page 173, line 7.
Remove extra word whether .
Reported 3/20/97 by Arash Madani of UC Davis.
Page 174, Stage 1 of algorithm S.
Add "w to" between "and" and "construct".
Reported 7/11/97 by Rong-Jaye Chen of Chiao Tung University, Taiwan.
Page 185, Parts 2 and 3.
Replace "Q" by "Q-{qreject}".
Reported 12/5/96 by David M. Martin Jr. of Boston University.
Page 189, lines 9 and 10.
Change each of the three occurrences of "character u" to "character in u".
Discovered 9/15/97.
Page 193, 2nd line after Theorem 5.22.
Change "except than" to "except that".
Reported 7/11/97 by Rong-Jaye Chen of Chiao Tung University, Taiwan.
Page 195, Problem 5.15, first line.
Change a input to an input.
Reported 10/28/97 by Luca Aceto of Aalborg University, Denmark.
Page 196, Problem 5.19, fourth line.
Change an CFG G to a CFG G.
Reported 11/17/97 by Kong Lei of Queens College of the City University of New York.
Page 196, Problem 5.19.
Change the last two line of the grammar to read:
T -> t1 T a1 | ... | tk T ak | t1 a1 | ... | tk ak
B -> b1 B a1 | ... | bk B ak | b1 a1 | ... | bk ak .
Reported 10/9/97 by Jeannie Fromer of MIT.
Page 206, second line.
Change assign to assigns.
Reported 10/24/97 by Raj D. Iyer of MIT.
Page 206, Example 6.9.
First and third lines: change both occurrences of M_1 to M_2.
Line following Example: Change Exercise 6.9 to Example 6.9.
Reported 10/24/97 by Raj D. Iyer of MIT.
Page 208, second and third lines.
Change \psi and \psi_i to \phi and \phi_i .
Reported 10/24/97 by Raj D. Iyer of MIT, and 10/28/97 by Luca Aceto of Aalborg University, Denmark.
Page 208, line 11 and line 7 from bottom.
Change \exist x_i to \exists x_{i+1} and
change \forall x_i and \not\exists\not x_i to \forall x_{i+1} and \not\exists\not x_{i+1}.
Reported 1/8/98 by Edmond Kayi Lee of MIT.
Page 209, Lemma 6.12, proof idea, fifth line.
Change "\psi_{M,w}" to "\phi_{M,w}".
Reported 9/25/97 by Georg Essl of Princeton University.
Page 211, four lines before Definition 6.16.
"simple" should be "simply".
Reported 11/7/96 by Max Rozenoer of MIT.
Page 212, Example 6.17, Machine N, step 1.
Change parallel in on to parallel on.
Reported 10/28/97 by Luca Aceto of Aalborg University, Denmark and 11/5/97 by Raj D. Iyer of MIT.
Page 212, Example 6.17, Machine N, step 2.
Change "halts on" to "accepts".
Reported 11/7/96 by Max Rozenoer of MIT.
Erratum corrected 1/22/97 by John J. Crashell of the State University of New York at Buffalo.

Page 217, paragraph 3 line 3, and Proof Idea line 2.
Change "s" to "x" in both places.
Reported 11/14/96 by Max Rozenoer of MIT.
Page 229, Definition 7.7, line 3.
"an O(t(n))" instead of "a O(t(n))".
Reported 12/9/96 by Farzan Fallah of MIT.
Page 232, fifth line from bottom.
Change uses is to uses.
Reported 12/1/97 by Luca Aceto of Aalborg University, Denmark.
Page 235, third paragraph, third sentence.
Add "to" before "develop".
Reported 5/15/97 by G. Allen Morris III of UC Berkeley.
Page 237, 2nd paragraph, 5th line.
Change "number or nodes" to "number of nodes".
Reported 8/4/97 by Peymann Gohari of the University of Toronto.
Page 238, third line in third paragraph.
Change D to G.
Reported 12/7/97 by Raj D. Iyer of MIT.
Page 240, last line.
Change "CFG L" to "CFL L".
Reported 11/14/96 by Max Rozenoer of MIT.
Page 241, last line before Section 7.3.
Change "running time of" to "number of stages executed by".
Reported 12/9/96 by Farzan Fallah of MIT.
Page 242, sixth line.
Change each node once to each node exactly once.
Reported 12/7/97 by Raj D. Iyer of MIT.
Page 247, alternative proof, stage 3 of algorithm N.
Change If both pass to If the test passes.
Reported 12/7/97 by Raj D. Iyer of MIT.
Pages 256-258.
Change all these occurrences (9 total) of M to N.
page 256, second line from bottom,
page 257, lines 2 (twice) and 4 from top, and lines 2, 5, and 14 after Figure 7.9,
page 258, lines 6 and 20 from bottom.
Reported 10/26/97 by Laurie Hiyakumoto of MIT.
Erratum corrected 1/7/98 by Guy St-Denis of the Universite de Montreal.

Page 257, fourth line.
Change an b to a b.
Reported 12/1/97 by Luca Aceto of Aalborg University, Denmark.
Page 258, first displayed expression.
Under the big AND sumbol, write "2<i<(nk-1), 1<j<(nk-1)" instead of "1<i,j<nk".
Reported 12/12/96 by Farzan Fallah of MIT.
Page 258, second displayed expression.
Exchange all first and second subscripts, e.g. xj,i-1,a1 \and ... .
Reported 12/9/96 by Soma Chaudhuri of Iowa State University.
Page 261, Figure 7.11.
Add an edge connecting the upper right node labeled x2\bar with the leftmost lower node labeled x2\bar.
Reported 11/14/96 by Li-Wei Lehman of MIT.
Erratum corrected 1/22/97 by John J. Crashell of the State University of New York at Buffalo.

Page 261, first paragraph of proof of Theorem 7.34, last sentence.
Remove "for" before "x".
Reported 1/3/97 by Farzan Fallah of MIT.
Erratum corrected 5/16/97 by Thomas Janzen.

Page 262, paragraph 2 line 4.
Change "edge gadgets" to "clause gadgets".
Reported 11/14/96 by Max Rozenoer of MIT.
Page 265-267, Figure 7.15.
This argument on page 267 that a Hamiltonian path must be normal is incorrect. To fix it we need to add an extra node between each of the pairs of nodes assigned to a clique in Figure 7.15.
Reported 11/13/96 Ran Libeskind-Hadas of Harvey Mudd College.
Page 267, Figure 7.19.
The rightmost node should be labeled "c".
Reported 11/7/96 by Farzan Fallah and Mariya Minkova of MIT.
Page 268, second paragraph, line 4.
Should be "vin" instead of "uin".
Reported 11/7/96 by Farzan Fallah of MIT.
Page 269, line 3 from bottom.
Change "j-1" to "k-j".
Reported 11/14/96 by Max Rozenoer of MIT.
Erratum corrected 10/25/97 by Edmond Kayi Lee and Laurie Hiyakumoto of MIT.

Page 273, Problem 7.23, last and third from last lines.
Change both occurrences of clique gadget to clause gadget.
Reported 12/4/97 by Allison Coates of UC Berkeley.
Page 275, Exercise 7.36.
Should say "P=NP" not "P \neq NP".
Reported 11/7/96 by Thomas Minka of MIT.
Page 278, Definition 8.2, 3rd and 5th lines.
Change "a O(f(n))" to "an O(f(n))".
Reported 1/3/97 by Farzan Fallah of MIT.
Page 278-279, Example 8.4.
Change all occurrences of "ENFA" to "ALLNFA".
Fourth line: Change "any" to "all".
Displayed equation: Change "\nullset" to "\Sigma*".
Third line after display: Add "not" before "accepted".
Page 282, line 3, and page 314, line 7 of proof of Theorem 9.15: Change occurrences of "ENFA" to "ALLNFA".
Reported 12/12/96 by Kyle Yung of MIT.
Erratum corrected 1/22/97 by John J. Crashell of the State University of New York at Buffalo.

Page 282, 13th and 16th lines.
Change "n 2^{O(f(n))}" to "f(n) 2^{O(f(n))}".
Reported 8/14/97 by Rong-Jaye Chen of Chiao Tung University, Taiwan.
Page 284, first line.
Change is the to as the.
Reported 12/7/97 by Raj D. Iyer of MIT.
Page 285, third line in third paragraph.
Change circuit representing to tableau representing.
Reported 12/7/97 by Raj D. Iyer of MIT.
Erratum corrected 1/7/98 by Guy St-Denis of the Universite de Montreal.

Page 285, line 9.
Change "if" to "if and only if".
Reported 3/10/97 by Shahadat Hossain of the University of Bergen, Norway.
Page 287, first line.
Change To calculate to size to To calculate the size.
Reported 11/17/97 by Kong Lei of Queens College of the City University of New York.
Page 289, line 3.
Remove extra "begin".
Reported 12/12/96 by Max Rozenoer of MIT.
Page 291, algorithm M.
Stage 3: Change "any" to "all".
Add Stage 0: REJECT if b has no outgoing edges.
Reported 11/16/96 by Bienvenido Velez-Rivera of MIT.
Page 291, last paragraph, third line.
"appears" instead of "appear".
Reported 11/15/96 by Farzan Fallah of MIT.
Page 292, first paragraph, second to last line.
"choose" instead of "chose".
Reported 5/14/97 by Kevin Fu of MIT.
Page 292, second paragraph, last line.
"Figure 8.4" instead of "the figure".
Reported 11/15/96 by Farzan Fallah of MIT.
Erratum corrected 5/15/97 by Thomas Janzen.

Page 292, last line.
"choose" instead of "chose" (2 occurences).
Reported 11/15/96 by Farzan Fallah of MIT.
Page 296, second line from bottom.
Change O(log f(n)) to O(f(n)).
Reported 11/16/96 by Bienvenido Velez-Rivera of MIT.
Page 297, fifth line in third paragraph.
Change in P to in NL.
Reported 12/1/97 by Raj D. Iyer of MIT.
Page 301, Stage 1 of algorithm M.
Change "c0 = 0" to "c0 = 1".
Reported 3/19/97 by Neal Young of Dartmouth College.
Erratum corrected 5/15/97 by Thomas Janzen.

Page 301, Stage 10 of algorithm M.
"an edge" instead of "a edge".
Reported 11/14/96 by Farzan Fallah of MIT.
Page 301, Stage 10 of algorithm M.
After "increment c_{i+1}." add "Go to stage 6 with the next node v."
Reported 2/20/97 by Neal Young of Dartmouth College.
Page 306, last line.
"number of bits" instead of "number bits".
Reported 11/14/96 by Farzan Fallah of MIT.
Page 307, last paragraph, first line.
"the way" instead of "that way".
Reported 11/14/96 by Farzan Fallah of MIT.
Page 310, Corollary 9.7, fourth line.
Change "purposes" to "purpose".
Reported 12/3/96 by Farzan Fallah of MIT.
Erratum corrected 5/15/97 by Thomas Janzen.

Page 310, Example 9.9, first sentence.
Change "at least n" to "at least n log n".
Remove the first function "n" from the next line.
Reported 5/17/97 by Alberto Medina of Northeastern University.
Page 311, 6 lines before end of proof idea.
Change "1/log n" to "1/log t(n)".
Reported 1/3/97 by Farzan Fallah of MIT.
Page 314, line 12 from bottom.
Add "M" after "TM".
Reported 12/12/96 by Max Rozenoer of MIT.
Page 316, line 7.
The variable Q is used for two different purposes here, (name of a regular expression and the set of states of the machine). To avoid confusion, change both occurrences of Q on line 7 (referring to M's state set) to Q'.
Reported 5/10/97 by Alberto Medina of Northeastern University.
Page 316, ninth line from bottom.
Change Thus S_1 generates to Thus S_i generates.
Reported 11/22/97 by Ching Law of MIT.
Page 317, lines 3 and 5.
Change 2(nk)-n to 2(nk)-n-2.
Reported 11/23/96 by Farzan Fallah of MIT.
Page 317, Figure 9.1.
Change 2(nk)-2 to 2(nk)-2.
Reported 11/14/96 by Geoff Lee Seyon of MIT.
Page 320, 7 lines before Stage i.
Change "P" to "PA".
Reported 12/12/96 by Max Rozenoer of MIT.
Page 321, fourth and sixth lines.
Change in A to in LA. (2 occurrences)
Reported 11/24/97 by Alberto Medina of MIT.
Page 328, first full paragraph.
line 3: Change "light[1,1,q0]" to "light[1,1,q0w1]".
line 4: Change "q0" to "q0w1", and "n+1" to "n".
line 5: Change "w1" to "w2".
line 7: Change "n+2" to "n+1".
Reported 12/12/96 by Max Rozenoer of MIT.
Erratum corrected 3/4/97 by Dave Isecke of Oberlin College.
Erratum corrected 1/7/98 by Guy St-Denis of the Universite de Montreal.

Page 332, Problem 9.18.
Change "result is l" to result is at least l" in the second sentence.
Add "s \in A" before "where" in the definition of pad(A,f(n)).
Reported 5/17/97 by Alberto Medina of Northeastern University.
Page 333, line 3.
Capitalize "computer".
Reported 3/31/97 by Jerry Grossman of Oakland University.
Page 335, second line before Theorem 10.2.
Change at most to at least.
Reported 11/24/97 by Alberto Medina of MIT.
Page 335, four lines before section 10.2.
Change "By the the" to "By the".
Reported 11/23/96 by Farzan Fallah of MIT.
Page 338, Algorithm M2.
Change "M2" to "M1" in stages 2 and 3.
Reported 5/17/97 by Alberto Medina of Northeastern University.
Page 339, first line in "PRIMALITY" subsection.
Change "a integer" to "an integer".
Reported 11/23/96 by Farzan Fallah of MIT.
Page 339, last paragraph.
Add that p and q are relatively prime.
Reported 12/3/96 by Farzan Fallah of MIT.
Page 342, line 6 of second paragraph of Proof.
Change "witness" to "nonwitness".
Reported 12/4/96 by Farzan Fallah of MIT.
Page 342, line 3 of third paragraph of Proof.
Change "c exists" to "t exists".
Reported 12/4/96 by Farzan Fallah of MIT.
Page 343, line 2 of Definition 10.10.
Change "recognized" to "accepted".
Reported 4/14/97 by Jerry Grossman of Oakland University.
Page 343, second line from bottom.
Change is NP-complete to is coNP-complete.
Reported 12/7/97 by Raj D. Iyer of MIT.
Page 345, algorithm D.
Change stages 1 and 2 as follows:
1. Select elements a1 through am at random from F.
2. Evaluate the polynomials p1 and p2 at a1 through am, without actually obtaining the polynomials.
Discovered 12/12/96.
Page 345, seventh line.
Change is NP-complete to is coNP-complete.
Reported 12/7/97 by Raj D. Iyer of MIT.
Page 347, line 5 of Induction step.
Change "arise" to "arises".
Reported 12/3/96 by Farzan Fallah of MIT.
Page 347, seventh line of Induction step.
Change though to through.
Reported 12/12/97 by Zulfikar Ramzan of MIT.
Page 355, first line of fourth paragraph.
Remove redundant words "at random".
Reported 12/8/96 by Mark Skandera of MIT.
Page 363, 2nd from last line in 3rd from last paragraph.
Change "be be" to "be".
Reported 1/3/97 by Farzan Fallah of MIT.
Page 364, 4th line.
Change " n2 " to " n-2 ".
Reported 1/3/97 by Farzan Fallah of MIT.
Page 367, second to last line.
Change "time" to "size".
Reported 6/3/97 by Alberto Medina of Northeastern University.
Page 368, Example 10.31, sixth line.
Change "i <= m" to "i <= n".
Reported 8/14/97 by Rong-Jaye Chen of Chiao Tung University, Taiwan.
Erratum corrected 1/7/98 by Guy St-Denis of the Universite de Montreal.

Page 369, Example 10.33.
Sixth line: Change "A^n" to "A^m", and change "O(n^5/2)" to "O(n^3)". Ninth line: Change "O(n^7/2)" to "O(n^5/2)".
Reported 8/14/97 by Rong-Jaye Chen of Chiao Tung University, Taiwan.
Page 378, Problem 10.11.
Change "Let B" to "Let M".
Reported 12/4/96 by Farzan Fallah of MIT.
Page 379, Problems 10.17 and 10.18.
Change second "family" to "branching".
Discovered 12/12/96.
Page 50, lines 8-9.
Change "split the finger on q1 into fingers on q1, q2, qnd q3" to "leave the finger on q1 where it is".
Reported 9/15/98 by Matthew Berman of MIT.