ERRATA 1.2 for Introduction to Algorithms by Cormen, Leiserson, and ...
ERRATA 1.2forIntroduction to Algorithmsby Cormen, Leiserson, and RivestJuly 28, 1994This list describes the known bugs in the second and subsequent printingsof the rst edition ofIntroduction to Algorithms. An errata sheet for the rstprinting is available separately.Typically, page and line numbers are given to localize the error. A negativeline number indicates numbering from the bottom up. The nder of each bugis credited on the right margin. Actual text from the book is surrounded by . Replacement text, where provided, is surrounded byhhii.A PostScript version of this errata sheet is available via an Internet elec-tronic mail server. To receive instructions on how to use this service, sendelectronic mail toalgorithms@theory.lcs.mit.eduwithSubject: help"in the message header. The instructions also describe how to submit bug re-ports by email and how to obtain errata for the rst printing. We regret thatwe cannot personally respond to all mail.Page xvi, line 28Hershel SaferChange Herschel Safer tohhHershel Saferii.Page 11, Exercise 1.2-3Julie SussmanExercise 1.2-3 depends on material introduced later in Chapter 1. Move it toSection 1.4.BugfixedPage 15, Exercise 1.3-3Stanley SelkowChange Use mathematical induction to show that the solution of therecurrence tohhUse mathematical induction to show that when n is an exactpower of 2, the solution of the recurrenceii.BugfixedPage 24, lines 22 24Charles E. LeisersonReplace the text every member of g n withhhevery member f n 2 g n ii. After the end of the sentence, insert the sentencehh Anasymp-totically positivefunction is one which is strictly positive for all su cientlylarge n. ii. As a result of this change, on page 33, line 9, the words asymp-totically positive should no longer be boldfaced.2Page 27, line 11Ron RivestThe text on or above g n . should be changed tohhon or above cg n .ii.Page 32, line 2George E. CollinsThe condition b6= 0 should be changed tohhb 0ii.Page 33, line 3Michael ErnstThe statement Thus, any positive exponential function grows faster thanany polynomial. should be restatedhhThus, any exponential function witha base strictly greater than 1 grows faster than any polynomial function.ii.Page 35, line 13Hal GabowThe text limn!1lgbn2algn should be replaced byhhlimn!1lgbn 2a lgnii.Page 35, equation 2.12 Greg ShannonThe upper bound for n! is incorrect for n7, but is correct, although loose,for n8. The upper bound should be changed to read as follows:hhn!p2n n=e ne1=12n:iiPage 55, line 10Julie SussmanThe symbol should be replaced byhhii.Page 55, line 18Julie SussmanThe constraint c2 should be changed to c1 .Page 67, line 2 of gure captionJulie SussmanThe text height logba should be changed tohhheight logbnii.Page 71, line 1Julie SussmanThe symbol should be replaced byhh=ii.Page 73, Problem 4-4, line 2Richard AndersonChange n2 tohhn8ii.3Page 82, line 11Lon SunshineChange equivalent to A. to equivalent to a. .Page 87, line 14Charles LeisersonThe termisolatedis not de ned. Add the sentencehhA vertex whose degreeis 0, such as vertex 4 in Figure 5.2 b , isisolated.iiafter has degree 2. .Page 88, lines 12 13Bruce MaggsThe text In an undirected graph, a pathhv0;v1;...;vkiforms acycleif v0=vkand v1;v2;...;vkare distinct. should be replaced byhhIn an undirectedgraph, a pathhv0;v1;...;vkiforms a simple cycleif k3, v0= vk, andv1;v2;...;vkare distinct.ii.Page 90, Exercise 5.4-2Bruce MaggsThe exercise should be eliminated, because the bug x to the de nition of acycle in an undirected graph on page 88, lines 12 13 obviates it.Page 92, line 10Julie SussmanThe text one path should be changed tohhone simple pathii.Page 115, Exercise 6.3-9Bobby BlumofeThe equation to prove should readhhVar aX = a2Var Xii, nothhVar aX =a2Var xiiBugfixedPage 121, line 3Julie SussmanThe expression ... 1,p n,k ,i has an extra right parenthesis. It shouldbe replaced byhh... 1,p n,k ,iii.Page 124, line 1, and page 125, line 1Tom CormenReplace the inequalities q1, eqe , and e,p1 byhhqi1,eqie , and e,piii.Page 130, line 11David WolfeThe last inequality in bounding E n should be an equality.Bugfixed4Page 131, lines -2 and -1, and page 132, lines 1 4Steve PonzioThe fact" given on page 132, line 2, is false e.g., for n = 210 . The text ismodi ed to read:hh 1,1=pn b2n=blgncc 1,1=pn 2n=lgn,1e, 2n=lgn,1 =pn= O e,lgn = O 1=n :For this argument, we used inequality 2.7 , 1 + xex.Thus, the probability that the longest streak exceedsblgnc=2 is at least1,O 1=n . Since the longest streak has length at least 0, the expected lengthof the longest streak is at least
blgnc=2 1,O 1=n + 0 1=n = lgn :iiBugfixedPage 133 Problem 6-2 , line -8 to -6Julie SussmanThe problem statement now gives a simpler assumption about the input,which guarantees that the input numbers are distinct:hhAssume that thenumbers in A are a random permutation of n distinct numbers.iiIn part a ,the element x is also now speci ed to be randomly chosen from a set ofhhiiidistinct numbers, instead of a set of n distinct numbers.BugfixedPage 140, rst sentence of Section 7.1Dick JohnsonbaughAdd the wordhhnearlyiibefore the phrase complete binary tree .Page 142, Exercise 7.1-3Dick JohnsonbaughChange the exercise to readhhShow that in any subtree of a heap, the root ofthe subtree contains the largest value occurring anywhere in that subtree.ii.Page 142, Exercise 7.1-4Dick JohnsonbaughChange the exercise to readhhWhere in a heap might the smallest elementreside, assuming that all elements are distinct?ii.Page 145, lines 20 22Julie SussmanThe text Our tighter analysis relies on the properties that in an n-elementheap there are at mostdn=2h+1enodes of any height h see Exercise 7.3-3 . is replaced to readhhOur tighter analysis relies on the properties that ann-element heap has heightblgnc see Exercise 7.1-2 and at mostdn=2h+1enodes of any height h see Exercise 7.3-3 .iiBugfixed5Page 147, Exercise 7.3-3Julie SussmanThis exercise should be starred.BugfixedPage 150, Exercise 7.5-1Charles LeisersonSince inserting 3 into the heap is trivial, the exercise is changed to insert thevalue 10 instead.BugfixedPage 159, line 22Tian YuxingThe text asks to you show should be replaced byhhasks you to showii.Page 160, Exercise 8.2-2Julie Sussman and Charles LeisersonChange when the array A is sorted in nonincreasing order. tohhwhen thearray A contains distinct elements and is sorted in decreasing order.ii.Page 170, part c of Problem 8-4Margrit BetkeAppend the sentencehhMaintain the O nlgn expected running time of thealgorithm.iito the end of the problem part.Page 183, Problem 9-1Julie Sussman and Charles LeisersonThere are several minor errors in parts b d . They should be replaced byhhb.Let D T denote the external path length of a tree T; that is, D T isthe sum of the depths of all the leaves of T. Let T be a tree with k 1leaves, and letLTandRTbe the left and right subtrees of T. Show thatD T = D LT + D RT + k.c.Let d k be the minimum value of D T over all decision trees T withk 1 leaves. Show that d k = min1ik,1fd i + d k,i + kg. Hint:Consider a decision tree T with k leaves that achieves the minimum. Let ibe the number of leaves inLTand k,i the number of leaves inRT. d.Prove that for a given value of k 1 and i in the range 1ik,1, thefunction ilgi + k,i lg k,i is minimized at i = k=2. Conclude thatd k = k lgk .iiPages 185, rst paragraphRonald GreenbergTo remove ambiguity and needless later verbiage, the de nition of median"is changed so that the phrase the median" of a set is always well-de ned.This change also causes some small changes to be made on pages 190 and 193.The revised introductory paragraph to the chapter now reads as follows.hhThe ithorder statisticof a set of n elements is the ith smallest element.6For example, theminimumof a set of elements is the rst order statistic i = 1 , and themaximumis the nth order statistic i = n . Amedian,informally, is the halfway point" of the set. When n is odd, the median isunique, occurring at i = n + 1 =2. When n is even, there are two medians,occurring at i = n=2 and i = n=2 + 1. Thus, regardless of the parity of n,medians occur at i =b n + 1 =2c thelower median and i =d n + 1 =2e theupper median . For simplicity in this text, however, we consistentlyuse the phrase the median" to refer to the lower median.iiBugfixedPage 186, last paragraphDick JohnsonbaughThe bound claimed in this paragraph is tightened to 3dn=2e,2, and a sen-tence justifying this is added:hhThe rst pair needs only one comparison toestablish the initial values for the current minimum and current maximum,which accounts for the,2 term.iiAlso, the word necessary is changed tohhsu cientiiin the rst sentence.BugfixedPage 189, line 3 2nd line of equations Julie SussmanThis should readhh=iirather than . .BugfixedPage 190Ron RivestThe description ofSelectis improved to include a description of the basecase n = 1 of the recursion; the following sentence is added:hh If n = 1thenSelectmerely returns its only input value as the ith smallest. iiBugfixedPage 190, step 2 of procedureSelectRonald GreenbergTo maintain consistency with the revised de nition of median see bug reportfor page 185 , and for simplicity in the algorithm, step 2 is revised to read asfollows:hhFind the median of each of thedn=5egroups by insertion sortingthe elements of each group of which there are 5 at most and then pickingthe median from the sorted list of group elements.iiBugfixedPage 191, Exercise 10.3-1Ron RivestTo make the problem a little easier, the last part of the exercise, How aboutgroups of 3? is replaced by the texthhArgue thatSelectwill not run inlinear time if groups of 3 are used.iiBugfixedPage 193, Problems 10-1 a and b Ronald GreenbergCommas should be inserted before the word and" in both parts.BugfixedPage 193, Problem 10-2Ronald GreenbergTo achieve consistency with the revised de nition of median see bug report forpage 185 , the introductory paragraph of this problem was revised as follows:7hhFor n distinct elements x1;x2;...;xnwith positive weights w1;w2;...;wnsuch thatPn
i=1wi= 1, theweighted medianis the element xksatisfyingXxixkwi1
2andXxixkwi1
2 : This is actually theweighted lower median; theweighted upper me-dianwould be de ned similarly. iiBugfixedPage 194, line -5Julie SussmanThe words, linear-time" are added after the phrase worst-case."BugfixedPage 208, Exercise 11.2-8, line 3Julie SussmanThe word index should be changed tohhpointerii.Page 212, 4 lines after the code forFree-ObjectDale RussellThe word three should be replaced byhhtwoii.Page 217, Problem 11-3, line 6Julie SussmanThe word in" has been left out of the sentence. The sentence can be furtherimproved by replacing the phrase much faster than linear time. withhhino n time.ii.Page 217, Problem 11-3John GateleyThe code forCompact-List-Searchdoes not work properly when searchingfor the rst element of the list. The test keyi k in line 3 of the codeshould be replaced byhhkeyikii.Page 228, line 16Margrit BetkeThe text = 2000=3 should be replaced withhh2000=3ii.Page 234, lines 6 7 of rst paragraphDisk JohnsonbaughThe sentence, We would then modify the procedureHash-Searchso that itkeeps on looking when it sees the valuedeleted, whileHash-Insertwouldtreat such a slot as if it were empty so that a new key can be inserted. isreplaced by the text,hhWe would then modify the procedureHash-Insertto treat such a slot as if it were empty so that a new key can be inserted.No modi cation ofHash-Searchis needed, since it will pass overdeletedvalues while searching.iiBugfixed8Page 234, line -11Ronald GreenbergThe text hh k;1 ;h k;2 ;...;h k;m i is replaced by hh k;0 ;h k;1 ;...;h k;m,1 i BugfixedPage 236, lines -9 to -6Ron RivestTo clarify the example, the value of m0is given, so that the sentence nowreads,hhFor example, if k = 123456, m = 701, and m0= 700, we haveh1 k = 80 and h2 k = 257, so the rst probe is to position 80, and thenevery 257th slot modulo m is examined until the key is found or every slotis examined.iiBugfixedPage 238, lines 7 and 6Dick JohnsonbaughAdd the words at most" in two places, so these two lines now read as follows:hhnumber of probes in an unsuccessful search is at most 1= 1,:5 =2. If it is90 percent full, the average number of probes is at most 1= 1,:9 = 10.ii.Page 239, line 4M. VeldhorstThe text number of probes is 1= 1, should be replaced withhhnumberof probes is at most 1= 1, ii.Page 239, Theorem 12.7Dick Johnsonbaugh and Ron RivestThe bound in Theorem 12.7 is not very good for smallish because of theunnecessary term 1= . Note that the bound in the theorem actually decreasesas increases from 0 to . 7! Replace the text 1 ln 11,+ 1 in thestatement of the theorem with the texthh1 ln 11,ii. Replace lines,4 to,2 of the proof withhh1 Hm,Hm,n = 1mXk=m,n+11=k1Zmm,n 1=x dx= 1 ln m= m,n = 1 ln 1= 1, iiThe constants on lines 2 and 1 of page 239 change from 3.387 tohh1.387iiand from 3.670 tohh2.559ii.Page 239, line -3Dick JohnsonbaughAdd the wordshhin a successful searchiiafter the phrase expected numberof probes .9Page 240, Exercise 12.4-4Dick JohnsonbaughReplace the second sentence byhhGive upper bounds on the expected numberof probes in an unsuccessful search and on the expected number of probes ina successful search.iiPage 240, Exercise 12.4-6Ron RivestThis exercise becomes irrelevant once the improvement to Theorem 12.7 notedin the erratum for page 239 has been made. Delete the exercise.Page 242, part d of Problem 12-3Julie SussmanIn order to be usable in part 3 , the statement of part d is modi ed to read:hhConclude that Pk1=n2for kk0= clgn=lglgn.iiBugfixedPage 243, line 3Julie SussmanThe dot product notation in Exercise 12-5 c is replaced by the equivalentsummation notation, for clarity. Also, it now says modm" at the end ofde nition of h:hhha;b x =rXi=0aixi+ b mod m ;iiBugfixedPages 244 and 251 253Ronald GreenbergReferring to the contents" of a node in a binary search tree is ambiguous,since it is unclear whether the contents includes the parent and child pointers.Use explicit reference to satellite data instead, entailing the following changes:On page 244, line,5, change In addition to akeyeld, tohhIn additionto akeyeld and satellite data,ii.On page 251, lines,2 and,3, change and replace the contents of z withthe contents of y. tohhand replace z's key and satellite data with y's keyand satellite data.ii.On page 252, Figure 13.4 caption, change and then replace the contentsof z with the contents of y. tohhand then replace z's key and satellitedata with y's key and satellite data.ii.On page 253, line 16 ofTree-Delete, change the line to readhhCopyy's satellite data, too.ii.On page 253, lines 8 9 of the paragraph following theTree-Deletepseu-docode, change the contents of z are moved from y to z, overwriting theprevious contents tohhy's key and satellite data are moved to z, overwrit-ing the previous key and satellite data.ii.Bugfixed10Page 250, Exercise 13.2-6Julie SussmanReplace Exercise 13.2-6 withhhLet T be a binary search tree whose keys aredistinct, let x be a leaf node, and let y be its parent. Show thatkeyy iseither the smallest key in T larger thankeyx or the largest key in T smallerthankeyx .ii.Page 262, Problem 13-4Mark KantrowitzIn the equation giving the Taylor expansion of f x , change f k x,a inthe numerator tohhf k a ii.BugfixedPage 263, line -2Ronald GreenbergChange to a leaf tohhdown to a leafii.Page 266, caption for Figure 14.2, lines 2 and 5Julie SussmanIn line 2, the text Right-Rotate T;x should be changed tohhRight-Rotate T;y ii, and in line 5, the text Left-Rotate T;y should bechanged tohhLeft-Rotate T;x ii.Page 267, Exercise 14.2-3Julie SussmanThe exercise is already pretty much answered in the text. It should be elimi-nated.Page 267, Exercise 14.2-4, line 3Rosario GennaroThe text a left rotation is performed on node x should be replaced byhharight rotation is performed on node yii.Page 267, Exercise 14.2-5Rosario GennaroThe exercise should be amended to refer to binary search trees, instead of justtrees. The new text ishhShow that any arbitrary n-node binary search treecan be transformed into any other arbitrary n-node binary search tree usingO n rotations. Hint:First show that at most n,1 right rotations su ce totransform the tree into a right-going chain. ii.Page 268, line 15 ofRB-InsertHubert WagenerA right bracket is missing:hhcolorp p xredii.Page 273, line 15 ofRB-DeleteHirendu VaishnavThis comment is ambiguous. Replace it withhhCopy y's satellite data, too.ii.11Page 277, Exercise 14.4-1Ronald GreenbergThe claim is false unless the root was black beforeRB-Deleteexecutes. Theexercise should be rewrittenhhArgue that if a red-black tree has a black rootbeforeRB-Deleteexecutes, then it has a black root afterwards.ii.Page 278, Problem 14-1Julie SussmanThat assumption that there is no parent eld, which is explicit in parts b and c needs to be explicit in the problem text preceding part a . The text Assume that each tree node has the eldskey,left, andrightbut no parenteld. See also Exercise 14.3-6. should be moved from part b to justbefore part a .Page 280, line 5Patricio PobleteChange an insertion to a deletion .Page 286, Exercises 15.1-1 and 15.1-2Julie SussmanChange references to Figure 15.2 tohhFigure 15.1ii.Page 286, Exercise 15.1-7Peter CsaszarChnage to to count tohhto countii.Page 304, line 7Hoon ChoiChange the the parenthesization tohhthe parenthesizationii.page 325, Problem 16-2, lines 5 7George Madrid and Julie SussmanThe number of extra space characters should be constrained to be nonegative,and it should be specifed that ij. Change the sentence beginning If agiven line to readhhIf a given line contains words i through j, where ij,and we leave exactly one space between words, the number of extra spacecharacters at the end of the line is M,j + i,Pj
k=ilk, which must benonnegative so that the words t on the line.ii.Page 326, Problem 16-3, rst line of displayHoon ChoiChange 3cost insert tohh4cost insert ii.Page 327, line 9James ParkChange the reference 106 for the Hu and Shing article to the two refer-ences listed in the erratum for page 992.Bugfixed12Page 339, line 4 of gure 17.4 captionDale RussellThe equation f= 100 is replaced by the correct texthhf= 101ii.BugfixedPage 346, line 20Dean KelleyThe text the addition of x to A should readhhthe addition of e to AiiBugfixedPages 428 429, Figure 21.3Seongbin ParkThe auxiliary array A in Figure 21.3 should run from 0 to 3, not 0 to 4.The Fibonacci heap in part a has n H = 15 nodes. By Exercise 21.2-3,D n H blgn Hc. Array A runs from 0 to D n H andblg15c= 3:BugnotfixedPage 439, line 5 of Chapter notesHal GabowChange Driscoll, Sarnak, Sleator, and Tarjan tohhDriscoll, Gabow, Shrair-man, and TarjaniiBugfixedPage 440, line 2Ron RivestChange is pointed to by x tohhis xii.Pages 443 446, Section 22.2Scot DrysdaleThe linked-list representation of disjoint sets requires that each list also in-clude a pointer to its last element. Otherwise, the append operation does nottake O 1 time.BugnotfixedPage 443, lines 7 and 5Dick JohnsonbaughThere are q,1Unionoperations being executed, so replace q = m,n =bm=2c,1 in line 7 withhhq = m,n+1 =bm=2ciiand replace m = n+q in line 5 withhhm = n + q,1ii.Page 444, Figure 22.3 captionDick JohnsonbaughChange O m2 tohh m2 ii.Page 446, Exercise 22.2-3Julie SussmanChange Argue on the basis of Theorem 22.1 that we can obtain tohhAdaptthe proof of Theorem 22.1 to obtainii.BugfixedPage 450, Exercise 22.3-4Greg ShannonBecause the pseudocode for theUnionoperation callsFind-Set, a sequenceof more than oneUnionoperation must contain some calls toFind-Set13before a call toUnion. Change the two appearances of Union tohhLinkiiin the exercise.Page 457, computation ofN j andP n Paul BeameSince there are at most n nodes, we have N 0 n, which in turn impliesthat N j n=B j for all j0. The constant 3=2 in the computation ofP n can therefore be eliminated.BugfixedPage 467, line 19Julie SussmanThe phrase the the transpose should have the extra the" removed.BugfixedPage 474, line 8Dale RussellThe sentence, Line 14... , which contains only" twice, is modi ed tocontain it only once:hhLine 14 is therefore executed only for vertices withnite d values.iiBugfixedPage 475, line 3Je ShallitReplace lemma withhhtheoremii.BugfixedPage 475, line -6Julie SussmanThe phrase reachable from v should readhhreachable from sii.BugfixedPage 479, line 6 of textJulie SussmanThe phrase lines 1 2 should readhhlines 1 3ii.BugfixedPage 479, line -2Dale RussellThe phrase lines 2 5 should readhhlines 3 6ii.BugfixedPage 480, line 11Haluk KonukThe text parenthesis u ," then should readhhparenthesis u ," theniiBugfixedPage 482, line -8Nils ThommesenTo avoid possible confusion as might occur in trying to solve Problem 23-1 a , the de nition of a back edge is expanded to help remind the readerthat self-loops are not of concern in undirected graphs. The new text reads:hhBack edgesare those edges u;v connecting a vertex u to an ancestorv in a depth- rst tree. Self-loops, which may occur in directed graphs, areconsidered to be back edges.iiBugfixed14Page 487, lines -10 to -8, Exercise 23.4-1Julie SussmanThis exercise should be modi ed to include the following phrase at the end:hhunder the assumption of Exercise 23.3-2ii.BugfixedPage 487, lines -3 to -1, Exercise 23.4-2Dr. M. VeldhorstThis exercise should be deleted, as the rst part is incorrect as stated.BugfixedPage 494, lines -4 to -3. Exercise 23.5-7Eric ConradThe given de nition of semiconnected, A directed graph G = V;E is saidto besemiconnectedif, for any two vertices u;v2V , we have u;v orv;u. can be made clearer, as follows:hhA directed graph G = V;E issaid to besemiconnectedif, for all pairs of vertices u;v2V , we have u;vor v;u.iiBugfixedPage 496, Problem 23-2Je ShallitPart b of the problem is buggy as stated, and should be changed to read asfollows:hhLet v be a nonroot vertex of G. Prove that v is an articulationpoint of G if and only if v has a child s such that there is no back edge froms or any descendant of s to a proper ancestor of v.ii.Page 505, last paragraphJulie SussmanThe sentence At each step, a light edge connecting a vertex in A to a vertexin V,A is added to the tree. does not type check. It should be replaced bythe sentencehhAt each step, a light edge is added to the tree A that connectsA to an isolated vertex of GA= V;A .ii.Page 513, last paragraphHal GabowThe reference to the best min spanning tree algorithm is time O E lg , notO E . The reference is E cient algorithms for nding minimum spanningtrees in undirected and directed graphs", H.N. Gabow, Z. Galil, T.H. Spencerand R.E. Tarjan, Combinatorica 6, 2, 1986, pp. 109-122.BugfixedPage 521, Figure 25.3Julie SussmanThe procedureRelaxtakes three parameters. Add the parameter w to thecalls toRelaxin the gure, and change the rst sentence of the caption from Relaxation of an edge u;v . tohhRelaxation of an edge u;v with weightw u;v = 2.ii.BugfixedPage 522, proof of Corollary 25.6Julie SussmanReplace d v ; thus, so tohhd v , and thusii.15Page 529, Figure 25.6 caption, line 3Julie SussmanChange V,S tohhSii.Page 530, line 17Julie SussmanChange lines 4 8 tohhlines 7 8ii.BugfixedPage 534, Theorem 25.14Julie SussmanIn the last line of the theorem statement, change reachable from S tohhreachable from sii.BugfixedPage 536, line 6Julie SussmanChange Unlike Dijkstra's algorithm, however, we use only O 1 time peredge. tohhUnlike Dijkstra's algorithm, there is no priority queue, and so weuse only O 1 time per edge.ii.BugfixedPage 537, line 6 of Figure 25.8 captionJulie SussmanChange was used as v tohhwas used as uii.BugfixedPage 547, Problem 25-4Julie SussmanAdd the sentencehhWe assume that all vertices are reachable from the source.iito the end of the second paragraph.BugfixedPage 551, line 11Michael ErnstChange and otherwise ijis some predecessor of j on a shortest path from i tohhand otherwise ijis the predecessor of j on some shortest path from iii.BugfixedPage 555, Improving the running timeJulie SussmanAn exercise shold be added at the end of the section to show that the mul-tiplication performed byExtend-Shortest-Pathsis associative and corre-sponds to extending shortest paths.BugnotfixedPage 560, line 6 ofFloyd-WarshallJulie SussmanAdd the keywordhhdoii.BugfixedPage 560, rst line after code forFloyd-WarshallJulie SussmanChange sentence to readhhFigure 26.4 shows the matrices D k computed bythe Floyd-Warshall algorithm for the graph in Figure 26.1.ii.16Page 562, line 10Julie SussmanChange the logical operations_and^ tohhthe logical operations_ logicalOR and^ logical AND ii.BugfixedPage 565, Exercise 26.2-8Ronald GreenbergChange the exercise to read as follows:hhSuppose that the transitive closureof a directed acyclic graph can be computed in f jVj;jEj time, where fis a monotonically increasing function ofjVjandjEj. Show that the timeto compute the transitive closure G= V;E of a general directed graphG = V;E is f jVj;jEj + O V + E .ii.Page 572, line 1Tom CormenReplace the last line of the display with the following:hh= p1 1 c c c c c c p2 :iiPage 585, line 1
refer page:-------http://www.officesoon.com/doc/173430-errata-1-2-for-introduction-to-algorithms-by-cormen-leiserson-and
Click Here To Download...