-
Notifications
You must be signed in to change notification settings - Fork 0
/
clrs-2e-bugs.html
1956 lines (1892 loc) · 104 KB
/
clrs-2e-bugs.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
<HTML>
<HEAD>
<TITLE>Introduction to Algorithms, Second Edition</TITLE>
</HEAD>
<BODY bgcolor=#FFFFFF text=#2A2A2A LINK=#146BEB VLINK=#242B86 ALINK=#C0C71A>
<a href="http://mitpress.mit.edu"><img src="http://mitpress.mit.edu/images/interface/colophon_text.gif" border="0" alt="The MIT Press" width="199" height="32"></a>
<BR>
<!-- <BR> -->
<TABLE BORDER=0 WIDTH="700" CELLPADDING=5>
<TR>
<TD WIDTH="101" VALIGN=top>
<BR>
<BR>
<FONT FACE="arial, helvetica" SIZE="-1"> </FONT>
<img src="http://mitpress.mit.edu/images/products/books/0262032937-f33.jpg" align="top" alt="Introduction to Algorithms">
</TD>
<TD WIDTH="353" VALIGN=top>
<!-- insert bug reports here-->
<FONT FACE="times, arial, helvetica">
<p>This page contains all known bugs and errata for <a href="http://mitpress.mit.edu/catalog/item/default.asp?ttype=2&tid=8570"><b><i>Introduction
to Algorithms</i>, Second Edition. </b></a>
<p>
<p>
Please send any reports of bugs, misprints, and other errata to <a href="mailto:[email protected]">[email protected]</a>.
<p>
<p> To determine which printing you have, look at page iv, which is
the copyright page just before the Table of Contents. If the bottom
line on the page is a sequence of numbers counting down from 20,
printed in a sans-serif font, then the last number on that line is the
printing number. Otherwise, find the line around the middle of the
page reading ``© 2001 by The Massachusetts Institute of
Technology''. If you have the first printing, the line above this
copyright line is blank. If you have any printing after the first,
the printing number is indicated on the line above this copyright
line.
<p>
<br>
<form action="bugs.php" method="post">
<br>Show errata in
<select name="printing">
<option value="12" >twelfth</option>
<option value="11" >eleventh</option>
<option value="10" >tenth</option>
<option value="9" >ninth</option>
<option value="8" >eighth</option>
<option value="7" >seventh</option>
<option value="6" >sixth</option>
<option value="5" >fifth</option>
<option value="4" >fourth</option>
<option value="3" >third</option>
<option value="2" >second</option>
<option value="1" selected>first</option>
</select>
printing<br><br>
<table border=0>
<tr><td><b>Order by</b></td></tr>
<tr><td>Date of posting </td>
<td><input type="radio" name="sort" value="date.asc" >least recent first </td>
<td><input type="radio" name="sort" value="date.desc" >most recent first </td>
<tr><td>Location </td>
<td><input type="radio" name="sort" value="location.asc" CHECKED>front to back </td>
<td><input type="radio" name="sort" value="location.desc" >back to front </td>
<tr><td>Severity </td>
<td><input type="radio" name="sort" value="severity.asc" >least to most severe </td>
<td><input type="radio" name="sort" value="severity.desc" >most to least severe </td>
<tr><td>Discoverer </td>
<td><input type="radio" name="sort" value="discoverer.asc" >A to Z </td>
<td><input type="radio" name="sort" value="discoverer.desc" >Z to A </td>
<tr><td><em>Or</em><big><big><big> </big></big></big></td></tr>
<tr><td><b>Incremental update</b></td></tr>
<tr><td>Errata posted on or <br>after April 25, 2009 </td>
<td><input type="radio" name="sort" value="cookie_date.asc" >front to back </td>
<td><input type="radio" name="sort" value="cookie_date.desc" >back to front </td>
<tr><td colspan=3>(This incremental update feature ignores the printing requested, and it requires cookies to be enabled. The date given is the most recent date on which you requested an incremental update. Because browsers may limit the number of cookies stored, the date remembered by this feature might revert to a default date.)</td></tr>
</table>
<table width=100% border=0><tr>
<br><br>
<td><input type="submit" name="show_errors" value="Show Errata"></td></table>
</form><br>
<hr>
<br>
<b>Severity levels</b>
<ol>
<li> A minor typographical error that should not affect your understanding (53 errors in first printing).
<li> A minor technical or expository error (135 errors in first printing).
<li> A more significant technical or expository error (41 errors in first printing).
<li> A serious error in the exposition of an algorithm, or an error that requires significant change to the text (11 errors in first printing).
</ol>
<hr><p>Page 14, bottom line. Change ``Medinas'' to
``Meidanis''.<br> Reported by Marcel K. de Carli Silva. Posted 6 December 2001.
<br> Severity level: 1
<br> Corrected in the third printing.
<hr>
<p>Page 20, line 13. Change ``<i>x</i> and <i>y</i> point
to (``are'') the same object'' to ``<i>x</i> and <i>y</i>
point to the same object''.<br> Reported by Jinoh Kim. Posted 25 March 2002.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 26, lines 17-18. Change ``so
<i>t<sub>j</sub></i> = <i>j</i>/2. If we work out the resulting
average-case running time, it turns out to be a quadratic function of
the input size'' to ``so <i>t<sub>j</sub></i> is about <i>j</i>/2.
The resulting average-case running time turns out to be a quadratic
function of the input size''.<br> Reported by Carlos Brizuela. Posted 26 October 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 44, line 26. Change ``the function
<i>f</i>(<i>n</i>) is on or below <i>g</i>(<i>n</i>)'' to ``the
function <i>f</i>(<i>n</i>) is on or below <i>cg</i>(<i>n</i>)''.<br> Reported by San Skulrattanakulchai. Posted 26 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 44, line 31. Change ``any quadratic function is in
<i>O</i>(<i>n</i><sup>2</sup>)'' to ``any such quadratic function
is in <i>O</i>(<i>n</i><sup>2</sup>)''.<br> Reported by San Skulrattanakulchai. Posted 26 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 44. Change the last sentence before the footnote to
read ``What may be more surprising is that when <i>a</i> > 0, any
<i>linear</i> function <i>an</i>+<i>b</i> is in
<i>O</i>(<i>n</i><sup>2</sup>), which is easily verified by taking
<i>c</i> = <i>a</i>+|<i>b</i>| and <i>n</i><sub>0</sub> = max(1,
-<i>b</i>/<i>a</i>).'' That is, add the condition that <i>a</i> >
0 and change the value of <i>n</i><sub>0</sub> to max(1,
-<i>b</i>/<i>a</i>).<br> Reported by Gerardo Quiñones and Linfeng Zhang. Posted 14 March 2005.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 50, Exercise 3.1-8. Change ``for all <i>n</i>
≥ <i>n</i><sub>0</sub> and <i>m</i> ≥
<i>m</i><sub>0</sub>'' to ``for all <i>n</i> ≥
<i>n</i><sub>0</sub> or <i>m</i> ≥ <i>m</i><sub>0</sub>''.<br> Reported by Charles Leiserson. Posted 1 July 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 51, inequality (3.7). There is an extra left
parenthesis in the expression on the right-hand side. The right-hand
side should read ''(<i>a</i> - (<i>b</i> - 1)) / <i>b</i>''.<br> Reported by Georgios Fainekos. Posted 22 July 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 83, line 7. Change ``≤'' to
``<''.<br> Reported by Luke Hodgkinson. Posted 19 August 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 85, Problem 4-2. Change the second paragraph of
the problem to read, ``Show that if the only way to access
information in array <i>A</i> is by this single-bit operation, we can
still determine the missing integer in <i>O</i>(<i>n</i>) time. Any
entire integer outside of <i>A</i> is still accessible in a single
operation.''<br> Reported by Balbir Singh. Posted 29 November 2006.
<br> Severity level: 3
<br> Corrected in the eighth printing.
<hr>
<p>Page 89, line 2. Change ``For the ``only if''
part'' to ``For the ``if'' part''.<br> Reported by Hui Zheng. Posted 12 November 2001.
<br> Severity level: 3
<br> Corrected in the third printing.
<hr>
<p>Page 90, line 2. The restriction on <i>b<sub>i</sub></i>
should read ``all <i>b<sub>i</sub></i> are greater than 1''.<br> Reported by Peter Hoyer. Posted 10 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 90, line 7. The summation should run from 1 to <i>k</i>
(not from 1 to <i>p</i>).<br> Reported by Peter Hoyer. Posted 7 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 94, last sentence before the exercises. There is an
extraneous ``a'' after the end of the sentence.<br> Reported by Tom O'Connell. Posted 4 August 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Pages 95-96. The variables <i>Y</i> and
<i>Y<sub>i</sub></i>, whose codomain is {<i>H</i>, <i>T</i>}, violate
the definition of a random variable on page 1106, which requires the
codomain to be the real numbers. The best correction removes these
variables altogether, recognizing that <i>H</i> and <i>T</i> are
events that can serve as arguments for the I{} notation. Make the
following changes:
<ul>
<li> Page 95, lines 7-10. Change ``Our sample space is <i>S</i> =
{<i>H</i>, <i>T</i>}, and we define a random variable <i>Y</i>
which takes on the values <i>H</i> and <i>T</i>, each with
probability 1/2. We can then define an indicator random variable
<i>X<sub>H</sub></i>, associated with the coin coming up heads,
which we can express as the event <i>Y</i> = <i>H</i>.'' to
``Our sample space is <i>S</i> = {<i>H</i>, <i>T</i>}, with
Pr{<i>H</i>} = Pr{<i>T</i>} = 1/2. We can then define an
indicator random variable <i>X<sub>H</sub></i>, associated with
the coin coming up heads, which is the event <i>H</i>.''
<p>
<li> Page 95, lines 13-14. Change the definition of
<i>X<sub>H</sub></i> to read ``<i>X<sub>H</sub></i> = I{<i>H</i>}
= 1 if <i>H</i> occurs, 0 if <i>T</i> occurs.'' (HTML does not
permit us to format the ``cases'' notation.)
<p>
<li> Page 95, lines 17-18. Change the first two lines of the
math display that calculates E[<i>X<sub>H</sub></i>] to read
<table>
<tr>
<td> E[<i>X<sub>H</sub></i>]
<td> =
<td> E[I{<i>H</i>}]
<tr>
<td>
<td> =
<td> 1 · Pr{<i>H</i>} + 0 · Pr{<i>T</i>}
</table>
<p>
<li> Page 96, lines 8-9. Change ``comes up heads. Letting
<i>Y<sub>i</sub></i> be the random variable denoting the outcome
of the <i>i</i>th flip, we have that <i>X<sub>i</sub></i> =
I{<i>Y<sub>i</sub></i> = <i>H</i>}.'' to ``comes up heads:
<i>X<sub>i</sub></i> = I{the <i>i</i>th flip results in the
event <i>H</i>}.''
</ul>
<br> Reported by Stanley Selkow. Posted 7 January 2003.
<br> Severity level: 3
<br> Corrected in the fourth printing.
<hr>
<p>Page 98, line 12. Change ``The expected interview
cost'' to ``The expected hiring cost''.<br> Reported by Kiyoung Yang. Posted 20 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 99, Exercise 5.2-5. Change ``Suppose that each element
of <i>A</i> is chosen randomly, independently, and uniformly from the
range 1 through <i>n</i>.'' to ``Suppose that the elements of
<i>A</i> form a uniform random permutation of <1, 2, ...,
<i>n</i>>.''<br> Reported by Tom Cormen. Posted 5 April 2002.
<br> Severity level: 3
<br> Corrected in the third printing.
<hr>
<p>Page 103, line 9. Change ``(See Appendix B.)'' to
``(See Appendix C.)''<br> Reported by Tom O'Connell. Posted 15 October 2001.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 103, line 10 from the bottom. Change ``We assume
that just before the (<i>i</i> - 1)st iteration'' to ``We assume
that just before the <i>i</i>th iteration''.<br> Reported by Tom Cormen. Posted 26 June 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 104, line 2 of
P<small>ERMUTE</small>-W<small>ITHOUT</small>-I<small>DENTITY</small>.
Change ``1 to <i>n</i>'' to ``1 to <i>n</i>-1''.<br> Reported by John Buck. Posted 20 February 2002.
<br> Severity level: 4
<br> Corrected in the third printing.
<hr>
<p>Page 114. The last sentence before Subsection 5.4.4
should read ``From these rough estimates alone, we can conclude that
the expected length of the longest streak is Θ(lg <i>n</i>).''
(Add the word ``expected.'')<br> Reported by Tom O'Connell. Posted 10 September 2001.
<br> Severity level: 2
<br> Corrected in the second printing.
<hr>
<p>Page 116, lines 1-5. Change ``whereas
<i>B<sub>i</sub></i> depends only on whether the value in position
<i>i</i> is greater than all the values 1 through <i>i</i>-1. The
ordering of positions 1 through <i>i</i>-1 does not affect whether
<i>i</i> is greater than all of them, and the value of <i>i</i> does
not affect the ordering of positions 1 through <i>i</i>-1.'' to
``whereas <i>B<sub>i</sub></i> depends only on whether the value in
position <i>i</i> is greater than the values in all other positions.
The ordering of the values in positions 1 through <i>i</i>-1 does not
affect whether the value in position <i>i</i> is greater than all of
them, and the value in position <i>i</i> does not affect the ordering
of the values in positions 1 through <i>i</i>-1.''<br> Reported by Tom O'Connell. Posted 12 October 2001.
<br> Severity level: 3
<br> Corrected in the third printing.
<hr>
<p>Page 118, Problem 5-2. Change the start of the first
sentence from ``Thus problem'' to ``This problem''.<br> Reported by Fredrik Manne. Posted 12 September 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Page 125, line 15. Change ``{1, 2, ..., <i>k</i>}''
to ``{0, 1, ..., <i>k</i>}''. On line 19, change ``and each
digit is in the set {1, 2, ..., <i>k</i>}'' to ``and each digit
can take on up to <i>k</i> possible values''.<br> Reported by Dave DeBarr. Posted 2 March 2005.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 129, line 19. Change ``presents five basic
procedures'' to ``presents some basic procedures''.<br> Reported by Nancy Uehara. Posted 13 September 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Page 133, last line. Change ``so we can express the
total cost of
B<small>UILD</small>-M<small>AX</small>-H<small>EAP</small> as'' to
``so we can express the total cost of
B<small>UILD</small>-M<small>AX</small>-H<small>EAP</small> as being
bounded from above by''.<br> Reported by Artem Matsak. Posted 26 August 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 144, line 15 of the Chapter notes. Change
``<i>O</i>((lg lg <i>n</i>)<sup>2</sup>) time'' to ``<i>O</i>(lg
lg <i>n</i>) time''.<br> Reported by Anna Veszprémi. Posted 22 July 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 144, line 27. Change ``Melhorn'' to
``Mehlhorn''.<br> Reported by Anna Veszprémi. Posted 30 April 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>The P<small>ARTITION</small> procedure puts all elements
equal to the pivot into the same partition. Therefore, if many
elements equal the pivot, the partitions are unbalanced, and the
average-case analyses of quicksort and selection in expected linear
time are incorrect. There are several changes in order to explicitly
state the assumption that elements are distinct:
<ul>
<li> Page 145, line 15. Change ``and in <i>O</i>(<i>n</i> lg
<i>n</i>) time on average.'' to ``and, assuming distinct
elements, in <i>O</i>(<i>n</i> lg <i>n</i>) time on
average.''
<p>
<li> Page 156, line 10. Change ``and then using this
understanding to derive an <i>O</i>(<i>n</i> lg <i>n</i>) bound
on the expected running time.'' to ``and then using this
understanding to derive an <i>O</i>(<i>n</i> lg <i>n</i>) bound
on the expected running time (assuming that the values of the
elements are distinct).''
<p>
<li> Page 157, line 4 from the bottom. Change ``In general, once
a pivot <i>x</i> is chosen'' to ``In general, because we
assume that element values are distinct, once a pivot <i>x</i>
is chosen''.
<p>
<li> Page 158, last line. Change ``is <i>O</i>(<i>n</i> lg
<i>n</i>).'' to ``is <i>O</i>(<i>n</i> lg <i>n</i>) when
element values are distinct.''
<p>
<li> Page 183, line 3 from the bottom. Change ``that achieves an
<i>O</i>(<i>n</i>) bound on the running time in the average
case.'' to ``that achieves an <i>O</i>(<i>n</i>) bound on
the running time in the average case, assuming distinct
elements.''
<p>
<li> Page 185, line 4 from the bottom. Change ``the expected time
of R<small>ANDOMIZED</small>-S<small>ELECT</small> is
Θ(<i>n</i>).'' to ``the expected time of
R<small>ANDOMIZED</small>-S<small>ELECT</small> is
Θ(<i>n</i>), assuming that the elements are distinct.''
<p>
<li> Page 187, line 4. Change ``and so we have'' to ``and so,
assuming that the elements are distinct, we have''.
<p>
<li> Page 192, Exercise 9.3-3. Change the exercise to read ``Show
how quicksort can be made to run in <i>O</i>(<i>n</i> lg
<i>n</i>) time in the worst case, assuming that all elements
are distinct.''
<p>
<li> Page 268, Exercise 12.4-5. Change ``a sequence of <i>n</i>
input numbers'' to ``a sequence of <i>n</i> distinct input
numbers''.
</ul><br> Reported by Jouni Järvinen. Posted 26 February 2003.
<br> Severity level: 4
<br> Corrected in the fourth printing.
<hr>
<p>Page 147, Figure 7.1 caption. In part (f), change ``The
values 3 and 8 are swapped'' to ``The values 3 and 7 are
swapped''.<br> Reported by Nafees Ud Din Ahmad. Posted 8 January 2002.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 148, Exercise 7.1-1. Because the array <i>A</i> has
its maximum element in the rightmost position, it does not serve as a
very interesting example for the P<small>ARTITION</small> procedure.
Switch the positions of the values 11 and 21 in the array so that
<i>A</i> = 〈 13, 19, 9, 5, 12, 8, 7, 4, 21, 2, 6, 11 〉.
[<em>Note</em>: In some browsers, the angle brackets around this
sequence appear as 〈 〉.]<br> Reported by Ronald Tungol. Posted 7 July 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 148, Exercise 7.1-2. Change ``so that <i>q</i> =
(<i>p</i>+<i>r</i>) / 2'' to ``so that <i>q</i> =
floor((<i>p</i>+<i>r</i>) / 2)''. (HTML does not permit us to print
the appropriate floor symbol.)<br> Reported by Antal Iványi. Posted 14 May 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 152, last line. Change ``of the average case''
to ``of the average case of a randomized version of
quicksort''.<br> Reported by Joel Seiferas. Posted 2 December 2001.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 157, line 20. Add the sentence ``Our analysis
assumes that each pivot is chosen randomly and independently.'' Page
158, line 8. Change ``Because the set <i>Z<sub>ij</sub></i> has
<i>j-</i><i>i</i>+1 elements,'' to ``Because the set
<i>Z<sub>ij</sub></i> has <i>j-</i><i>i</i>+1 elements, and because
pivots are chosen randomly and independently,''.<br> Reported by Charles Leiserson. Posted 15 September 2001.
<br> Severity level: 3
<br> Corrected in the second printing.
<hr>
<p>Page 159, last line. Change ``T. Hoare'' to
``C. A. R. Hoare''.<br> Reported by Charles Leiserson. Posted 2 October 2001.
<br> Severity level: 1
<br> Corrected in the third printing.
<hr>
<p>Page 160, Problem 7-1(a). Change ``after each
iteration of the <b>for</b> loop in lines 4-11'' to ``after each
iteration of the <b>while</b> loop in lines 4-11''.<br> Reported by Ronald Tungol. Posted 7 July 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 160, Problem 7-1. Change the sentence
immediately preceding part (b) to read, ``Assuming that the subarray
<i>A</i>[<i>p</i> .. <i>r</i>] contains at least two elements, prove
the following:''<br> Reported by Luke Hodgkinson. Posted 17 October 2005.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 161, Problem 7-2. In part (c), change ``Show that
equation (7.5) simplifies to'' to ``Show that equation (7.5) can
be rewritten as'', and change the summation to start at <i>q</i>=2.
In part (d), change the summation to start at <i>k</i>=2, and in the
hint change ``one for <i>k</i> = 1, 2, ...'' to ``one for
<i>k</i> = 2, 3, ...''. In part (e), change the hint to read
``Show, by substitution, that E[<i>T</i>(<i>n</i>)] ≤
<i>an</i> lg <i>n</i> for sufficiently large <i>n</i> and for some
positive constant <i>a</i>.''<br> Reported by Charles Leiserson. Posted 26 September 2001.
<br> Severity level: 3
<br> Corrected in the second printing.
<hr>
<p>Page 172, Lemma 8.3. Append to the statement of the
lemma ``if the stable sort it uses takes Θ(<i>n</i>+<i>k</i>)
time''.<br> Reported by Richard Beigel. Posted 7 April 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 172. In the paragraph just before the statement
of Lemma 8.4, change ``radix sort runs in linear time'' to
``radix sort can be made to run in linear time''. In the
statement of Lemma 8.4, add to the end the condition ``if the stable
sort it uses takes Θ(<i>n</i> + <i>k</i>) time''.<br> Reported by Amelio Vázquez-Reina. Posted 23 April 2008.
<br> Severity level: 2
<br> Corrected in the twelfth printing.
<hr>
<p>Page 174, first line of Section 8.4. Change
''<b><i>Bucket sort</i></b> runs in linear time'' to
''<b><i>Bucket sort</i></b> runs in linear expected time''.<br> Reported by Brendan McKay. Posted 23 July 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 174, Section 8.4. In the fifth line of the first
paragraph, change ``uniformly over the interval [0,1)'' to
``uniformly and independently over the interval [0,1)''. In the
third line of the second paragraph, change ``uniformly distributed
over [0,1)'' to ``uniformly and independently distributed over
[0,1)''.<br> Reported by Charles Leiserson. Posted 17 October 2005.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 187, line 19. Remove the outermost parentheses of
the expression, so that the <i>O</i>(<i>n</i>) term is not in the
summation.<br> Reported by Randy Goldman. Posted 3 November 2001.
<br> Severity level: 3
<br> Corrected in the third printing.
<hr>
<p>Page 188, line 6. Change ``Assume that
<i>T</i>(<i>n</i>) ≤ <i>cn</i>'' to ``Assume that
E[<i>T</i>(<i>n</i>)] ≤ <i>cn</i>''.<br> Reported by Zubair Adamjee. Posted 12 August 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 189, line 4. Change ``we have <i>T</i>(<i>n</i>) =
<i>O</i>(<i>n</i>)'' to ``we have E[<i>T</i>(<i>n</i>)] =
<i>O</i>(<i>n</i>)''.<br> Reported by Tom Cormen. Posted 21 May 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 190, last line of main text. Change ``greater
than<sup>1</sup> the median-of-medians <i>x</i>.'' to ``greater
than or equal to the median-of-medians <i>x</i>.<sup>1</sup>''.
Change the footnote to read ``Because of our assumption that the
numbers are distinct, all medians except <i>x</i> are either greater
than or less than <i>x</i>.''<br> Reported by Tom Cormen. Posted 1 June 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p> Page 191. Lines 13-14, change ''that any input of 140
or fewer elements'' to ''that any input of fewer than 140
elements''. Lines 16-17 (the bound on <i>T</i>(<i>n</i>)), change
the first case to ''<i>O</i>(1) if <i>n</i> < 140'' and change
the second case to hold ''if <i>n</i> ≥ 140''. Line 20,
change ''and all <i>n</i> ≤ 140'' to ''and all
<i>n</i> < 140''.<br> Reported by Tom Cormen. Posted 6 June 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 195, line 4 from the bottom. Change
``Schonhage'' to ``Schönhage''.<br> Reported by Zsolt Lencse. Posted 16 June 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 219. In seven places in the text of Problem 10-3,
calls to the procedures
C<small>OMPACT</small>-L<small>IST</small>-S<small>EARCH</small> and
C<small>OMPACT</small>-L<small>IST</small>-S<small>EARCH</small>´
should have the parameter <i>n</i> inserted as the second parameter of
the call.<br> Reported by István Fekete. Posted 29 April 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 223, Exercise 11.1-4. In the hint, change
``Use an additional stack, whose size is the number of keys'' to
``Use an additional array, treated somewhat like a stack whose size
is the number of keys''.<br> Reported by Jack Weinstein. Posted 4 June 2007.
<br> Severity level: 2
<br> Corrected in the tenth printing.
<hr>
<p>Page 234, Corollary 11.4. Add the following sentence at
the end of the proof: ``Since each operation takes Ω(1) time,
the Θ(n) bound follows.''.<br> Reported by Antal Iványi. Posted 22 September 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 234, line 29. Change ``hav <i>p</i> >
<i>m</i>'' to ``have <i>p</i> > <i>m</i>''.<br> Reported by Tom O'Connell. Posted 4 September 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Page 235, line 4 from the bottom. Change ``(by
inequality (3.7))'' to ``(by inequality (3.6))''.<br> Reported by H. Jun Lee. Posted 10 April 2002.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 244, Exercise 11.4-1. Change ``with the primary
hash function'' to ``with the auxiliary hash function''.<br> Reported by Scot Anderson. Posted 11 October 2001.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 246, Figure 11.6. For consistency with the scheme
that the first-level hash table has size <i>m</i> = <i>n</i>, the set
<i>K</i> in the figure should have 9 keys, rather than 7. Add the
keys 52 and 72 to the set <i>K</i> so that <i>K</i> = {10, 22, 37, 40,
52, 60, 70, 72, 75}. In the figure, change <i>m</i><sub>2</sub> to 9,
make secondary hash table <i>S</i><sub>2</sub> have 9 slots, and put
60 into slot 3, 72 into slot 4, and 75 into slot 7 of
<i>S</i><sub>2</sub>. All other slots of <i>S</i><sub>2</sub> are
empty. In line 5 of the caption, change ``Since
<i>h</i><sub>2</sub>(75) = 1, key 75 is stored in slot 1'' to
``Since <i>h</i><sub>2</sub>(75) = 7, key 75 is stored in slot
7''. In the figure, change <i>m</i><sub>7</sub> to 16, make
secondary hash table <i>S</i><sub>7</sub> have 16 slots, and put 40
into slot 7, 52 into slot 8, 22 into slot 9, and 37 into slot 14 of
<i>S</i><sub>7</sub>. All other slots of <i>S</i><sub>7</sub> are
empty.<br> Reported by Tom Cormen. Posted 16 January 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 249, last line in the statement of Corollary 11.12.
Change ``exceeds 4<i>n</i>'' to ``equals or exceeds
4<i>n</i>''.<br> Reported by Tom Cormen. Posted 16 January 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 250, Problem 11-1. In part (b), change ``at
most 1/<i>n</i><sup>2</sup>'' to
``<i>O</i>(1/<i>n</i><sup>2</sup>)''. In the paragraph between
parts (b) and (c), change ``Pr{X<sub><i>i</i></sub> > 2 lg
<i>n</i>} ≤ 1/<i>n</i><sup>2</sup>'' to
``Pr{X<sub><i>i</i></sub> > 2 lg <i>n</i>} =
<i>O</i>(1/<i>n</i><sup>2</sup>)''. In part (c), change ``Pr{X
> 2 lg <i>n</i>} ≤ 1/<i>n</i>'' to ``Pr{X > 2 lg
<i>n</i>} = <i>O</i>(1/<i>n</i>)''.<br> Reported by Stephan Stiller. Posted 20 November 2006.
<br> Severity level: 3
<br> Corrected in the eighth printing.
<hr>
<p>Page 251. In Problem 11-3, change step 3 to ``Set
<i>j</i> ← <i>j</i> + 1. If <i>j</i> = <i>m</i>, the table is
full, so terminate the search. Otherwise, set <i>i</i> ←
(<i>i</i> + <i>j</i>) mod <i>m</i>, and return to step 2.''
[<em>Note</em>: In some browsers, the left arrow symbol that we use
for ``gets'' appears as &larr;.]<br> Reported by Gabriel Nivasch. Posted 31 August 2005.
<br> Severity level: 3
<br> Corrected in the seventh printing.
<hr>
<p>Page 251, Problem 11-4. The problem has been rewritten.
You can get the new text in either <a
href="2e-page-changes/pp-251-252.ps">PostScript</a> or <a
href="2e-page-changes/pp-251-252.pdf">PDF</a>.<br> Reported by Charles Leiserson. Posted 5 November 2001.
<br> Severity level: 4
<br> Corrected in the third printing.
<hr>
<p>Page 265, lines 21-22. Change ``we let
<i>R<sub>n</sub></i> denote the random variable that holds this key's
rank within the set of <i>n</i> keys.'' to ``we let
<i>R<sub>n</sub></i> denote the random variable that holds this key's
<b><i>rank</i></b> within the set of <i>n</i> keys; that is,
<i>R<sub>n</sub></i> holds the position that this key would occupy if
the set of keys were sorted.''.<br> Reported by Johan Gade. Posted 31 May 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 267, lines 3-5. We also need to verify that
E[<i>Y</i><sub>0</sub>] ≤ (1/4) (3 choose 3). Change the
sentence to read ``For the base cases, we verify that the
bounds<br>0 = <i>Y</i><sub>0</sub> = E[<i>Y</i><sub>0</sub>]
≤ (1/4) (3 choose 3) =
1/4 and 1 = <i>Y</i><sub>1</sub> =
E[<i>Y</i><sub>1</sub>] ≤ (1/4) (1+3 choose 3) =
1<br>hold.'' (HTML does not permit us to format fractions or the
``choose'' notation properly.)<br> Reported by Sára Nagy. Posted 12 May 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 267, line 7 (second line of the math display bounding
E[<i>Y</i><sub><i>n</i></sub>]). Change the equal sign to
less-than-or-equal.<br> Reported by Tom Cormen. Posted 11 April 2002.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 278, procedure
L<small>EFT</small>-R<small>OTATE</small>. Replace line 3 by the two
lines<br> <b>if</b> <i>left</i>[<i>y</i>] ≠
<i>nil</i>[<i>T</i>]<br> <b>then</b>
<i>p</i>[<i>left</i>[<i>y</i>]] ← <i>x</i><br> [<em>Note</em>: In
some browsers, the left arrow symbol that we use for ``gets''
appears as &larr;.]<br> Reported by Timothy Haritun. Posted 22 October 2001.
<br> Severity level: 4
<br> Corrected in the third printing.
<hr>
<p>Page 285, caption for Figure 13.5. Change ``Case 1 of
the procedure RB-I<small>NSERT</small>'' to ``Case 1 of the
procedure RB-I<small>NSERT</small>-F<small>IXUP</small>''.<br> Reported by Lee May. Posted 9 February 2006.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 289, line 4. Remove the phrase, ``In the latter
case,''.<br> Reported by Lee May. Posted 9 February 2006.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 296, Problem 13-3(d). The statement of part (d)
asks for something that is not true. Change part (d) to read ``Show
that AVL-I<small>NSERT</small>, run on an <i>n</i>-node AVL tree,
takes <i>O</i>(lg <i>n</i>) time and performs <i>O</i>(1)
rotations.''.<br> Reported by Vassos Hadzilacos. Posted 10 October 2002.
<br> Severity level: 3
<br> Corrected in the fourth printing.
<hr>
<p>Page 301, line 8. Change ``Sleator and Tarjan [281]''
to ``Sleator and Tarjan [282]''.<br> Reported by Steve Witham. Posted 3 March 2005.
<br> Severity level: 1
<br> Corrected in the seventh printing.
<hr>
<p>Page 307, Exercise 14.1-1. Change
``OS-S<small>ELECT</small>(<i>T</i>, 10)'' to
``OS-S<small>ELECT</small>(<i>root</i>[<i>T</i>], 10)''.<br> Reported by Jouni Järvinen. Posted 24 March 2003.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 314, line 10 from the bottom. Remove the sentence
``(Note that no interval in the right subtree overlaps <i>i</i>--we
shall see why later.)''<br> Reported by Jørgen Villadsen. Posted 6 May 2002.
<br> Severity level: 3
<br> Corrected in the fourth printing.
<hr>
<p>Page 317, Exercise 14.3-7. Change ``<i>x</i>- and
<i>y</i>-axis'' to ``<i>x</i>- and <i>y</i>-axes'' and change
``a set of rectangles so represented'' to ``a set of <i>n</i>
rectangles so represented''.<br> Reported by Charles Leiserson. Posted 3 March 2005.
<br> Severity level: 1
<br> Corrected in the seventh printing.
<hr>
<p>Page 329, line 3 of
F<small>ASTEST</small>-W<small>AY</small>. The keyword ``to''
should be in boldface.<br> Reported by Curt Tilmes. Posted 15 September 2005.
<br> Severity level: 1
<br> Corrected in the seventh printing.
<hr>
<p>Page 329, lines 15-18 of
F<small>ASTEST</small>-W<small>AY</small>. Change the equals signs to
left arrows.<br> Reported by Nándor Érsek. Posted 22 September 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 330. Change the parameters of
P<small>RINT</small>-S<small>TATIONS</small> from ``(<i>l</i>,
<i>n</i>)'' to ``(<i>l</i>, <i>l</i><sup>*</sup>,
<i>n</i>)''.<br> Reported by Antal Iványi. Posted 12 July 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 340, line 12 from the bottom. Change ``1 ≤
<i>k</i> ≤ <i>j</i>'' to ``1 ≤ <i>k</i> <
<i>j</i>''.<br> Reported by Domenico Maria De Giorgio. Posted 22 August 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 343, line 14 from the bottom. Change ``then we
cannot solve it all'' to ``we cannot solve it at all''.<br> Reported by Luke Hodgkinson. Posted 2 September 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 347, line 4. Change ``through
<i>S</i><sub><i>i</i>,<i>j</i></sub>'' to ``through
<i>S</i><sub>1,<i>j</i></sub>''.<br> Reported by Luke Hodgkinson. Posted 2 September 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 361, line 14. Change ``for 1 ≤ <i>i</i>
≤ <i>n</i>'' to ``for 1 ≤ <i>i</i> ≤
<i>n</i>+1''.<br> Reported by Stefan Schumann. Posted 4 August 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 372, line 10. Change ``represent to entire
problem'' to ``represent the entire problem''.<br> Reported by John Buck. Posted 25 March 2002.
<br> Severity level: 1
<br> Corrected in the third printing.
<hr>
<p>Page 373, line 2. Change ``producing a another
solution'' to ``producing another solution''.<br> Reported by Erica Schultz. Posted 10 April 2002.
<br> Severity level: 1
<br> Corrected in the third printing.
<hr>
<p>Page 373, line 10. Change ``we can build an maximum''
to ``we can build a maximum''.<br> Reported by Jim Nastos. Posted 12 August 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Page 373, equation (16.3). The max needs to be over all
<i>k</i> such that <i>i</i> < <i>k</i> < <i>j</i> and also
<i>a<sub>k</sub></i> is in <i>S<sub>ij</sub></i>.<br> Reported by Bob Roos. Posted 16 November 2001.
<br> Severity level: 3
<br> Corrected in the third printing.
<hr>
<p>Page 374, line 8 from the bottom. Change ``there are
<i>j</i>-<i>i</i>-1 choices'' to ``there are up to
<i>j</i>-<i>i</i>-1 choices''.<br> Reported by Luke Hodgkinson. Posted 9 September 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Pages 375-378. As written, the procedure
R<small>ECURSIVE</small>-A<small>CTIVITY</small>-S<small>ELECTOR</small>
is flawed, in that it works only when <i>j</i> = <i>n</i>+1. It so
happens that in the initial call and all recursive calls, <i>j</i>
does equal <i>n</i>+1, but for general values of <i>j</i>, the
statement on page 375, lines 4-5 from the bottom, ``It returns a
maximum-size subset of mutually compatible activities in
<i>S<sub>ij</sub></i>'' does not hold. The best remedy is to
rewrite the procedure so that the fourth parameter is always <i>n</i>,
and have it return a maximum-size subset of mutually compatible
activities in <i>S</i><sub><i>i</i>,<i>n</i>+1</sub>. Pages 375-378
have been rewritten to accommodate this change. You can get the
updated pages in either <a
href="2e-page-changes/pp-375-378.ps">PostScript</a> or <a
href="2e-page-changes/pp-375-378.pdf">PDF</a>. <em>Note: these
updated pages were changed on 12 February 2002.</em><br> Reported by Paulo Feofiloff and Augusto Fernandes Vellozo. Posted 16 November 2001.
<br> Severity level: 4
<br> Corrected in the third printing.
<hr>
<p>Page 384, Exercise 16.2-2. Change ``where <i>n</i>
is number of items'' to ``where <i>n</i> is the number of
items''.<br> Reported by Eric Robinson. Posted 29 October 2004.
<br> Severity level: 1
<br> Corrected in the seventh printing.
<hr>
<p>Page 384, Exercise 16.2-6. Remove the sentence
``Assume that you have a solution to Problem 9-2.''<br> Reported by Joel Seiferas. Posted 5 December 2001.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 393. In the definition of a matroid, change the
first condition to ``<i>S</i> is a finite set.'' (Remove the
word ``nonempty.'')<br> Reported by Gene Luks. Posted 30 January 2003.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 393, Theorem 16.5. In the theorem statement,
change ``undirected graph'' to ``acyclic, undirected
graph''.<br> Reported by Martin Schweitzer. Posted 18 May 2006.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Page 393, Theorem 16.5. A previously posted error
said to change ``undirected graph'' to ``acyclic, undirected
graph'' in the theorem statement. That change was incorrect. The
original wording of the theorem statement, without ``acyclic,'' is
correct. The original error report has been removed from this
page.<br> Reported by Johannes Lipp. Posted 26 August 2008.
<br> Severity level: 2
<br> Corrected in the twelfth printing.
<hr>
<p>Page 400, line 4. Change ``so it also still early'' to
``so it also is still early''.<br> Reported by Jim Nastos. Posted 12 August 2001.
<br> Severity level: 1
<br> Corrected in the second printing.
<hr>
<p>Page 400. In the proof of Lemma 16.12, change
``since (2) implies that the <i>i</i>th largest deadline is at most
<i>i</i>'' to ``since (2) implies that the <i>i</i>th largest
deadline is at least <i>i</i>''.<br> Reported by Johannes Lipp. Posted 26 August 2008.
<br> Severity level: 2
<br> Corrected in the twelfth printing.
<hr>
<p>Page 403, Problem 16-3(b). At the end of this problem
part, change ``is matroid'' to ``is a matroid''.<br> Reported by Curt Tilmes. Posted 13 October 2005.
<br> Severity level: 1
<br> Corrected in the seventh printing.
<hr>
<p>Page 403, Problem 16-3. In part (e), change ``for a
directed graph <i>G</i> = (<i>V</i>, <i>E</i>)'' to ``for a
directed graph <i>G</i> = (<i>V</i>, <i>E</i>) with no self-loops''.
Page 531, Exercise 22.1-7. Change ``of a directed graph <i>G</i> =
(<i>V</i>, <i>E</i>)'' to ``of a directed graph <i>G</i> =
(<i>V</i>, <i>E</i>) with no self-loops''.<br> Reported by Holger Mauch. Posted 30 November 2005.
<br> Severity level: 2
<br> Corrected in the seventh printing.
<hr>
<p>Pages 408-409. Replace ``floor(lg <i>n</i>)'' by
``<i>k</i>-1''. (HTML does not permit us to print the appropriate
floor symbol.) Specifically, on page 408, line 2 from the bottom,
change ``for <i>i</i> = 0, 1, ..., floor(lg <i>n</i>)'' to ``for
<i>i</i> = 0, 1, ..., <i>k</i>-1''; on page 408, last line, change
``For <i>i</i> > floor(lg <i>n</i>)'' to ``For <i>i</i>
≥ <i>k</i>''; and in page 409, line 2 of the text, change
the upper bound of the first summation from ``floor(lg <i>n</i>)''
to ``<i>k</i>-1''.<br> Reported by Tom Cormen. Posted 23 April 2002.
<br> Severity level: 3
<br> Corrected in the fourth printing.
<hr>
<p>Page 416, Exercise 17.3-7. <i>S</i> should be a dynamic
set. In the first sentence, change ``for a set <i>S</i>'' to
``for a dynamic set <i>S</i>''. Change the description of the
I<small>NSERT</small> operation to ``I<small>NSERT</small>(<i>S</i>,
<i>x</i>) inserts <i>x</i> into <i>S</i>.''<br> Reported by Ralf Juengling. Posted 28 May 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 416, Exercise 17.3-7. The exercise should
clarify that duplicate values are allowed, and so <i>S</i> is a
dynamic multiset rather than a dynamic set. It should also specify
that there should also be a way to output the elements of <i>S</i> in
<i>O</i>(|<i>S</i>|) time.<br> Reported by Kevin Liu. Posted 21 December 2004.
<br> Severity level: 3
<br> Corrected in the seventh printing.
<hr>
<p>Page 416, Exercise 17.3-7. In the specification for
D<small>ELETE</small>-L<small>ARGER</small>-H<small>ALF</small>(<i>S</i>),
change ``ceiling(<i>S</i>/2)'' to ``ceiling(|<i>S</i>|/2)''.
(HTML does not permit us to print the appropriate ceiling symbol.)<br> Reported by Eric Rupert. Posted 3 October 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 422, line 21. Change ``α[<i>T</i>] = 1''
to ``α(<i>T</i>) = 1''.<br> Reported by Tom Cormen. Posted 29 May 2008.
<br> Severity level: 1
<br> Corrected in the twelfth printing.
<hr>
<p>Page 431. The footnote should be numbered ``1''
rather than ``2''.<br> Reported by Nándor Érsek. Posted 8 September 2003.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 442, line 21. Change ``The number of disk pages
accessed by B-T<small>REE</small>-S<small>EARCH</small> is therefore
Θ(<i>h</i>) = Θ(log<sub><i>t</i></sub> <i>n</i>)'' to
``The number of disk pages accessed by
B-T<small>REE</small>-S<small>EARCH</small> is therefore
<i>O</i>(<i>h</i>) = <i>O</i>(log<sub><i>t</i></sub> <i>n</i>)''.<br> Reported by Jouni Järvinen. Posted 10 April 2002.
<br> Severity level: 2
<br> Corrected in the third printing.
<hr>
<p>Page 455, line 4 from the bottom of the main text.
Change ``in worst-case time <i>O</i>(lg <i>n</i>) (or better) on a
binary heap'' to ``in worst-case time <i>O</i>(lg <i>n</i>) on a
binary heap''.<br> Reported by Zoltán Csörnyei. Posted 12 May 2003.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 456, Figure 19.1. The entry with row label
``U<small>NION</small>'' and column label ``Binomial heap
(worst case)'' should read ``Θ(lg <i>n</i>)'' rather than
``<i>O</i>(lg <i>n</i>)''. Page 473, Exercise 19.2-10. The
worst-case running time of
B<small>INOMIAL</small>-H<small>EAP</small>-U<small>NION</small> is
Ω(lg <i>n</i>), so this procedure should be moved from the list
in the second sentence of the exercise to the list in the first
sentence.<br> Reported by Greg Plaxton. Posted 2 November 2004.
<br> Severity level: 3
<br> Corrected in the seventh printing.
<hr>
<p>Page 458, proof of part (3) of Lemma 19.1. The reason
``(by the inductive hypothesis)'' should appear on the second line
of the display (not the first line), and the reason ``(by Exercise
C.1-7)'' should appear on the third line of the display (not the
second line).<br> Reported by Beau Skinner. Posted 28 June 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 468, line 3 of
B<small>INOMIAL</small>-H<small>EAP</small>-E<small>XTRACT</small>-M<small>IN</small>.
Change the line to read ``reverse the order of the linked list of
<i>x</i>'s children, setting the <i>p</i> field of each child to
<small>NIL</small>, and set <i>head</i>[<i>H</i>´] to point to
the head of the resulting list''.<br> Reported by Jouni Järvinen. Posted 14 April 2003.
<br> Severity level: 4
<br> Corrected in the fifth printing.
<hr>
<p>Page 477, line 12. Change ``a handle to
corresponding'' to ``a handle to the corresponding''.<br> Reported by Beau Skinner. Posted 28 June 2004.
<br> Severity level: 1
<br> Corrected in the fifth printing.
<hr>
<p>Page 480, line 5. Change ``<i>D</i>(<i>n</i>) = lg
<i>n</i>'' to ``<i>D</i>(<i>n</i>) = floor(lg <i>n</i>)''.
(HTML does not permit us to print the appropriate floor symbol.)<br> Reported by Johan Gade. Posted 31 May 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 482, line 4 of
F<small>IB</small>-H<small>EAP</small>-U<small>NION</small>. Change
the condition ``<i>min</i>[<i>H</i><sub>2</sub>] <
<i>min</i>[<i>H</i><sub>1</sub>]'' to
``<i>key</i>[<i>min</i>[<i>H</i><sub>2</sub>]] <
<i>key</i>[<i>min</i>[<i>H</i><sub>1</sub>]]''.<br> Reported by Doug Dunham. Posted 10 April 2002.
<br> Severity level: 4
<br> Corrected in the third printing.
<hr>
<p>Pages 484-485, Figure 20.3. In parts (f), (g), and
(h), node <i>w</i> should be the node with key 7. In part (k), node
<i>w</i> should be the node with key 52.<br> Reported by Jens Kristian Jensen. Posted 20 November 2002.
<br> Severity level: 2
<br> Corrected in the fourth printing.
<hr>
<p>Page 490, line 30. Change ``performs a
<b><i>cascading-cut</i></b> operation on <i>y</i>'' to ``attempts
to perform a <b><i>cascading-cut</i></b> operation on <i>y</i>''.<br> Reported by Johan Gade. Posted 31 May 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 493, proof of Lemma 20.1. In the second sentence of
the proof, change ``<i>degree</i>[<i>x</i>] = <i>i</i>-1'' to
``<i>degree</i>[<i>x</i>] ≥ <i>i</i>-1''. In the third
sentence of the proof, change ``<i>degree</i>[<i>y<sub>i</sub></i>]
= <i>i</i>-1'' to ``<i>degree</i>[<i>y<sub>i</sub></i>] ≥
<i>i</i>-1''.<br> Reported by Tom Cormen. Posted 13 February 2004.
<br> Severity level: 2
<br> Corrected in the fifth printing.
<hr>
<p>Page 495, proof of Lemma 20.3. The first paragraph of the
proof does not make it clear that <i>z</i> may be in any Fibonacci
heap. There is no need to give a value for <i>s</i><sub>2</sub>,