算法设计与分析基础课后习题答案solu2.pdf

《算法设计与分析基础课后习题答案solu2.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、Thisfilecontainstheexercises,hints,andsolutionsforChapter2ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms,”2ndedition,byA.Levitin.Theproblemsthatmightbechallengingforatleastsomestudentsaremarkedby
;thosethatmightbedifficultforamajorityofstudentsarema

2、rkedby.Exercises2.11.Foreachofthefollowingalgorithms,indicate(i)anaturalsizemetricforitsinputs;(ii)itsbasicoperation;(iii)whetherthebasicoperationcountcanbedifferentforinputsofthesamesize:a.computingthesumofnnumbersb.computingn!c.findingthelargestelementina

3、listofnnumbersd.Euclid’salgorithme.sieveofEratosthenesf.pen-and-pencilalgorithmformultiplyingtwon-digitdecimalintegers2.a.Considerthedefinition-basedalgorithmforaddingtwon-by-nmatri-ces.Whatisitsbasicoperation?Howmanytimesisitperformedasafunctionofthematrix

4、ordern?Asafunctionofthetotalnumberofelementsintheinputmatrices?b.Answerthesamequestionsforthedefinition-basedalgorithmformatrixmultiplication.3.Consideravariationofsequentialsearchthatscansalisttoreturnthenumberofoccurrencesofagivensearchkeyinthelist.Willit

5、sefficiencydifferfromtheefficiencyofclassicsequentialsearch?4.a.GloveselectionThereare22glovesinadrawer:5pairsofredgloves,4pairsofyellow,and2pairsofgreen.Youselecttheglovesinthedarkandcancheckthemonlyafteraselectionhasbeenmade.Whatisthesmallestnumberofglovesyou

6、needtoselecttohaveatleastonematchingpairinthebestcase?intheworstcase?(after[Mos01],#18)b.MissingsocksImaginethatafterwashing5distinctpairsofsocks,youdiscoverthattwosocksaremissing.Ofcourse,youwouldliketohavethelargestnumberofcompletepairsremaining.Thus,you

7、areleftwith4completepairsinthebest-casescenarioandwith3completepairsintheworstcase.Assumingthattheprobabilityofdisappearanceforeach1ofthe10socksisthesame,findtheprobabilityofthebest-casescenario;theprobabilityoftheworst-casescenario;thenumberofpairsyoushoul

8、dexpectintheaveragecase.(after[Mos01],#48)5.a.
Proveformula(2.1)forthenumberofbitsinthebinaryrepresentationofapositiveinteger.b.Whatwouldbetheanalogousformulaforthenumberofdecimaldigits?c.Explainwhy,withinthe