算法导论

算法导论教师⼿册

Instructor’sManual

toAccompany

IntroductiontoAlgorithmsThirdEdition

son

CliffordStein

TheMITPress

Cambridge,MassachuttsLondon,England

Instructor’sManualtoAccompanyIntroductiontoAlgorithms,ThirdEdition

,son,,andCliffordStein

htsrerved.

Nopartofthispublicationmaybereproducedordistributedinanyformorbyanymeans,orstoredinadatabaorretrieval

system,withoutthepriorwrittenconntofTheMITPress,including,butnotlimitedto,networkorotherelectronicstorageor

transmission,orbroadcastfordistancelearning.

Contents

RevisionHistoryR-1

PrefaceP-1

Chapter2:GettingStarted

LectureNotes2-1

Solutions2-17

Chapter3:GrowthofFunctions

LectureNotes3-1

Solutions3-7

Chapter4:Divide-and-Conquer

LectureNotes4-1

Solutions4-17

Chapter5:ProbabilisticAnalysisandRandomizedAlgorithms

LectureNotes5-1

Solutions5-9

Chapter6:Heapsort

LectureNotes6-1

Solutions6-10

Chapter7:Quicksort

LectureNotes7-1

Solutions7-9

Chapter8:SortinginLinearTime

LectureNotes8-1

Solutions8-10

Chapter9:MediansandOrderStatistics

LectureNotes9-1

Solutions9-10

Chapter11:HashTables

LectureNotes11-1

Solutions11-16

Chapter12:BinarySearchTrees

LectureNotes12-1

Solutions12-15

Chapter13:Red-BlackTrees

LectureNotes13-1

Solutions13-13

Chapter14:AugmentingDataStructures

LectureNotes14-1

Solutions14-9

ivContents

Chapter15:DynamicProgramming

LectureNotes15-1

Solutions15-21

Chapter16:GreedyAlgorithms

LectureNotes16-1

Solutions16-9

Chapter17:AmortizedAnalysis

LectureNotes17-1

Solutions17-14

Chapter21:DataStructuresforDisjointSets

LectureNotes21-1

Solutions21-6

Chapter22:ElementaryGraphAlgorithms

LectureNotes22-1

Solutions22-13

Chapter23:MinimumSpanningTrees

LectureNotes23-1

Solutions23-8

Chapter24:Single-SourceShortestPaths

LectureNotes24-1

Solutions24-13

Chapter25:All-PairsShortestPaths

LectureNotes25-1

Solutions25-9

Chapter26:MaximumFlow

LectureNotes26-1

Solutions26-12

Chapter27:MultithreadedAlgorithms

Solutions27-1

IndexI-1

RevisionHistory

Revisionsarelistedbydateratherthanbeingnumbered.

nalternativesolutiontoExerci2.3-7,courtesyofViktorKorsunand

teda

minorerrorintheChapter15notesintherecurrenceforT.n/fortherecursive

CUT-RO

tedan

/?ow

iesofallpudocodeproceduresareindentedslightly.

tedanerrorinthesolutiontoProblem2-4(c),andremovedunnecessarycodeinthesolutionto

Problem2-4(d).Addedamissing

dthe

pudocodeforHEAP-EXTRACT-MAXonpage6-8andMAX-HEAP-INSERT

onpage6-9toassumethattheparameternispasdbyreference.

dthesolutionstoExercis22.2-3and22.3-4becautheexercischanged.

tedaminorerrorinthesolutiontoExerci4.3-7.

nalternativesolutiontoExerci6.3-3,courtesyofEyalMashiach.

olutionstoExercis16.3-1,26.1-1,26.1-3,26.1-7,

26.2-1,26.2-8,26.2-9,26.2-12,26.2-13,-

lcorrectionstothe

solutiontoExerci16.4-3,hangestothe

solutionstoExercis24.3-3and24.4-7andProblem24-1.

lrelea.

Preface

