Errata List for Algorithm Manual Skiena

Please download to get full document.

View again

of 13
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Documents

Published:

Views: 3 | Pages: 13

Extension: DOC | Download: 0

Share
Related documents
Description
Errata List for Algorithm Manual Skiena
Tags
Transcript
  Errata List for The Algorithm Design Manual (2nd Edition) by Steven SkienaLast addition Mar!h 2# 2$%&on'trivial errata are denoted ith a ()* + in!lude a se,arate se!tionat the end for !ommentaries '' additional suggestions - !larifi!ationssuggested by readers hi!h are not really errata*............................................................................/resh Errata (no ith Se!tion des!ri,tions for e'0ook readers)1age # ,aragra,h 3# line 4 (Se!tion $*$) ***before returning at the rightmost ,oint* should be ***before returning at the leftmost ,oint* 1age 25# /igure 25 (Se!tion $*) Adding !ommas beteen the digits ould makeit !learer1age 2# line % (Se!tion $*) '' 6e,la!ing 72#3#58 by 72#5#%8 might offera more dire!t !onne!tion to the reasoning underlying the !a,tion offigure $*$* (hi!h is u,dated in figure $*$$)() 1age 3# fifth and si9th e9,ressions (Se!tion 2*2) !an be !larified3n:2 ' $n ;  is not <=mega(n:3) be!ause be!ause for any >,ositive? ! + !hoose 3n:2 ' $n ;  @ !n:3 for any n  3-!;3B3n:2 ' $n ;  . <=mega(n) be!ause + !hoose ! . $ and n @ 3n:2 ' $n ;  hen n  35B1age 55# line 3 (Se!tion 2*%*3) for ,. Skiena* the ,eriod should be moved outside the Cuotes*1age 5# line '$ (Se!tion 2*) this definition is the same !ould be this eCuivalen!e is the same () 1age %%# line '$ (Se!tion 2*4*$) a d'dimensional hy,er!ube of length n:($-d) on ea!h side has volume d* should be a d'dimensional hy,er!ube of length n:($-d) on ea!h side has volume n* 1age 2# ,roblem 2'3 (Se!tion 2*$) ' the out,ut statement is im,ro,erly indented*1age # line '$ (Se!tion 3*$) The F<lg nFs in the formula should be rittenas F<l!eil <lg n <r!eilF*() 1age # line '$ (Se!tion 3*$) This analysis !an be looked at in a differentay# hi!h yields a sim,ler and more ,re!ise (though asym,toti!ally identi!al)anser* +f e sum the number of !o,y o,erations as they are made# e getSum from (i.$) to (log n) of n-(2:i)instead ofSum from (i.$) to (log n)'$ of >in-(2:(i'$))?hi!h is !ounting the number of elements hi!h get !o,ied i times# times i*Ghen n.2:H im,lied in the analysis# both summations are asym,toti!ally the  same# a,,roa!hing 2n* () 1age # deleteIlist-,rede!essorIlist() subroutines '' A eird thing !anha,,en if you insert multi,le elements ith the same key* +f you insert avalue# then insert a different one# finally inserting the same value as thefirst insertion again (i*e* $# 2# $)# hen you try to delete the head nodeJsJ$J value the deleteIlist() subroutine ill lo!ate the in!orre!t ,rede!essornode and basi!ally break the ,rogram by setting the ,rede!essorJs Jne9tJ valueto ,oint to itJs self and delete the rong node*This is hy it is bad to insert to distinguishable elements ith the the samekey in a data stru!ture*() 1age 5# table '' Singly'linked deletion !an be done in !onstant time by !o,ying the ne9t value to over'rite the key of the deleted node# then ,oint to the ne9t ne9t element and free hat as srcinally the node after it*fun!tion delete (list elementToDelete) !o,y elementToDelete'ne9tJs DATA into elementToDeleteJs DATA set elementToDelete'ne9t to ,oint to elementToDelete'ne9t'ne9t delete elementToDelete'ne9t1age %# line  of the ,aragra,h under the table (Se!tion 3*%) ' the minimum entry have should be the minimum entry e have *1age %# table# Delete'min ro and 0alan!ed tree !olumn (Se!tion 3*%) '' in fa!t there is a ay to do Delete'Min in =($) time# but it is a little more !om,li!ated than the method + des!ribe*() 1age $%# line $ (Se!tion 5*$) ,olygon of smallest area should beeither !onve9 ,olygon of smallest area or ,olygon of smallest ,erimeter 1age $$3# line '$ (Se!tion 5*3*3) 6eturn ty,e should be itemIty,e# not int*() 1age $$5 line '5 (Se!tion 5*3*3) As im,lemented in the book# my hea,sortis not in',la!e# be!ause it !reates the ,riority Cueue in C# not s*1age $$# ,art 2 of solution to the Sto, and Think se!tion  the last lineshould read sin!e the to, k levels have F2:k ' $F elements 1age $2$# line '2 (Se!tion 5*%) ' 2:k ,airs sorted list should be 2:k ,airsof sorted lists *1age $24# line $4 (Se!tion 5*) Ge !ould sort sorting should be Ge !ould sort 1age $3$# ,aragra,h 3# line 3 (Se!tion 5*) ' getting the the data should be getting the data *1age $3$# Line ' (Se!tion 5*) The !orre!t link to the sorting ben!hmark ishtt,--sortben!hmark*org-*() 1age $5 line '$ (Se!tion %*$) Ge !onfess that all im,lementations in thisbook are designed to ork =&LK on sim,le gra,hs*  1age $%2# lines 3 and 5 of the table (Se!tion %*2) small and big should be s,arse and dense*1age $$# line 3 (Se!tion %*%) ' su!h ,rinting should be su!h as ,rinting *() 1age $5# line 5 (Se!tion %*) '' this im,lementation sets ,ro!essed>v?.T6E at the to, of the hile loo,# here as the ,seudo!ode does so at the bottom*1resuambly the bottom is the right !hoi!e# although it generally should not matter*1age $5# line  (Se!tion %*) ' there is a right ,arenthesis missing at the end of this line* 1age $# in the se!ond bulleted ,aragra,h (Se!tion %*)# the s,elling des!endents# hi!h a,,ears ti!e# should be des!endants* () 1age $# line 3 (Se!tion %*4) ' !omment should be is the ,arent of the verte9 the root of the D/S tree *() 1age $# se!ond and third bullet ,oints (Se!tion %*$) ' the ord !om,leted in both ,aragra,hs should be ,ro!essed *1age $3# line 3 (Se!tion %*$) ' edges that ,oint verti!es should be edgesthat ,oint to verti!es *() 1age $# line 5 of ,roblem %'2 (Se!tion %*$$) ' is a subset of  should be is a subset  *1age $4%# line '% (Se!tion *$) ' out of ne tree verte9 should be out of ea!h ne tree verte9 *1age $4# last line# last ord (Se!tion *$*2) ' ,suedo!ode ' ,seudo!ode 1age $44# line '3 (Se!tion *$*3) ' The height *** stay the same should be The heights *** stay the same 1age 2# line $ of unionsIsets (Se!tion *$*3) ' the return ty,e should not be int# be!ause the fun!tion returns nothing*1age 2$# line 3#  (first o!!uren!e) and  (Se!tion *$*3) ' height'2 and height'3 should be height 2 and height 3 res,e!tively*1age 22# line $5 (Se!tion *$*5) ' the highest degree node *** is small should be the highest degree of a node *** is small *1age 25# line  (Se!tion *2) ' the right arm to visits should be the right arm visits *() 1age 2$# /igure *$3 (Se!tion *%*2) The gra,h shoing the residual flo6(N) has a dire!ted edge from the !enter node to the to, !enter node (itheight 3)# hi!h should be undire!ted*1age 23$# se!tion *$# se!ond ,aragra,h ea!h one ,ossible !onfiguration .. ea!h ,ossible !onfiguration   () 1age 232# ba!ktra!k !ode (Se!tion *$) ' the !all to unmakeImove() should be before the if (finished) !he!k# otherise the finished solution ill be unmade*1age 232# line ' (Se!tion *$)  elements of ve!tor a from a !om,lete solution ' elements of ve!tor a form a !om,lete solution *() 1age 23# line  of !onstru!tI!andidates (Se!tion *$*3) should be for (i.B i@kB i;;) inIsol>a>i?? . T6EB *() 1age 25# line ' of !onstru!tI!andidates should be for (i.$B i@.D+ME&S+=&B i;;) *1age 25# line '$ (Se!tion *%) ' a!!ess should be assess *1age 2%# line '$ (Se!tion *%*$) ' e9a!tly ho unordered ,airs should be e9a!tly ho many unordered ,airs *() 1age 2%# formula (Se!tion *%*3) The e9ternal negative sign on the eCuation reverses the !ondition*+t should be e:((O(Si) ' O(S>i;$?))-kT) . r() 1age 2%# line $3 (Se!tion *%*3) should be transition(s#t#i2#i$)B1age 23# /ig* *$2 (Se!tion *) 1refi9 NA and suffi9 AA should yield NAAA not NAAN*1age 2# line 2# in !omment (Se!tion *$*5) ' !om,uter should be !om,ute *1age 2# line  !ould be for (i.2B i@.nB i;;) * /or i . $# b!>$?>? and b!>$?>$? have already been evaluated in the lines above and the inner loo, ill not even run*() 1age 24$# table (Se!tion *3) ' the Length lIi indi!es should be $ 2 2 3 $ 5 5 % % *1age 243# line $ of first bullet ,oint (Se!tion *5) ' to, run i to run bottom H should be to, run i to bottom run H *1age 245# line '$$ ' +# ould volunteer should be + ould volunteer *() 1age 24# line $ belo the figure (Se!tion *%) ' ,>H? ' ,>k? should be ,>H? ' ,>i'$? *() 1age 3# under the se!ond min in the first formula ' i.k should be k.i *1age 32# line ' (Se!tion **$) ' e get are stu!k should be e get stu!k *1age 33# line 22 (Se!tion **2) ' solution is entire should be solution is the entire *() 1age 3$%# line 2 of ,roblem '23 (Se!tion *$) ' o,timal orst !ase !ost should be o,timal e9,e!ted !ost * =therise the ,robabilities are irrelevant at least if they are all larger than *
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks