https://ebookmass.com/product/data-structures-and-algorithmanalysis-in-java-3rd-ed-edition-mark-allen-weiss/
Instant digital products (PDF, ePub, MOBI) ready for you
Download now and discover formats that fit your needs...
Data Structures and Algorithm Analysis in C++ 4th Edition, (Ebook PDF)
https://ebookmass.com/product/data-structures-and-algorithm-analysisin-c-4th-edition-ebook-pdf/
ebookmass.com
Starting Out with Java: From Control Structures through Data Structures 3rd Edition, (Ebook PDF)
https://ebookmass.com/product/starting-out-with-java-from-controlstructures-through-data-structures-3rd-edition-ebook-pdf/
ebookmass.com
eTextbook 978-0134285436 Java Foundations: Introduction to Program Design and Data Structures (4th Edition)
https://ebookmass.com/product/etextbook-978-0134285436-javafoundations-introduction-to-program-design-and-data-structures-4thedition/
ebookmass.com
Fundamentals of Building Construction: Materials and Methods 6th Edition – Ebook PDF Version
https://ebookmass.com/product/fundamentals-of-building-constructionmaterials-and-methods-6th-edition-ebook-pdf-version/
ebookmass.com
The International Legal Order's Colour Line: Racism, Racial Discrimination, and the Making of International Law
William A. Schabas
https://ebookmass.com/product/the-international-legal-orders-colourline-racism-racial-discrimination-and-the-making-of-international-lawwilliam-a-schabas/
ebookmass.com
Fundamentals of Management 10th Edition Ricky Griffin
https://ebookmass.com/product/fundamentals-of-management-10th-editionricky-griffin/
ebookmass.com
Joy to the Wolves Terry Spear
https://ebookmass.com/product/joy-to-the-wolves-terry-spear-3/
ebookmass.com
Atkins’ Physical Chemistry 12th Edition Peter Atkins
https://ebookmass.com/product/atkins-physical-chemistry-12th-editionpeter-atkins/
ebookmass.com
A Heart of Hope: A Lesbian/Sapphic Surgeons Romance (Hearts Medical Romance Series Book 2) Emily Hayes
https://ebookmass.com/product/a-heart-of-hope-a-lesbian-sapphicsurgeons-romance-hearts-medical-romance-series-book-2-emily-hayes/
ebookmass.com
Empire Asunder Box Set: Books 1-3 Plus Sourcebook Michael Jason Brandt
https://ebookmass.com/product/empire-asunder-box-set-books-1-3-plussourcebook-michael-jason-brandt/
ebookmass.com
This page intentionally left blank
Data Structures and Algorithm Analysis in JavaTM This page intentionally left blank
Data Structures and Algorithm Analysis in Java Mark Alle n Weis s Florida International University
BostonColumbusIndianapolisNewYorkSanFranciscoUpperSaddleRiver AmsterdamCapeTownDubaiLondonMadridMilanMunichParisMontrealToronto DelhiMexicoCitySaoPauloSydneyHongKongSeoulSingaporeTaipeiTokyo
PEARSON
EditorialDirector:MarciaHortonProjectManager:PatBrown Editor-in-Chief:MichaelHirschManufacturingBuyer:PatBrown EditorialAssistant:EmmaSniderArtDirector:JayneConte DirectorofMarketing:PatriceJonesCoverDesigner:BruceKenselaar MarketingManager:YezanAlayanCoverPhoto: c De-KayDreamstime.com
MarketingCoordinator:KathrynFerrantiMediaEditor:DanielSandin DirectorofProduction:VinceO’BrienFull-ServiceProjectManagement:Integra ManagingEditor:JeffHolcombComposition:Integra ProductionProjectManager:KaylaPrinter/Binder:CourierWestford Smith-TarboxCoverPrinter:Lehigh-PhoenixColor/Hagerstown TextFont:Berkeley-Book
Copyright c 2012,2007,1999PearsonEducation,Inc., publishingasAddison-Wesley.Allrightsreserved. PrintedintheUnitedStatesofAmerica.ThispublicationisprotectedbyCopyright,andpermissionshould beobtainedfromthepublisherpriortoanyprohibitedreproduction,storageinaretrievalsystem,ortransmissioninanyformorbyanymeans,electronic,mechanical,photocopying,recording,orlikewise.Toobtain permission(s)tousematerialfromthiswork,pleasesubmitawrittenrequesttoPearsonEducation,Inc., PermissionsDepartment,OneLakeStreet,UpperSaddleRiver,NewJersey07458,oryoumayfaxyour requestto201-236-3290.
Manyofthedesignationsbymanufacturersandsellerstodistinguishtheirproductsareclaimedastrademarks.Wherethosedesignationsappearinthisbook,andthepublisherwasawareofatrademarkclaim,the designationshavebeenprintedininitialcapsorallcaps.
LibraryofCongressCataloging-in-PublicationData
Weiss,MarkAllen.
DatastructuresandalgorithmanalysisinJava/MarkAllenWeiss.–3rded. p.cm.
ISBN-13:978-0-13-257627-7(alk.paper)
ISBN-10:0-13-257627-9(alk.paper)
1.Java(Computerprogramlanguage)2.Datastructures(Computerscience)
3.Computeralgorithms.I.Title.
QA76.73.J38W4482012
005.1–dc232011035536
1514131211—CRW—10987654321
ISBN10:0-13-257627-9
ISBN13:9780-13-257627-7
Totheloveofmylife,Jill. This page intentionally left blank
Prefacexvii
Chapter1Introduction1 1.1What’stheBookAbout?1
1.2MathematicsReview2
1.2.1Exponents3
1.2.2Logarithms3
1.2.3Series4
1.2.4ModularArithmetic5
1.2.5The P Word6
1.3ABriefIntroductiontoRecursion8
1.4ImplementingGenericComponentsPre-Java512
1.4.1Using Object forGenericity13
1.4.2WrappersforPrimitiveTypes14
1.4.3UsingInterfaceTypesforGenericity14
1.4.4CompatibilityofArrayTypes16
1.5ImplementingGenericComponentsUsingJava5Generics16
1.5.1SimpleGenericClassesandInterfaces17
1.5.2Autoboxing/Unboxing18
1.5.3TheDiamondOperator18
1.5.4WildcardswithBounds19
1.5.5GenericStaticMethods20
1.5.6TypeBounds21
1.5.7TypeErasure22
1.5.8RestrictionsonGenerics23
1.6FunctionObjects24
Summary26
Exercises26 References28
Chapter2AlgorithmAnalysis29 2.1MathematicalBackground29
2.2Model32
2.3WhattoAnalyze33
2.4RunningTimeCalculations35
2.4.1ASimpleExample36
2.4.2GeneralRules36
2.4.3SolutionsfortheMaximumSubsequenceSumProblem39
2.4.4LogarithmsintheRunningTime45
2.4.5AGrainofSalt49 Summary49
Exercises50 References55
Chapter3Lists,Stacks,andQueues57 3.1AbstractDataTypes(ADTs)57
3.2TheListADT58
3.2.1SimpleArrayImplementationofLists58
3.2.2SimpleLinkedLists59
3.3ListsintheJavaCollectionsAPI61
3.3.1 Collection Interface61
3.3.2 Iterator s61
3.3.3The List Interface, ArrayList,and LinkedList 63
3.3.4Example:Using remove ona LinkedList 65
3.3.5 ListIterators67
3.4ImplementationofArrayList67
3.4.1TheBasicClass68
3.4.2TheIteratorandJavaNestedandInnerClasses71
3.5ImplementationofLinkedList75
3.6TheStackADT82
3.6.1StackModel82
3.6.2ImplementationofStacks83
3.6.3Applications84
3.7TheQueueADT92
3.7.1QueueModel92
3.7.2ArrayImplementationofQueues92
3.7.3ApplicationsofQueues95 Summary96 Exercises96
Chapter4Trees101 4.1Preliminaries101
4.1.1ImplementationofTrees102
4.1.2TreeTraversalswithanApplication103
4.2BinaryTrees107
4.2.1Implementation108
4.2.2AnExample:ExpressionTrees109
4.3TheSearchTreeADT—BinarySearchTrees112
4.3.1 contains 113
4.3.2 findMin and findMax 115
4.3.3 insert 116
4.3.4 remove 118
4.3.5Average-CaseAnalysis120
4.4AVLTrees123
4.4.1SingleRotation125
4.4.2DoubleRotation128
4.5SplayTrees137
4.5.1ASimpleIdea(ThatDoesNotWork)137
4.5.2Splaying139
4.6TreeTraversals(Revisited)145
4.7B-Trees147
4.8SetsandMapsintheStandardLibrary152
4.8.1Sets152
4.8.2Maps153
4.8.3Implementationof TreeSet and TreeMap 153
4.8.4AnExampleThatUsesSeveralMaps154 Summary160
Exercises160 References167
Chapter5Hashing171 5.1GeneralIdea171
5.2HashFunction172
5.3SeparateChaining174
5.4HashTablesWithoutLinkedLists179
5.4.1LinearProbing179
5.4.2QuadraticProbing181
5.4.3DoubleHashing183
5.5Rehashing188
5.6HashTablesintheStandardLibrary189
5.7HashTableswithWorst-Case O(1)Access192
5.7.1PerfectHashing193
5.7.2CuckooHashing195
5.7.3HopscotchHashing205
5.8UniversalHashing211
5.9ExtendibleHashing214 Summary217 Exercises218 References222
Chapter6PriorityQueues(Heaps)225
6.1Model225
6.2SimpleImplementations226
6.3BinaryHeap226
6.3.1StructureProperty227
6.3.2Heap-OrderProperty229
6.3.3BasicHeapOperations229
6.3.4OtherHeapOperations234
6.4ApplicationsofPriorityQueues238
6.4.1TheSelectionProblem238
6.4.2EventSimulation239
6.5 d-Heaps240
6.6LeftistHeaps241
6.6.1LeftistHeapProperty241
6.6.2LeftistHeapOperations242
6.7SkewHeaps249
6.8BinomialQueues252
6.8.1BinomialQueueStructure252
6.8.2BinomialQueueOperations253
6.8.3ImplementationofBinomialQueues256
6.9PriorityQueuesintheStandardLibrary261 Summary261 Exercises263 References267
Chapter7Sorting271 7.1Preliminaries271
7.2InsertionSort272
7.2.1TheAlgorithm272
7.2.2AnalysisofInsertionSort272
7.3ALowerBoundforSimpleSortingAlgorithms273
7.4Shellsort274
7.4.1Worst-CaseAnalysisofShellsort276
7.5Heapsort278
7.5.1AnalysisofHeapsort279
7.6Mergesort282
7.6.1AnalysisofMergesort284
7.7Quicksort288
7.7.1PickingthePivot290
7.7.2PartitioningStrategy292
7.7.3SmallArrays294
7.7.4ActualQuicksortRoutines294
7.7.5AnalysisofQuicksort297
7.7.6ALinear-Expected-TimeAlgorithmforSelection300
7.8AGeneralLowerBoundforSorting302
7.8.1DecisionTrees302
7.9Decision-TreeLowerBoundsforSelectionProblems304
7.10AdversaryLowerBounds307
7.11Linear-TimeSorts:BucketSortandRadixSort310
7.12ExternalSorting315
7.12.1WhyWeNeedNewAlgorithms316
7.12.2ModelforExternalSorting316
7.12.3TheSimpleAlgorithm316
7.12.4MultiwayMerge317
7.12.5PolyphaseMerge318
7.12.6ReplacementSelection319 Summary321
Exercises321 References327
Chapter8TheDisjointSetClass331
8.1EquivalenceRelations331
8.2TheDynamicEquivalenceProblem332
8.3BasicDataStructure333
8.4SmartUnionAlgorithms337
8.5PathCompression340
8.6WorstCaseforUnion-by-RankandPathCompression341
8.6.1SlowlyGrowingFunctions342
8.6.2AnAnalysisByRecursiveDecomposition343
8.6.3An O( M log* N )Bound350
8.6.4An O( M α (M,N ))Bound350
8.7AnApplication352
Summary355 Exercises355 References357
Chapter9GraphAlgorithms359
9.1Definitions359
9.1.1RepresentationofGraphs360
9.2TopologicalSort362
9.3Shortest-PathAlgorithms366
9.3.1UnweightedShortestPaths367
9.3.2Dijkstra’sAlgorithm372
9.3.3GraphswithNegativeEdgeCosts380
9.3.4AcyclicGraphs380
9.3.5All-PairsShortestPath384
9.3.6Shortest-PathExample384
9.4NetworkFlowProblems386
9.4.1ASimpleMaximum-FlowAlgorithm388
9.5MinimumSpanningTree393
9.5.1Prim’sAlgorithm394
9.5.2Kruskal’sAlgorithm397
9.6ApplicationsofDepth-FirstSearch399
9.6.1UndirectedGraphs400
9.6.2Biconnectivity402
9.6.3EulerCircuits405
9.6.4DirectedGraphs409
9.6.5FindingStrongComponents411
9.7IntroductiontoNP-Completeness412
9.7.1Easyvs.Hard413
9.7.2TheClassNP414
9.7.3NP-CompleteProblems415 Summary417 Exercises417 References425
Chapter10AlgorithmDesign Techniques429 10.1GreedyAlgorithms429
10.1.1ASimpleSchedulingProblem430
10.1.2HuffmanCodes433
10.1.3ApproximateBinPacking439
10.2DivideandConquer448
10.2.1RunningTimeofDivide-and-ConquerAlgorithms449
10.2.2Closest-PointsProblem451
10.2.3TheSelectionProblem455
10.2.4TheoreticalImprovementsforArithmeticProblems458 10.3DynamicProgramming462
10.3.1UsingaTableInsteadofRecursion463
10.3.2OrderingMatrixMultiplications466
10.3.3OptimalBinarySearchTree469
10.3.4All-PairsShortestPath472
10.4RandomizedAlgorithms474
10.4.1RandomNumberGenerators476
10.4.2SkipLists480
10.4.3PrimalityTesting483
10.5BacktrackingAlgorithms486
10.5.1TheTurnpikeReconstructionProblem487
10.5.2Games490
Summary499
Exercises499 References508
Chapter11AmortizedAnalysis513
11.1AnUnrelatedPuzzle514
11.2BinomialQueues514
11.3SkewHeaps519
11.4FibonacciHeaps522
11.4.1CuttingNodesinLeftistHeaps522
11.4.2LazyMergingforBinomialQueues525
11.4.3TheFibonacciHeapOperations528
11.4.4ProofoftheTimeBound529
11.5SplayTrees531
Summary536
Exercises536
References538
Chapter12AdvancedDataStructures andImplementation541
12.1Top-DownSplayTrees541
12.2Red-BlackTrees549
12.2.1Bottom-UpInsertion549
12.2.2Top-DownRed-BlackTrees551
12.2.3Top-DownDeletion556
12.3Treaps558
12.4SuffixArraysandSuffixTrees560
12.4.1SuffixArrays561
12.4.2SuffixTrees564
12.4.3Linear-TimeConstructionofSuffixArraysandSuffixTrees567
12.5 k-dTrees578
12.6PairingHeaps583
Summary588
Exercises590 References594
Index599
This page intentionally left blank
PREFACE Purpose/Goals ThisnewJavaeditiondescribes datastructures, methodsoforganizinglargeamountsof data,and algorithmanalysis, theestimationoftherunningtimeofalgorithms.Ascomputers becomefasterandfaster,theneedforprogramsthatcanhandlelargeamountsofinput becomesmoreacute.Paradoxically,thisrequiresmorecarefulattentiontoefficiency,since inefficienciesinprogramsbecomemostobviouswheninputsizesarelarge.Byanalyzing analgorithmbeforeitisactuallycoded,studentscandecideifaparticularsolutionwillbe feasible.Forexample,inthistextstudentslookatspecificproblemsandseehowcareful implementationscanreducethetimeconstraintforlargeamountsofdatafromcenturies tolessthanasecond.Therefore,noalgorithmordatastructureispresentedwithoutan explanationofitsrunningtime.Insomecases,minutedetailsthataffecttherunningtime oftheimplementationareexplored.
Onceasolutionmethodisdetermined,aprogrammuststillbewritten.Ascomputers havebecomemorepowerful,theproblemstheymustsolvehavebecomelargerandmore complex,requiringdevelopmentofmoreintricateprograms.Thegoalofthistextistoteach studentsgoodprogrammingandalgorithmanalysisskillssimultaneouslysothattheycan developsuchprogramswiththemaximumamountofefficiency.
Thisbookissuitableforeitheranadvanceddatastructures(CS7)courseorafirst-year graduatecourseinalgorithmanalysis.Studentsshouldhavesomeknowledgeofintermediateprogramming,includingsuchtopicsasobject-basedprogrammingandrecursion,and somebackgroundindiscretemath.
SummaryoftheMostSignificantChangesintheThirdEdition Thethirdeditionincorporatesnumerousbugfixes,andmanypartsofthebookhave undergonerevisiontoincreasetheclarityofpresentation.Inaddition,
Chapter4includesimplementationoftheAVLtreedeletionalgorithm—atopicoften requestedbyreaders.
Chapter5hasbeenextensivelyrevisedandenlargedandnowcontainsmaterialontwo neweralgorithms:cuckoohashingandhopscotchhashing.Additionally,anewsection onuniversalhashinghasbeenadded.
Chapter7nowcontainsmaterialonradixsort,andanewsectiononlowerbound proofshasbeenadded.
Chapter8usesthenewunion/findanalysisbySeidelandSharir,andshowsthe O( Mα (M, N ))boundinsteadoftheweaker O( M log∗ N )boundinprioreditions.
Chapter12addsmaterialonsuffixtreesandsuffixarrays,includingthelinear-time suffixarrayconstructionalgorithmbyKarkkainenandSanders(withimplementation). ThesectionscoveringdeterministicskiplistsandAA-treeshavebeenremoved.
Throughoutthetext,thecodehasbeenupdatedtousethediamondoperatorfrom Java7.
Approach Althoughthematerialinthistextislargelylanguageindependent,programmingrequires theuseofaspecificlanguage.Asthetitleimplies,wehavechosenJavaforthisbook.
JavaisoftenexaminedincomparisonwithC++.Javaoffersmanybenefits,andprogrammersoftenviewJavaasasafer,moreportable,andeasier-to-uselanguagethanC++. Assuch,itmakesafinecorelanguagefordiscussingandimplementingfundamentaldata structures.OtherimportantpartsofJava,suchasthreadsanditsGUI,althoughimportant, arenotneededinthistextandthusarenotdiscussed.
Completeversionsofthedatastructures,inbothJavaandC++,areavailableon theInternet.Weusesimilarcodingconventionstomaketheparallelsbetweenthetwo languagesmoreevident.
Overview Chapter1containsreviewmaterialondiscretemathandrecursion.Ibelievetheonlyway tobecomfortablewithrecursionistoseegoodusesoverandover.Therefore,recursion isprevalentinthistext,withexamplesineverychapterexceptChapter5.Chapter1also presentsmaterialthatservesasareviewofinheritanceinJava.Includedisadiscussionof Javagenerics.
Chapter2dealswithalgorithmanalysis.Thischapterexplainsasymptoticanalysisand itsmajorweaknesses.Manyexamplesareprovided,includinganin-depthexplanationof logarithmicrunningtime.Simplerecursiveprogramsareanalyzedbyintuitivelyconverting themintoiterativeprograms.Morecomplicateddivide-and-conquerprogramsareintroduced,butsomeoftheanalysis(solvingrecurrencerelations)isimplicitlydelayeduntil Chapter7,whereitisperformedindetail.
Chapter3coverslists,stacks,andqueues.Thischapterhasbeensignificantlyrevised fromprioreditions.ItnowincludesadiscussionoftheCollectionsAPI ArrayList and LinkedList classes,anditprovidesimplementationsofasignificantsubsetofthe collectionsAPI ArrayList and LinkedList classes.
Chapter4coverstrees,withanemphasisonsearchtrees,includingexternalsearch trees(B-trees).TheUNIXfilesystemandexpressiontreesareusedasexamples.AVLtrees andsplaytreesareintroduced.Morecarefultreatmentofsearchtreeimplementationdetails isfoundinChapter12.Additionalcoverageoftrees,suchasfilecompressionandgame trees,isdeferreduntilChapter10.Datastructuresforanexternalmediumareconsidered asthefinaltopicinseveralchapters.NewtothiseditionisadiscussionoftheCollections API TreeSet and TreeMap classes,includingasignificantexamplethatillustratestheuseof threeseparatemapstoefficientlysolveaproblem.
Chapter5discusseshashtables,includingtheclassicalgorithmssuchasseparatechainingandlinearandquadraticprobing,aswellasseveralneweralgorithms, namelycuckoohashingandhopscotchhashing.Universalhashingisalsodiscussed,and extendiblehashingiscoveredattheendofthechapter.
Chapter6isaboutpriorityqueues.Binaryheapsarecovered,andthereisadditional materialonsomeofthetheoreticallyinterestingimplementationsofpriorityqueues.The FibonacciheapisdiscussedinChapter11,andthepairingheapisdiscussedinChapter12.
Chapter7coverssorting.Itisveryspecificwithrespecttocodingdetailsandanalysis. Alltheimportantgeneral-purposesortingalgorithmsarecoveredandcompared.Four algorithmsareanalyzedindetail:insertionsort,Shellsort,heapsort,andquicksort.Newto thiseditionisradixsortandlowerboundproofsforselection-relatedproblems.External sortingiscoveredattheendofthechapter.
Chapter8discussesthedisjointsetalgorithmwithproofoftherunningtime.Theanalysisisnew.ThisisashortandspecificchapterthatcanbeskippedifKruskal’salgorithm isnotdiscussed.
Chapter9coversgraphalgorithms.Algorithmsongraphsareinteresting,notonly becausetheyfrequentlyoccurinpractice,butalsobecausetheirrunningtimeissoheavily dependentontheproperuseofdatastructures.Virtuallyallthestandardalgorithmsare presentedalongwithappropriatedatastructures,pseudocode,andanalysisofrunning time.Toplacetheseproblemsinapropercontext,ashortdiscussiononcomplexitytheory (including NP-completenessandundecidability)isprovided.
Chapter10coversalgorithmdesignbyexaminingcommonproblem-solvingtechniques.Thischapterisheavilyfortifiedwithexamples.Pseudocodeisusedintheselater chapterssothatthestudent’sappreciationofanexamplealgorithmisnotobscuredby implementationdetails.
Chapter11dealswithamortizedanalysis.ThreedatastructuresfromChapters4and6 andtheFibonacciheap,introducedinthischapter,areanalyzed.
Chapter12coverssearchtreealgorithms,thesuffixtreeandarray,the k-dtree,and thepairingheap.Thischapterdepartsfromtherestofthetextbyprovidingcompleteand carefulimplementationsforthesearchtreesandpairingheap.Thematerialisstructuredso thattheinstructorcanintegratesectionsintodiscussionsfromotherchapters.Forexample,thetop-downred-blacktreeinChapter12canbediscussedalongwithAVLtrees (inChapter4).
Chapters1–9provideenoughmaterialformostone-semesterdatastructurescourses. Iftimepermits,thenChapter10canbecovered.Agraduatecourseonalgorithmanalysis couldcoverChapters7–11.TheadvanceddatastructuresanalyzedinChapter11caneasily bereferredtointheearlierchapters.Thediscussionof NP-completenessinChapter9is fartoobrieftobeusedinsuchacourse.Youmightfinditusefultouseanadditionalwork on NP-completenesstoaugmentthistext.
Exercises Exercises,providedattheendofeachchapter,matchtheorderinwhichmaterialispresented.Thelastexercisesmayaddressthechapterasawholeratherthanaspecificsection. Difficultexercisesaremarkedwithanasterisk,andmorechallengingexerciseshavetwo asterisks.
References Referencesareplacedattheendofeachchapter.Generallythereferenceseitherarehistorical,representingtheoriginalsourceofthematerial,ortheyrepresentextensionsand improvementstotheresultsgiveninthetext.Somereferencesrepresentsolutionsto exercises.
Supplements Thefollowingsupplementsareavailabletoallreadersat www.pearsonhighered.com/cssupport:
Sourcecodeforexampleprograms
Inaddition,thefollowingmaterialisavailableonlytoqualifiedinstructorsatPearson’s InstructorResourceCenter(www.pearsonhighered.com/irc).VisittheIRCorcontactyour campusPearsonrepresentativeforaccess.
Solutionstoselectedexercises
Figuresfromthebook
Acknowledgments Many,manypeoplehavehelpedmeinthepreparationofbooksinthisseries.Someare listedinotherversionsofthebook;thankstoall.
Asusual,thewritingprocesswasmadeeasierbytheprofessionalsatPearson.I’dliketo thankmyeditor,MichaelHirsch,andproductioneditor,PatBrown.I’dalsoliketothank AbinayaRajendranandherteaminIntegraSoftwareServicesfortheirfineworkputting thefinalpiecestogether.MywonderfulwifeJilldeservesextraspecialthanksforeverything shedoes.
Finally,I’dliketothankthenumerousreaderswhohavesente-mailmessagesand pointedouterrorsorinconsistenciesinearlierversions.MyWorldWideWebpage www.cis.fiu.edu/~weisscontainsupdatedsourcecode(inJavaandC++),anerratalist, andalinktosubmitbugreports.
M.A.W. Miami,Florida
Introduction Inthischapter,wediscusstheaimsandgoalsofthistextandbrieflyreviewprogramming conceptsanddiscretemathematics.Wewill
Seethathowaprogramperformsforreasonablylargeinputisjustasimportantasits performanceonmoderateamountsofinput.
Summarizethebasicmathematicalbackgroundneededfortherestofthebook. Brieflyreviewrecursion.
SummarizesomeimportantfeaturesofJavathatareusedthroughoutthetext.
1.1What’stheBookAbout? Supposeyouhaveagroupof N numbersandwouldliketodeterminethe kthlargest.This isknownasthe selectionproblem.Moststudentswhohavehadaprogrammingcourse ortwowouldhavenodifficultywritingaprogramtosolvethisproblem.Therearequitea few“obvious”solutions.
Onewaytosolvethisproblemwouldbetoreadthe N numbersintoanarray,sortthe arrayindecreasingorderbysomesimplealgorithmsuchasbubblesort,andthenreturn theelementinposition k
Asomewhatbetteralgorithmmightbetoreadthefirst k elementsintoanarrayand sortthem(indecreasingorder).Next,eachremainingelementisreadonebyone.Asanew elementarrives,itisignoredifitissmallerthanthe kthelementinthearray.Otherwise,it isplacedinitscorrectspotinthearray,bumpingoneelementoutofthearray.Whenthe algorithmends,theelementinthe kthpositionisreturnedastheanswer.
Bothalgorithmsaresimpletocode,andyouareencouragedtodoso.Thenaturalquestions,then,arewhichalgorithmisbetterand,moreimportant,iseitheralgorithmgood enough?Asimulationusingarandomfileof30millionelementsand k = 15,000,000 willshowthatneitheralgorithmfinishesinareasonableamountoftime;eachrequires severaldaysofcomputerprocessingtoterminate(albeiteventuallywithacorrectanswer). Analternativemethod,discussedinChapter7,givesasolutioninaboutasecond.Thus, althoughourproposedalgorithmswork,theycannotbeconsideredgoodalgorithms, becausetheyareentirelyimpracticalforinputsizesthatathirdalgorithmcanhandleina reasonableamountoftime.
Figure1.1 Samplewordpuzzle Asecondproblemistosolveapopularwordpuzzle.Theinputconsistsofatwodimensionalarrayoflettersandalistofwords.Theobjectistofindthewordsinthepuzzle. Thesewordsmaybehorizontal,vertical,ordiagonalinanydirection.Asanexample,the puzzleshowninFigure1.1containsthewords this,two,fat, and that. Theword this begins atrow1,column1,or(1,1),andextendsto(1,4); two goesfrom(1,1)to(3,1); fat goes from(4,1)to(2,3);and that goesfrom(4,4)to(1,1).
Again,thereareatleasttwostraightforwardalgorithmsthatsolvetheproblem.For eachwordinthewordlist,wecheckeachorderedtriple(row,column,orientation)for thepresenceoftheword.Thisamountstolotsofnested for loopsbutisbasically straightforward.
Alternatively,foreachorderedquadruple(row,column,orientation,numberofcharacters) thatdoesn’trunoffanendofthepuzzle,wecantestwhetherthewordindicatedisinthe wordlist.Again,thisamountstolotsofnested for loops.Itispossibletosavesometime ifthemaximumnumberofcharactersinanywordisknown.
Itisrelativelyeasytocodeupeithermethodofsolutionandsolvemanyofthereal-life puzzlescommonlypublishedinmagazines.Thesetypicallyhave16rows,16columns, and40orsowords.Suppose,however,weconsiderthevariationwhereonlythepuzzle boardisgivenandthewordlistisessentiallyanEnglishdictionary.Bothofthesolutions proposedrequireconsiderabletimetosolvethisproblemandthereforearenotacceptable. However,itispossible,evenwithalargewordlist,tosolvetheprobleminamatterof seconds.
Animportantconceptisthat,inmanyproblems,writingaworkingprogramisnot goodenough.Iftheprogramistoberunonalargedataset,thentherunningtimebecomes anissue.Throughoutthisbookwewillseehowtoestimatetherunningtimeofaprogram forlargeinputsand,moreimportant,howtocomparetherunningtimesoftwoprograms withoutactuallycodingthem.Wewillseetechniquesfordrasticallyimprovingthespeed ofaprogramandfordeterminingprogrambottlenecks.Thesetechniqueswillenableusto findthesectionofthecodeonwhichtoconcentrateouroptimizationefforts.
1.2MathematicsReview
Thissectionlistssomeofthebasicformulasyouneedtomemorizeorbeabletoderive andreviewsbasicprooftechniques.
1.2.1Exponents
X A X B = X A+B X A X B = X A B (X A )B = X AB
X N + X N = 2X N = X 2N 2N + 2N = 2N +1
1.2.2Logarithms
Incomputerscience,alllogarithmsaretothebase2unlessspecifiedotherwise.
Definition1.1.
X A = B ifandonlyiflogX B = A
Severalconvenientequalitiesfollowfromthisdefinition.
Theorem1.1.
logA B = logC B logC A ; A, B, C > 0, A = 1
Proof.
Let X = logC B,Y = logC A, and Z = logA B.Then,bythedefinitionoflogarithms, CX = B, CY = A,and AZ = B.Combiningthesethreeequalitiesyields CX = B = (CY )Z .Therefore, X = YZ, whichimplies Z = X /Y ,provingthetheorem.
Theorem1.2.
log AB = log A + log B; A, B > 0
Proof.
Let X = log A, Y = log B,and Z = log AB.Then,assumingthedefaultbaseof2, 2X = A,2Y = B,and2Z = AB.Combiningthelastthreeequalitiesyields2X 2Y = AB = 2Z .Therefore, X + Y = Z,whichprovesthetheorem.
Someotherusefulformulas,whichcanallbederivedinasimilarmanner,follow.
log A/B = log A log B
log(AB ) = B log A
log X < X forall X > 0
log1 = 0,log2 = 1,log1,024 = 10,log1,048,576 = 20
1.2.3Series Theeasiestformulastorememberare
andthecompanion,
i=0 Ai = AN +1 1 A 1
Inthelatterformula,if0 < A < 1,then
andas N tendsto ∞,thesumapproaches1/(1 A).Thesearethe“geometricseries” formulas.
Wecanderivethelastformulafor ∞ i=0 Ai (0 < A < 1)inthefollowingmanner.Let S bethesum.Then
Then
Ifwesubtractthesetwoequations(whichispermissibleonlyforaconvergentseries), virtuallyallthetermsontherightsidecancel,leaving
whichimpliesthat
Wecanusethissametechniquetocompute ∞ i=1 i/2i ,asumthatoccursfrequently. Wewrite
andmultiplyby2,obtaining
