算法设计与分析基础课后习题答案solu3

算法设计与分析基础(影印版)Anany Levitin 清华大学出版社 课后习题答案

This lecontainstheexercises,hints,andsolutionsforChapter3ofthebook”IntroductiontotheDesignandAnalysisofAlgorithms,”2ndedition,by

A.Levitin.Theproblemsthatmightbechallengingforatleastsomestudentsaremarkedby ;thosethatmightbedi cultforamajorityofstudentsaremarkedby .

Exercises3.1

1.a.Giveanexampleofanalgorithmthatshouldnotbeconsideredanapplicationofthebrute-forceapproach.

b.Giveanexampleofaproblemthatcannotbesolvedbyabrute-forcealgorithm.

2.a.Whatisthee ciencyofthebrute-forcealgorithmforcomputinganasafunctionofn?Asafunctionofthenumberofbitsinthebinaryrepresentationofn?

b.Ifyouaretocomputeanmodmwherea>1andnisalargepositiveinteger,howwouldyoucircumventtheproblemofaverylargemagnitudeofan?

3.ForeachofthealgorithmsinProblems4,5,and6ofExercises2.3,tellwhetherornotthealgorithmisbasedonthebrute-forceapproach.

4.a.Designabrute-forcealgorithmforcomputingthevalueofapolynomial

p(x)=anxn+an 1xn 1+...+a1x+a0

atagivenpointx0anddetermineitsworst-casee ciencyclass.

b.IfthealgorithmyoudesignedisinΘ(n2),designalinearalgorithmforthisproblem.

c.Isitpossibletodesignanalgorithmwithabetterthanlineare ciencyforthisproblem?

5.SortthelistE,X,A,M,P,L,Einalphabeticalorderbyselectionsort.

6.Isselectionsortstable?(Thede nitionofastablesortingalgorithmwasgiveninSection1.3.)

7.IsitpossibletoimplementselectionsortforlinkedlistswiththesameΘ(n2)e ciencyasthearrayversion?

8.SortthelistE,X,A,M,P,L,Einalphabeticalorderbybubblesort.

9.a.Provethatifbubblesortmakesnoexchangesonitspassthroughalist,thelistissortedandthealgorithmcanbestopped.

1

算法设计与分析基础课后习题答案solu3相关文档

最新文档

返回顶部