Errata for Foundations of Computer Science

    We shall try to keep users informed of errata. As we hear of mistakes, the PDF sources will be altered to reflect changes, if possible. You may assume that downloads taken after the date indicated in the table do not have the error.

    Found an error not listed in the table below? Please send email to ullman at gmail dt com.

    LocationProblemReported ByDate Fixed
    p. 46, l. -14 "The goal is" should be "The goal". Don Voita 11/4/09
    p. 48, l. 9 E2 should be E1. Vinay Sachdev 2/5/09
    p. 82, l. -3 "Exercise 2.2.8" should be "Exercise 2.2.7". Vinay Sachdev 3/8/09
    p. 88, l. 4 Delete one "need". Jason W. Powell 12/16/08
    p. 131 l. 5, 6, 7 The time for line 3 is O(1)+O(n). Thus, the expression on l. 6 has the order of the middle terms reversed (i.e., the O(n2) term should be second, as it comes from line (2) of main. Also, "third" on l. 7 should thus be "second". Vinay Sachdev 1/6/09
    p. 170, Exercise 4.4.6. (a-b+1) should be (b+1). Sivaiah Nallagatla 11/2/09
    p. 172, l. 15 and p. 178, l. 1 min(n,n-m-1) should be min(m,n-m-1). Vinay Sachdev 5/12/09
    p. 199, last full paragraph R1 and R3 are interchanged throughout. Vinay Sachdev 7/17/09
    p. 206, l. 20 "0-05" should be "0.05". Vinay Sachdev 7/17/09
    p. 270, l. 8-9 The three exponents should each be increased by 1. Vinay Sachdev 9/29/09
    p. 451ff The figure, example, and other numbers in Ch. 9 were missing. They are now restored. Jason W. Powell 12/28/08
    p. 767, l. 6 "Fig. 11.2(b)" should be "Fig. 8.2(b)". Dave Seiler 11/23/08