Thisdocumentisaninstructor’smanualtoaccompanyIntroductiontoAlgorithms,

ThirdEdition,,son,,and

htalso?nd

someofthematerialhereintobeufulforaCS2-stylecourindatastructures.

Unliketheinstructor’smanualforthe?rsteditionofthetext—whichwasorganized

aroundtheundergraduatealgorithmscourtaughtbyCharlesLeirsonatMIT

inSpring1991—butliketheinstructor’smanualforthecondedition,wehave

chontoorganizethemanualforthethirdeditionaccordingtochaptersofthe

,formostchapterswehaveprovidedatoflecturenotesandatof

ganizationallows

youtodecidehowtobestuthematerialinthemanualinyourowncour.

Wehavenotincludedlecturenotesandsolutionsforeverychapter,norhavewe

includedsolutionsforeveryexerciandproblemwithinthechaptersthatwehave

thatChapter1istoonontechnicaltoincludehere,andChap-

ter10consistsofbackgroundmaterialthatoftenfallsoutsidealgorithmsanddata-

alsoomittedthechaptersthatarenotcoveredinthe

coursthatweteach:Chapters18–20and27–35,aswellasAppendicesA–D;

retwo

reasonsthatwehavenotincludedsolutionstoallexercisandproblemsinthe

,writingupallthesolutionswouldtakealongtime,and

wefeltitmoreimportanttoreleathismanualinastimelyafashionaspossible.

Second,ifweweretoincludeallsolutions,thismanualwouldbemuchlongerthan

thetextitlf.

WehavenumberedthepagesinthismanualusingtheformatCC-PP,whereCC

isachapternumberofthetextandPPisthepagenumberwithinthatchapter’s

umbersrestartfrom1atthebeginningofeach

chapter’ethisformofpagenumberingsothatifweadd

orchangesolutionstoexercisandproblems,theonlypageswhonumberingis

er,ifweaddmaterial

forcurrentlyuncoveredchapters,thenumbersoftheexistingpageswillremain

unchanged.

Thelecturenotes

Thelecturenotesarebadonthreesources:

P-2Preface

Somearefromthe?rst-editionmanual;theycorrespondtoCharlesLeirson’slecturesinMIT’sundergraduatealgorithms

cour,6.046.

SomearefromTomCormen’slecturesinDartmouthCollege’sundergraduatealgorithmscour,CS25.

Somearewrittenjustforthismanual.

Youwill?ndthatthelecturenotesaremoreinformalthanthetext,asisappro-

places,wehavesimpli?edthematerialfor

ctionsofthe

text—usuallystarred—areomittedfromthelecturenotes.(Wehaveincludedlec-

turenotesforonestarredction:12.4,onrandomlybuiltbinaryarchtrees,

whichwecoverinanoptionalCS25lecture.)

Inveralplacesinthelecturenotes,wehaveincluded“asides”totheinstruc-

desaretypetinaslantedfontandareenclodinsquarebrack-

ets.[Hereisanaside.]Someoftheasidessuggestleavingcertainmaterialonthe

board,reprojectingaprenta-

tionratherthanwritingonablackboardorwhiteboard,youmightwanttoreplicate

slidescontainingthismaterialsothatyoucaneasilyreprithemlaterinthelec-

ture.

Wehavechonnottoindicatehowlongittakestocovermaterial,asthetimenec-

essarytocoveratopicdependsontheinstructor,thestudents,theclassschedule,

andothervariables.

Therearetwodifferencesinhowwewritepudocodeinthelecturenotesandthe

text:

?ndtheminconvenienttonumberwhenwritingpudocodeontheboard.

d,ange

makesthepudocode

moreconci,aswellasmatchingbetterwiththedescriptionofwhatitdoes.

Wehavealsominimizedtheuofshadingin?gureswithinlecturenotes,since

drawinga?gurewithshadingonablackboardorwhiteboardisdif?cult.

Thesolutions

ewritten

