版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
ComputerAlgorithms,ThirdEdition,
SolutionstoSelectedExercises
SaraBaase
AllenVanGelder
February25,2000
INTRODUCTION
ThismanualcontainssolutionsfortheselectedexercisesinComputerAlgorithms:IntroductiontoDesignandAnaly
sis,thirdedition,bySaraBaaseandAllenVanGelder.
Solutionsmanualsareintendedprimarilyforinstructors,butitisafactthatinstructorssometimesputcopiesin
campuslibrariesorontheirwebpagesforusebystudents.Forinstructorswhoprefertohavestudentsworkon
problemswithoutaccesstosolutions,wehavechosennottoincludealltheexercisesfromthetextinthismanual.The
includedexercisesarelistedinthetableofcontents.Roughlyeveryotherexerciseissolved.
Someofthesolutionswerewrittenspecificallyforthismanual;othersareadaptedfromsolutionssetshandedout
tostudentsinclasseswetaught(writtenbyourselves,teachingassistants,andstudents).
Thusthereissomeinconsistencyinthestyleandamountofdetailinthesolutions.Somemayseemtobeaddressed
toinstructorsandsometostudents.Wedecidednottochangetheseinconsistencies,inpartbecausethemanualwillbe
readbyinstructorsandstudents.Insomecasesthereismoredetail,explanation,orjustificationthanastudentmight
beexpectedtosupplyonahomeworkassignment.
Manyofthesolutionsusethesamepseudocodeconventionsusedinthetext,suchas:
1.Blockdelimiters"and")“)areomitted.Blockboundariesareindicatedbyindentation.
2.Thekeywordstaticisomittedfrommethod(functionandprocedure)declarations.Allmethodsdeclaredin
thesolutionsarestatic.
3.Classnamequalifiersareomittedfrommethod(functionandprocedure)calls.Forexample,x=cons(z/
x)mightbewrittenwhentheJavasyntaxrequiresx=IntList.cons(z,x).
4.Keywordstocontrolvisibility,public,private,andprotected,areomitted.
5.Mathematicalrelationaloperators“区,“"•二,"and"""areusuallywritten,insteadoftheirkeyboardversions.
Relationaloperatorsareusedontypeswherethemeaningisclear,suchasString,eventhoughthiswouldbe
invalidsyntaxinJava.
WethankChuckSandersforwritingmostofthesolutionsforChapter2andforcontributingmanysolutionsin
Chapter14.WethankLuoHong,agraduatestudentatUCSantaCruz,forassistingwithseveralsolutionsinChapters
9,10,11,and13.
Inafewcasesthesolutionsgiveninthismanualareaffectedbycorrectionsandclarificationstothetext.These
casesareindicatedatthebeginningofeachaffectedsolution.Theup-to-dateinformationoncorrectionsandclarifica
tions,alongwithothersupplementarymaterialsforstudents,canbefoundattheseInternetsites:
/cseng/authors/baase
/faculty/baase
/personnel/facuity/avg.html
©Copyright2000SaraBaaseandAllenVanGelder.Allrightsreserved.
Permissionisgrantedforcollegeanduniversityinstructorstomakeareasonablenumberofcopies,freeofcharge,
asneededtoplanandadministertheircourses.Instructorsareexpectedtoexercisereasonableprecautionsagainst
further,unauthorizedcopies,whetheronpaper,electronic,orothermedia.
PermissionisalsograntedforAddison-Wesley-Longmaneditorial,marketing,andsalesstafftoprovidecopies
freeofchargetoinstructorsandprospectiveinstructors,andtomakecopiesfortheirownuse.
Othercopies,whetherpaper,electronic,orothermedia,areprohibitedwithoutpriorwrittenconsentoftheauthors.
ListofSolvedExercises
1AnalyzingAlgorithmsandProblems:PrinciplesandExamples
1.1..11.1331.2851.447
1.2..21.1541.3161.467
1.4..21.1841.3361.477
1.6..21.2041.3561.487
1.8..31.2241.3761.508
1.10......31.2341.396
1.12......31.2551.427
DataAbstractionandBasicDataStructures9
2.2..92.892.1412
2.4..92.10112.1613
2.6..92.12112.1814
RecursionandInduction17
3.2173.6173.1018
3.4173.8183.1218
Sorting19
4.2194.21214.37244.5326
4.4194.23214.40244.5527
4.6194.25224.42244.5727
4.9..194.26224.44254.5928
4.11......194.27234.45254.6128
4.13......204.29234.46254.6329
4.15......204.31234.48254.6529
4.17......204.34244.4925
4.19......214.35244.5126
SelectionandAdversaryArguments31
5.2..315.8335.14345.2135
5.4..325.10345.16345.2236
5.6..325.12345.19355.2437
DynamicSetsandSearching39
6.1..396.12416.24476.3649
6.2..396.14436.26476.3749
6.4..406.16456.28476.4050
6.6..406.18456.3047
6.8..416.20456.3248
6.10......416.22466.3449
ivListofSolvedExercises
7GraphsandGraphTraversals
745372874059
7.151
z653z3o57749
7.35115
8533257
7.45174359
72054z3457
7.6517456O
72273558
7.8517476O
72454z3759
7.1052I
7275773959z496
7.1252
8GraphOptimizationProblemsandGreedyAlgorithms63
8.1638.8648.16......658.24......67
648.18......65
8.3638.108.26......67
8.5638.12648.20......65
8.7648.14648.22......678.27......67
9TransitiveClosure,All-PairsShortestPaths69
9.2699.7719.12......729.18....,.72
9.4709.8719.14......72
9.6719.10719.16......72
10DynamicProgramming73
10.27310.97310.16.....7510.23.....78
10.47310.107410.18.....7610.26.....79
10.57310.127510.19.....77
10.77310.147510.21.....78
11StringMatching81
11.18111.88411.17.....8411.25.....86
11.28111.108411.19.....85
11.48111.128411.21.....85
11.68311.158411.23.....85
12PolynomialsandMatrices87
12.28712.88712.14.....88
12.48712.108712.16.....88
12.68712.128812.17.....88
13NP-CompleteProblems89
13.28913.149213.26.....9313.37.....96
13.48913.169213.28.....9313.39.....96
13.69113.189213.30...9413.42.....98
13.89113.209313.32.....9413.44.....99
13.109113.219313.34.....9613.47.....99
13.129113.239313.35.....9613.49.....99
ListofSolvedExercises
13.51.....9913.54.....10013.57.....10013.61.....101
13.53.....10013.55.....10013.59.....101
14ParallelAlgorithms103
14.2......10314.10.....10414.18.....10514.25.....106
14.4...一.10314.11.....10414.19.....10614.27.....107
14.5...一.10314.13.....10414.20.....10614.29.....107
14.7......10414.14.....10514.22.....10614.30.....108
14.8......10414.16.....10514.24.....10614.32.....108
viListofSolvedExercises
Chapter1
AnalyzingAlgorithmsandProblems:PrinciplesandExamples
Section1.2:JavaasanAlgorithmLanguage
1.1
Itiscorrectforinstancefieldswhosetypeisaninnerclasstobedeclaredbeforethatinnerclass(asinFigure1.2in
thetext)orafter(ashere).AppendixA.7givesanalternativetospellingoutalltheinstancefieldsinthecopymethods
(functions).
classPersonal
f
publicstaticclassName
f
StringfirstName;
StringmiddleName;
StringlastName;
publicstaticNamecopy(Namen)
f
Namen2;
n2.firstName=n.firstName;
n2.middleName=n.middleName;
n2.lastName=n.lastName;
returnn2;
publicstaticclassAddress
f
Stringstreet;
Stringcity;
Stringstate;
publicstaticAddresscopy(Addressa);/*similartoName.copy()*/|
publicstaticclassPhoneNumber
r
intareaCode;
intprefix;
intnumber;
publicstaticPhoneNumbercopy(PhoneNumbern);/*similartoName.copy()*/%
r
Namename;
Addressaddress;
PhoneNumberphone;
StringeMail;
publicstaticPersonalcopy(Personalp);
r
Personalp2;
p2.name=Name.copy();
p2.address=Address.copy(p.address);
p2.phone=PhoneNumber.copy(p.phone);
p2.eMail=p.eMail;
returnp2;
2Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples
Section1.3:MathematicalBackground
1.2
For0<n,wehave
in-1\_(n-1)!_-1]!(〃一自
\k)~丽~1~而三电!
(ft_1、_|n-11!_
\k1/Ik1)!|nk[!k\\n
Addthemgiving:
ln-l!!(n|fn\
k\\n^k\!yk;
For0「〃「kweusethefactthat|-0whenevera-'b.(Thereisnowaytochoosemoreelementsthantherearein
thewholeset.)Thus|晨)-0inallthesecases.IandI*areboth0,confirmingtheequation.Ifn-k,
I;}|andIareboth1,againconfirmingtheequation.(Weneedthefactthat0!11when〃一攵一1.)
L4
Itsufficestoshow:
Iogcxlog/,C-log^x.
Considerbraisedtoeachside.
bleflside.(•^log^cjlog.-x.logx
-ccx
^rightside-^log^.v_(
Soleftside=rightside.
1.6
Letx-pg!n1CLThesolutionisbasedonthefactthat2X1-'/H1•:2X.
x=0;
twoToTheX=1;
while(twoToTheX<n+1)
x+=1;
twoToTheX*=2;
returnx;
Thevaluescomputedbythisprocedureforsmallnandtheapproximatevaluesoflg[n+-1)are:
nX1g:n*1)
000.0
111.0
221.6
322.0
432.3
532.6
632.8
733.0
843.2
943.3
Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples3
1.8
Pr\SandT)Pr(SlPr^Tl
PrlS|T)一Pi\S\
-Pr\T{-Pr\T[-
Thesecondequationissimilar.
1.10
WeknowABandD':'C.Bydirectcounting:
PrlA<CandA-andD《Ci5/245
Pr\ACC
Pr\A<BandD<"Cl67246
Pr\ACDCCandAeBl3.'2431
eD4《BandOe。-——"__
Pr\ACBandD<C|?24"62
PrlAeBCCandQe。3/2431
Pr\BCCABandDCC)一—■一
P八AeBandDCCl6/2462
1/24_
PrB-DA《BandDdO」
Pr\ABandD-'C\6/24-6
1.12
Weassumethattheprobabilityofeachcoinbeingchosenis1/3,thattheprobabilitythatitshows“heads“afterbeing
flippedis1/2andthattheprobabilitythatitshows"tails“afterbeingflippedis1/2.Callthecoins/A,B,andC.Define
theelementaryevents,eachhavingprobability1/6,asfollows.
AHAischosenandflippedandcomesout“heads”.
ATAischosenandflippedandcomesout“tails”.
BHBischosenandflippedandcomesout“heads”.
BTBischosenandflippedandcomesout“tails”.
CHCischosenandflippedandcomesout“heads”
CTCischosenandflippedandcomesout“tails".
a)BHandCHcauseamajoritytobe“heads”,sotheprobabilityis1/3.
b)Noeventcausesamajoritytobe“heads",sotheprobabilityis0.
c)AH,BH,CHandCTcauseamajoritytobe"heads”,sotheprobabilityis2/3.
1.13
Theentryinrowi,columnjistheprobabilitythatD,willbeatD;.
221812
36-3636
122216
--
363636
1212422
183636-
--
3620
76
22
--
36
NotethatD\beats。2,。2beatsD3,D3beats£)4,andD4beatsD].
4Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples
1.153.
Theproofisbyinductiononn,theupperlimitofthesum.Thebasecaseis0.Then£3i2-0,and2",•J~=0.
Sotheequationholdsforthebasecase.For-0,assumetheformulaholdsforn1.
n
£?_层h?二1;工3〃二1二山4n
丁£6
・1
2/-6〃2-6〃―24-3〃2-6〃4-3—〃-1
2/-3〃2―n6〃22/73—3〃2—〃
-一-
666
1.18
ConsideranytworealswCz.Weneedtoshowthatf\vv)f(z\;thatis,f[z[f[vv),0.Sincef\x\isdifferentiable,
itiscontinuous.WecallupontheMeanValueTheorem(sometimescalledtheTheoremoftheMean),whichcanbe
foundinanycollegecalculustext.Bythistheoremthereissomepointy,suchthatw''yz,forwhich
[Zwj
Bythehypothesisofthelemma,/1yl>0.Also,Izvv)>0.Therefore,f(z)f\w\>0.
1.20
Letlabbreviatethephrase,4tislogicallyequivalentto”.WeusetheidentityrrA-Aasneeded.
糊4M>B[才M.lx^\A\xl,所疝(byEq.1.24)
=IHVBlxjj(byEq.1.21)
=力I(byDeMorgan'slaw,Eq.1.23).
Section1.4:AnalyzingAlgorithmsandProblems
1.22
Thetotalnumberofoperationsintheworstcaseis472-2;theyare:
ComparisonsinvolvingK:n
Comparisonsinvolvingindex:nII
Additions:n
Assignmentstoindex:nI1
1.23
a)
if(a<b)
if(b<c)
median=b;
elseif(a<c)
median=c;
else
median=a;
elseif(a<c)
median=a;
elseif(b<c)
median=c;
else
median=b;
Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples5
b)Disthesetofpermutationsofthreeitems.
c)Worstcase=3;average=21.
d)Threecomparisonsareneededintheworstcasebecauseknowingthemedianofthreenumbersrequiresknowing
thecompleteorderingofthenumbers.
1.25
Solution1.Pairuptheentriesandfindthelargerofeachpair;ifnisodd,oneelementisnotexamined|n'?\
comparisons).ThenfindthemaximumamongthelargerelementsusingAlgorithm1.3,includingtheunexamined
elementifnisodd(J112]-1comparisons).Thisisthelargestentryintheset.Thenfindtheminimumamong
thesmallerelementsusingtheappropriatemodificationofAlgorithm1.3,againincludingtheunexaminedelementif
nisodd(|l/iI1j/2]1comparisons).Thisisthesmallestentryintheset.Whethernisoddoreven,thetotalis
|-1:.Thefollowingalgorithminterleavesthethreesteps.
/**Precondition:n>0.*
if(odd(n))
min=E[n-1];
max=E[n-1];
elseif(E[n-2]<E[n-1])
min=E[n-2];
max=E[n-1];
else
max=E[n-2];
min=E[n-1];
for(i=0;i<=n-3;i=i+2)
if(E[i]<E[i+1])
if(E[i]<min)min=E[i];
if(E[i+1]>max)max=E[i+1];
else
if(E[i]>max)max=E[i];
if(E[i+1]<min)min=E[i+1];
Solution2.WhenweassignthisproblemaftercoveringDivideandConquersortingalgorithmsinChapter4,many
studentsgivethefollowingDivideandConquersolution.(Butmostofthemcannotshowformallythatitdoesroughly
3〃,2comparisons.)
Ifthereareatmosttwoentriesintheset,comparethemtofindthesmallerandlarger.Otherwise,breakthesetin
halves,andrecursivelyfindthesmallestandlargestineachhalf.Thencomparethelargestkeysfromeachhalftofind
thelargestoverall,andcomparethesmallestkeysfromeachhalftofindthesmallestoverall.
AnalysisofSolution2requiresmaterialintroducedinChapter3.Therecuirenceequationforthisprocedure,
assumingnisapowerof2,is
Winj=1for/?=2
W\n[-2WI-2forn>2
Therecursiontreecanbeevaluateddirectly.Itisimportantthatthenonrecursivecostsinthen'lleavesofthistree
are1each.Thenonrecursivecostsinthe〃,2-1internalnodesare2each.Thisleadstothetotalof3〃,2—2forthe
specialcasethatnisapowerof2.Morecarefulanalysisverifiestheresult「3〃’2-2"foralln.Theresultcanalsobe
provenbyinduction.
Section1.5:ClassifyingFunctionsbyTheirAsymptoticGrowthRates
1.28
lrim-PI川-r--i.im+等+…4券谭)一仅>0.
n
6Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples
1.31
Thesolutionherecombinesparts(a)and(b).Thefunctionsonthesamelineareofthesameasymptoticorder.
IglgH
lg〃・In
、所
n
/£
n2-Ign
n3
〃一九3+7〃5
2«-12/:
n\
1.33
Let/-n.Forsimplicityweshowacounter-exampleinwhichanonmonotonicfunctionisused.Considerthe
functionh\nI:
nforoddn
(1forevenn
Clearlyh\n:「O\/In::.But加加?。sohn\「0f\:.Therefore,h\n\「Of\-0/1A/:I.Itremainsto
showthath\n\iZo\Butthisfollowsbythefactthath\nl-1foroddintegers.
Withmoredifficultyh\canbeconstructedtobemonotonic.Forall%1,leth\beconstantontheintervalkk•'
1
n''i\k¥IFr-1)andleth\—内onthisinterval.Thuswhen〃—/,人(小'/]-1,butwhenn—(k-1)^'1,
h\n[ff\riy-//(l〃:11),whichtendsto0asngetslarge.
1.35
Property1:SupposefC01gl.Therearec0and〃osuchthatforn>〃o,f\n\<2cglny.Thenforn>〃o,
gi川(n[.Theotherdirectionisprovedsimilarly.
Property2:fC0ig)meansfr0\g厂。ByProperty1,T门0\力,sog「0i.
Property3:Lemma1.9ofthetextgivestransitivity.Property2givessymmetry.Sinceforanyf.fC0(/),wehave
reflexivity.
Property4:Weshow0(f•gl-。maxif.gll.Theotherdirectionissimilar.Leth厂0\f•g{.Therearec>0and
nosuchthatforn>n()th\n{•'clfgHThenforn->“0,h\〃广-2cmaxi八gln\.
1.37
ln2?,w,n2
WewilluseL'H6pital'sRule,soweneedtodifferentiate2〃.Observethat2"-ie:一e.Letc=ln2X0.7.
Thederivativeof-'isen,so,usingthechainrule,wefindthatthederivativeof2"isc2n.Now,usingL'H6pitai'sRule
repeatedly,
lim空q.=lim普=。
lim——lim---2n
〃,82〃n•«<»c2"nkooc28法2〃
sincekisconstant.
1.39
.J1foroddn.nforoddn
f(gln\―
/Jn|-<Inforevennforevenn
Therearealsoexamplesusingcontinuousfunctionsonthereals,aswellasexamplesusingmonotonicfunctions.
Chapter1AnalyzingAlgorithmsandProblems:PrinciplesandExamples7
Section1.6:SearchinganOrderedArray
1.42
Therevisedprocedureis:
intbinarysearch(int[]Ezintfirst,intlast,intK)
1.if(last<first)
2.index=-1;
3.elseif(last==first)
4.if(K==E[first])
5.index=first;
6.else
7.index=-1;
8.else
9.intmid=(first+last)/2;
10.if(KE[mid])
11.index=binarysearch(E,first,mid,K);
12.else
13.index=binarysearch(E,mid+1,last,K);
14.returnindex;
ComparedtoAlgorithm1.4(BinarySearch)inthetext,thisalgorithmcombinesthetestsoflines5and7intoonetest
online10,andtheleftsubrangeisincreasedfrommidItomid,becausemidmightcontainthekeybeingsearched
for.Anextrabasecaseisneededinlines3-7,whichtestsforexactequalitywhentherangeshrinkstoasingleentry.
Actually,ifwecanassumethepreconditionfirst•二last,thenlines1-2canbedispensedwith.Thisprocedure
propagatesthatpre
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 400TD脱酚棉籽浓缩蛋白及精深加工生产线项目可行性研究报告模板-立项备案
- 事业编计算机岗大数据分析情景应变面试题库及解析
- 2026年婚姻家庭咨询师一级(高级技师)理论知识冲刺模拟考试卷及答案(三)
- 2026年环境影响评价工程师资格考试环境影响评价技术导则与标准冲刺模拟考试卷及答案(七)
- 物流仓储管理人员货物分拣优化方案
- 物流仓储货物检测与质量控制指南
- 医院药房药品盘点操作流程手册
- 确定2026年会议安排通知函(7篇)
- 合作项目进度延期申请函(5篇范文)
- 确认合同签署流程操作规范通知函8篇范文
- 浙江省衢州、丽水、湖州2026年11月三地市高三教学质量检测化学试卷(含答案)
- 中医医院卒中中心脑出血救治流程
- 测量工施工安全作业指导书培训课件
- 2026新教材语文 16.金字塔第1课时【教学课件】2026-2027学年部编版五年级语文上册
- 2026年国企财务管理岗招聘考试专业卷(含财务报表分析)押题卷及答案
- 氧、氮、氩气管道安装施工方案
- G3111混凝土结构加固构造图集施工技术交底与验收检查表模板
- 学校食堂营养配餐培训
- 【初中地理】世界的海陆分布+课件-2025-2026学年七年级地理上学期(湘教版2024)
- 第四版危重病医学课件-第二十九章+术后肝功能不全
- 青春托起中国梦课件
评论
0/150
提交评论