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
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Still loading...
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-201when refering to the line number in the algorithm, it reads "line ??" instead of "line 3", say, or "line 10"
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
20
21
22
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