abitmoreformallythanthelecturenotes,thoughabitlessformallythanthetext.

Wedonotnumberlinesofpudocode,butwedouthelengthattribute(onthe

assumptionthatyouwillwantyourstudentstowritepudocodeasitappearsin

thetext).

Asofthethirdedition,wehavepubliclypostedafewsolutionsonthebook’sweb-

olutionsalsoappearinthismanual,withthenotation“Thissolution

isalsopostedpublicly”ofpublicly

postedsolutionsmightincreaovertime,soweencourageyoutocheckwhether

aparticularsolutionispostedonthewebsitebeforeyouassignanexercior

problemtoyourstudents.

PrefaceP-3Theindexlistsalltheexercisandproblemsforwhichthismanualprovidessolu-

tions,alongwiththenumberofthepageonwhicheachsolutionstarts.

,wearelessreluctanttoushadingin?gureswithin

solutions,sincethe?guresaremorelikelytobereproducedthantobedrawnonaboard.

Source?les

Forveralreasons,weareunabletopublishortransmitsource?ogizeforthisinconvenience.

Youcanutheclrscode3epackageforLATEX2"?ndthis

packageat/doc//thc/clrscode/.Thatsitealso

retoutheclrscode3epackage,nottheclrscodepackage;clrscodeisforthecond

editionofthebook.

Reportingerrorsandsuggestions

Undoubtedly,instructorswill?reporterrorsbyndingemailtoclrs-manual-

bugs@/doc/.

Ifyouhaveasuggestionforanimprovementtothismanual,pleafeelfreetosubmititviaemailtoclrs-manual-

suggestions@/doc/.

Asusual,ifyou?ndanerrorinthetextitlf,pleaverifythatithasnotalreadybeenpostedontheerratawebpagebefore

utheMITPresswebsiteforthe

text,/doc//algorithms/,tolocatetheerratawebpage

andtosubmitanerrorreport.

Wethankyouinadvanceforyourassistanceincorrectingerrorsinboththismanualandthetext.

Howweproducedthismanual

LikethethirdeditionofIntroductiontoAlgorithms,thismanualwasproducedinLATEX2".WeudtheTimesfontwith

lthreeeditionsofthetextbook,wecompiledtheindexusing

Windex,theillustrationsusingMacDrawPro,1withsomeofthemathematical

expressionsinillustrationslaidinwiththepsfragpackageforLATEX2".WecreatedthePDF?lesforthismanualona

MacBookProrunningOS10.5.

Acknowledgments

Thismanualborrowsheavilyfromthemanualsforthe?ussman,P.P.A.,wrotethe?rst-edition

idsuchasuperbjobonthe

P-4Preface

rst-editionmanual,ndingnumerourrorsintherst-editiontextintheprocess,

thatwewerethrilledtohaveherrveastechnicalcopyeditorforboththecond

sLeirsonalsoputinlargeamountsoftime

workingwithJulieonthe?rst-editionmanual.

ThemanualforthecondeditionwaswrittenbyTomCormen,ClaraLee,and

ndEricawereundergraduatecomputersciencemajorsatDart-

mouthatthetime,andtheydidasuperbjob.

TheotherthreeIntroductiontoAlgorithmsauthors—CharlesLeirson,Ron

Rivest,andCliffStein—providedhelpfulcommentsandsuggestionsforsolutions

thesolutionsaremodi?cationsofthowritten

overtheyearsbyteachingassistantsforalgorithmscoursatMITandDartmouth.

Atthispoint,wedonotknowwhichTAswrotewhichsolutions,andsowesimply

lofthesolutionstonewexercisandproblems

inthethirdeditionwerewrittenbySharathGururajofColumbiaUniversity;we

thankSharathforhis?nework.

WealsothanktheMITPressandoureditor,AdaBrunstein,formoraland?-

gubovandWayneCrippsprovidedcomputersupportat

Dartmouth.

Hanover,NewHampshire

August2009