15210 Book Errata and Comments
Comments
 Share
The version of the browser you are using is no longer supported. Please upgrade to a supported browser.Dismiss

 
$
%
123
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
ABCDEFGHIJKLMNOPQRSTUVWXYZ
1
Page Number or other descriptorDescription of the ErrorResponse from the authors (if applicable)
2
inconsistent notationthroughoutsometimes you write log n, sometimes lg n. stick to one; i prefer the latter myself.
3
typopg 96, Example 6.2missing ) in the description of R: (3,a}
4
typopg 104, Example 6.10result for collect cmp kv is incorrect: extra "jack" in the collected sequence for jack, extra ) in the collected sequence for mary
5
6
7
possible algorithm errorPage 31, Chap. 6 (Sequences)In algorithm 6.34, should "all" be defined as <n mod i : 2 <= i <= sqrt(n) > instead of i mod n?
8
possible algorithm errorPage 33, Chap. 6 (Sequences)In algorithm 6.36, should values of i =1 and j = 1 be avoided in constructing cs to avoid including primes? Also, should sieve = <(x,false) : x in cs> instead of true?
9
work recurrence errorpage 66I believe that the work recurrence for example 4.25, randomized quicksort on a sequence assuming pivot division of the sequence into two equal sized halves at each level, should be W(n) = 2W(n/2) + Theta(n). The example currently uses Theta(1), which would result in the recurrence giving a work of Theta(n). Furthermore, there is a typo in stating the work, as it says WCn) = Theta(nlgn) rather than W(n) = Theta(nlgn)
10
typopage 64In example 4.23, the Work equation says W(n) = 2*W(n/2) + O(1), but instead of O(1), it should be O(n), as the text in the example states.
11
missing informationp200-201
12
typopage 203 (2nd to last ¶)missing mean of adjestment or "by" should be removed
13
typos204 (last ¶)replace th with the and replace none with note
14
missing information214under expected span of quicksort there is "Section ??"
15
possible error160it says the expected value of geometric random variable X, E[X] is p. also, the grammar is wrong.
16
typo327 (Problem 19.10)It says " S = \Sigma^* and T = \Sigma^* " but it should read " S, T \in \Sigma^* "
17
possible algorithm errorpage 135Algorithm 8.4, second to last line: sL and sR should be combined using f instead of op+
18
possible algorithm errorpage 333implementation of memo: return type is inconsistent; the first branch of case statement should return (M, v)
19
"There are several reason for why"page 4"reason" should be "reasons"
20
"For example,an Internet"page 4There should be a space between "example," and "an"
21
page 71Duplicate entry of W(n) = 2W(n/2)+nlogn
22
typopage 220-> in a function definition, rather than in a type
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
Loading...
 
 
 
Sheet1