﻿
x
Contents
5.7 HashTableswithWorst-CaseO(1)Access
212
5.7.1 PerfectHashing g 213
5.7.2 CuckooHashing g 215
5.7.3 HopscotchHashing g 227
5.8 UniversalHashing
230
5.9 ExtendibleHashing
233
Summary 236
Exercises 237
References 241
Chapter6 PriorityQueues(Heaps)
245
6.1 Model
245
6.2 SimpleImplementations
246
6.3 BinaryHeap
247
6.3.1 StructureProperty y 247
6.3.2 Heap-OrderProperty y 248
6.3.3 BasicHeapOperations s 249
6.3.4 OtherHeapOperations s 252
6.4 ApplicationsofPriorityQueues
257
6.4.1 TheSelectionProblem
258
6.4.2 EventSimulation n 259
6.5 d-Heaps
260
6.6 LeftistHeaps
261
6.6.1 LeftistHeapProperty y 261
6.6.2 LeftistHeapOperations s 262
6.7 SkewHeaps
269
6.8 BinomialQueues
271
6.8.1 BinomialQueueStructure e 271
6.8.2 BinomialQueueOperations s 271
6.8.3 ImplementationofBinomialQueues s 276
6.9 PriorityQueuesintheStandardLibrary
282
Summary 283
Exercises 283
References 288
Chapter7 Sorting
291
7.1 Preliminaries
291
7.2 InsertionSort
292
7.2.1 TheAlgorithm
292
7.2.2 STLImplementationofInsertionSort t 293
7.2.3 AnalysisofInsertionSort t 294
7.3 ALowerBoundforSimpleSortingAlgorithms
295
Convert pdf to powerpoint using - C# Create PDF from PowerPoint Library to convert pptx, ppt to PDF in C#.net, ASP.NET MVC, WinForms, WPF
Online C# Tutorial for Creating PDF from Microsoft PowerPoint Presentation
how to add pdf to powerpoint presentation; table from pdf to powerpoint
Convert pdf to powerpoint using - VB.NET Create PDF from PowerPoint Library to convert pptx, ppt to PDF in vb.net, ASP.NET MVC, WinForms, WPF
VB.NET Tutorial for Export PDF file from Microsoft Office PowerPoint
pdf to powerpoint converter; how to convert pdf to ppt for
Contents
xi
7.4 Shellsort
296
7.4.1 Worst-CaseAnalysisofShellsort t 297
7.5 Heapsort
300
7.5.1 AnalysisofHeapsort t 301
7.6 Mergesort
304
7.6.1 AnalysisofMergesort t 306
7.7 Quicksort
309
7.7.1 PickingthePivot t 311
7.7.2 PartitioningStrategy y 313
7.7.3 SmallArrays s 315
7.7.4 ActualQuicksortRoutines s 315
7.7.5 AnalysisofQuicksort t 318
7.7.6 ALinear-Expected-TimeAlgorithmforSelection n 321
7.8 AGeneralLowerBoundforSorting
323
7.8.1 DecisionTrees s 323
7.9 Decision-TreeLowerBoundsforSelectionProblems
325
328
331
7.12ExternalSorting
336
7.12.1WhyWeNeedNewAlgorithms 336
7.12.2ModelforExternalSorting 336
7.12.3TheSimpleAlgorithm
337
7.12.4MultiwayMerge 338
7.12.5PolyphaseMerge 339
7.12.6ReplacementSelection 340
Summary 341
Exercises 341
References 347
Chapter8 TheDisjointSetsClass
351
8.1 EquivalenceRelations
351
8.2 TheDynamicEquivalenceProblem
352
8.3 BasicDataStructure
353
8.4 SmartUnionAlgorithms
357
8.5 PathCompression
360
8.6 WorstCaseforUnion-by-RankandPathCompression
361
8.6.1 SlowlyGrowingFunctions s 362
8.6.2 AnAnalysisbyRecursiveDecomposition n 362
8.6.3 AnO(Mlog*N)Bound d 369
8.6.4 AnO(Mα(M,N))Bound d 370
8.7 AnApplication
372
How to C#: Overview of Using XDoc.PowerPoint
How to C#: Overview of Using XDoc.PowerPoint. your application with advanced PowerPoint document manipulating SDK to load, create, edit, convert, extract, and
pdf to ppt; convert pdf to editable powerpoint online
C# PDF Convert to Jpeg SDK: Convert PDF to JPEG images in C#.net
Convert PDF to JPEG Using C#.NET. Add necessary references: RasterEdge.Imaging.Basic. dll. RasterEdge.Imaging.Basic.Codec.dll. RasterEdge.Imaging.Drawing.dll.
convert pdf to editable ppt online; how to convert pdf into powerpoint presentation
xii
Contents
Summary 374
Exercises 375
References 376
Chapter9 GraphAlgorithms
379
9.1 Deﬁnitions
379
9.1.1 RepresentationofGraphs s 380
9.2 TopologicalSort
382
9.3 Shortest-PathAlgorithms
386
9.3.1 UnweightedShortestPaths s 387
9.3.2 Dijkstra’sAlgorithm
391
9.3.3 GraphswithNegativeEdgeCosts s 400
9.3.4 AcyclicGraphs s 400
9.3.6 ShortestPathExample e 404
9.4 NetworkFlowProblems
406
9.4.1 ASimpleMaximum-FlowAlgorithm
408
9.5 MinimumSpanningTree
413
9.5.1 Prim’sAlgorithm
414
9.5.2 Kruskal’sAlgorithm
417
9.6 ApplicationsofDepth-FirstSearch
419
9.6.1 UndirectedGraphs s 420
9.6.2 Biconnectivity y 421
9.6.3 EulerCircuits s 425
9.6.4 DirectedGraphs s 429
9.6.5 FindingStrongComponents s 431
9.7 IntroductiontoNP-Completeness
432
9.7.1 Easyvs.Hard d 433
9.7.2 TheClassNP P 434
9.7.3 NP-CompleteProblems s 434
Summary 437
Exercises 437
References 445
Chapter10AlgorithmDesignTechniques
449
10.1GreedyAlgorithms
449
10.1.1ASimpleSchedulingProblem
450
10.1.2HuffmanCodes 453
10.1.3ApproximateBinPacking 459
10.2DivideandConquer
467
10.2.1RunningTimeofDivide-and-ConquerAlgorithms 468
10.2.2Closest-PointsProblem
470
VB.NET PDF Convert to HTML SDK: Convert PDF to html files in vb.
converter library control is a 100% clean .NET document image solution, which is designed to help .NET developers convert PDF to HTML webpage using simple VB
drag and drop pdf into powerpoint; how to change pdf file to powerpoint
VB.NET PDF Convert to Tiff SDK: Convert PDF to tiff images in vb.
VB.NET PDF - Convert PDF to TIFF Using VB in VB.NET. using RasterEdge.Imaging.Basic; using RasterEdge.XDoc.PDF; Demo Code to Convert PDF to Tiff Using VB.NET.
export pdf into powerpoint; convert pdf into powerpoint online
Contents
xiii
10.2.3TheSelectionProblem
475
10.2.4TheoreticalImprovementsforArithmeticProblems 478
10.3DynamicProgramming
482
10.3.2OrderingMatrixMultiplications 485
10.3.3OptimalBinarySearchTree 487
10.4RandomizedAlgorithms
494
10.4.1Random-NumberGenerators 495
10.4.2SkipLists 500
10.4.3PrimalityTesting 503
10.5BacktrackingAlgorithms
506
10.5.1TheTurnpikeReconstructionProblem
506
10.5.2Games 511
Summary 518
Exercises 518
References 527
Chapter11AmortizedAnalysis
533
11.1AnUnrelatedPuzzle
534
11.2BinomialQueues
534
11.3SkewHeaps
539
11.4FibonacciHeaps
541
11.4.1CuttingNodesinLeftistHeaps 542
11.4.2LazyMergingforBinomialQueues 544
11.4.3TheFibonacciHeapOperations 548
11.4.4ProofoftheTimeBound 549
11.5SplayTrees
551
Summary 555
Exercises 556
References 557
andImplementation
559
12.1Top-DownSplayTrees
559
12.2Red-BlackTrees
566
12.2.1Bottom-UpInsertion 567
12.2.2Top-DownRed-BlackTrees 568
12.2.3Top-DownDeletion 570
12.3Treaps
576
VB.NET PDF Convert to Jpeg SDK: Convert PDF to JPEG images in vb.
VB.NET How-to, VB.NET PDF, VB.NET Word, VB.NET Excel, VB.NET PowerPoint, VB.NET Tiff, VB.NET Imaging, VB.NET OCR, VB VB.NET PDF - Convert PDF to JPEG Using VB.
pdf page to powerpoint; convert pdf file to powerpoint online
C# PDF Convert to HTML SDK: Convert PDF to html files in C#.net
converter library control is a 100% clean .NET document image solution, which is designed to help .NET developers convert PDF to HTML webpage using simple C#
how to change pdf to powerpoint slides; how to add pdf to powerpoint slide
xiv
Contents
12.4SufﬁxArraysandSufﬁxTrees
579
12.4.1SufﬁxArrays 580
12.4.2SufﬁxTrees 583
12.4.3Linear-TimeConstructionofSufﬁxArraysandSufﬁxTrees 586
12.5k-dTrees
596
12.6PairingHeaps
602
Summary 606
Exercises 608
References 612
AppendixA SeparateCompilationof
ClassTemplates
615
616
A.2 ExplicitInstantiation
616
Index
619
C# PDF Convert to Word SDK: Convert PDF to Word library in C#.net
Using this PDF to Word converting library control, .NET developers can quickly convert PDF document to Word file using Visual C# code.
convert pdf back to powerpoint; how to convert pdf into powerpoint on
C# PDF Convert to SVG SDK: Convert PDF to SVG files in C#.net, ASP
C#.NET PDF SDK - Convert PDF to SVG in C#.NET. C# Programming Language to Render & Convert PDF to SVG Using C#.NET XDoc.PDF Converter Control.
image from pdf to powerpoint; conversion of pdf into ppt
PREFACE
Purpose/Goals
ThefourtheditionofDataStructuresandAlgorithmAnalysisinC
++
describesdatastructures,
methodsoforganizinglargeamountsofdata,andalgorithmanalysis,theestimationofthe
runningtimeofalgorithms.Ascomputersbecomefasterandfaster,theneedforprograms
morecarefulattentiontoefﬁciency,sinceinefﬁcienciesinprogramsbecomemostobvious
wheninputsizesarelarge.Byanalyzinganalgorithmbeforeitisactuallycoded,students
candecideifaparticularsolutionwillbefeasible.Forexample,inthistextstudentslookat
speciﬁcproblemsandseehowcarefulimplementationscanreducethetimeconstraintfor
largeamountsofdatafromcenturiestolessthanasecond.Therefore,noalgorithmordata
structureispresentedwithoutanexplanationofitsrunningtime.Insomecases,minute
detailsthataffecttherunningtimeoftheimplementationareexplored.
Onceasolutionmethodisdetermined,aprogrammuststillbewritten.Ascomputers
havebecomemorepowerful,theproblemstheymustsolvehavebecomelargerandmore
complex,requiringdevelopmentofmoreintricateprograms.Thegoalofthistextistoteach
studentsgoodprogrammingandalgorithmanalysisskillssimultaneouslysothattheycan
developsuchprogramswiththemaximumamountofefﬁciency.
This book is suitable foreither an advanced datastructurescourse or aﬁrst-year
mediate programming, including g such topics s as pointers,recursion,and object-based
programming,aswellassomebackgroundindiscretemath.
Approach
Althoughthematerialinthistextislargelylanguage-independent,programmingrequires
theuseofaspeciﬁclanguage.Asthetitleimplies,wehavechosenC
++
forthisbook.
C
++
ofthesyntactic ﬂawsofC,C
++
providesdirectconstructs (theclassand template)to
implementgenericdatastructuresasabstractdatatypes.
ThemostdifﬁcultpartofwritingthisbookwasdecidingontheamountofC
++
to
include.UsetoomanyfeaturesofC
++
andonegetsanincomprehensibletext;usetoofew
andyouhavelittlemorethanaCtextthatsupportsclasses.
Theapproachwetakeistopresentthematerialinanobject-basedapproach.Assuch,
thereisalmostnouseofinheritanceinthetext.Weuseclasstemplatestodescribegeneric
datastructures.WegenerallyavoidesotericC
++
featuresandusethe
vector
and
string
classesthatarenowpartoftheC
++
standard.Previouseditionshaveimplementedclass
templatesbyseparating theclasstemplateinterfacefromitsimplementation.Although
xv
xvi
Preface
representsclasstemplatesasasingleunit,withnoseparationofinterfaceandimplementa-
tion.Chapter1providesareviewoftheC
++
featuresthatareusedthroughoutthetextand
couldberewrittentouseseparatecompilation.
Complete versions ofthe datastructures,in both C
++
and Java, , areavailableon
theInternet.Weusesimilarcodingconventionstomaketheparallelsbetweenthetwo
languagesmoreevident.
SummaryoftheMostSigniﬁcantChangesintheFourthEdition
Thefourtheditionincorporatesnumerousbugﬁxes,andmanypartsofthebookhave
Chapter4includesimplementationoftheAVLtreedeletionalgorithm—atopicoften
Chapter5hasbeenextensivelyrevisedandenlargedandnowcontainsmaterialon
unordered_set
and
unordered_map
classtemplatesintroducedinC
++
11.
Chapter6ismostlyunchanged;however,theimplementationofthebinaryheapmakes
useofmoveoperationsthatwereintroducedinC
++
11.
proofs has been n added. . Sorting g code makes s use e of move operations that were
introducedinC
++
11.
Chapter 8 uses the new w union/ﬁnd d analysis s by y Seidel and Sharir r and shows the
N)boundinprioreditions.
sufﬁxarrayconstructionalgorithmbyKarkkainenandSanders(withimplementation).
ThesectionscoveringdeterministicskiplistsandAA-treeshavebeenremoved.
Throughoutthetext,thecodehasbeenupdatedtouseC
++
11.Notably,thismeans
useofthenewC
++
11features,includingthe
auto
keyword,therange
for
loop,move
constructionandassignment,anduniforminitialization.
Overview
Chapter1containsreviewmaterialondiscretemathandrecursion.Ibelievetheonlyway
tobecomfortablewithrecursionistoseegoodusesoverandover.Therefore,recursion
isprevalentinthistext,withexamplesineverychapterexceptChapter5.Chapter1also
includesmaterialthatservesasareviewofbasicC
++
andimportantconstructsinC
++
classdesign.
Chapter2deals with algorithmanalysis.Thischapterexplainsasymptoticanalysis
anditsmajorweaknesses.Manyexamplesareprovided,includinganin-depthexplana-
tionoflogarithmicrunningtime.Simplerecursiveprogramsareanalyzedbyintuitively
convertingthemintoiterativeprograms.Morecomplicateddivide-and-conquerprograms
areintroduced,butsomeoftheanalysis(solvingrecurrencerelations)isimplicitlydelayed
untilChapter7,whereitisperformedindetail.
Preface
xvii
vector
and
list
classes,includingmaterialoniterators,anditprovidesimplementations
ofasigniﬁcantsubsetofthe
STLvectorandlist
classes.
Chapter4coverstrees,withanemphasisonsearchtrees,includingexternalsearch
trees(B-trees).The
UNIX
ﬁlesystemandexpressiontreesareusedasexamples.AVLtrees
andsplaytreesareintroduced.Morecarefultreatmentofsearchtreeimplementationdetails
trees,isdeferreduntilChapter10.Datastructuresforanexternalmediumareconsidered
set
and
map
classes,
includingasigniﬁcantexamplethatillustratestheuseofthreeseparatemapstoefﬁciently
solveaproblem.
Chapter 5 discusses hash tables, including g the e classic c algorithms such as sepa-
rate chaining and linearand d quadratic c probing,as wellas several newer algorithms,
namelycuckoohashingandhopscotchhashing.Universalhashingisalsodiscussed,and
extendiblehashingiscoveredattheendofthechapter.
materialonsomeofthetheoreticallyinterestingimplementationsofpriorityqueues.The
FibonacciheapisdiscussedinChapter11,andthepairingheapisdiscussedinChapter12.
Allthe importantgeneral-purposesorting algorithmsarecovered and compared.Four
algorithmsareanalyzedindetail:insertionsort,Shellsort,heapsort,andquicksort.Newto
sortingiscoveredattheendofthechapter.
Chapter8discussesthedisjointsetalgorithmwithproofoftherunningtime.Thisisa
shortandspeciﬁcchapterthatcanbeskippedifKruskal’salgorithmisnotdiscussed.
Chapter9coversgraphalgorithms.Algorithmsongraphsareinteresting,notonly
becausetheyfrequentlyoccurinpracticebutalsobecausetheirrunningtimeissoheavily
dependentontheproperuseofdatastructures.Virtuallyallofthestandardalgorithms
arepresentedalongwithappropriatedatastructures,pseudocode,andanalysisofrunning
time.Toplacetheseproblemsinapropercontext,ashortdiscussiononcomplexitytheory
(includingNP-completenessandundecidability)isprovided.
Chapter 10 coversalgorithmdesignby examining common problem-solvingtech-
niques.Thischapterisheavilyfortiﬁedwithexamples.Pseudocodeisusedintheselater
implementationdetails.
Chapter11dealswithamortizedanalysis.ThreedatastructuresfromChapters4and
6andtheFibonacciheap,introducedinthischapter,areanalyzed.
thepairingheap.Thischapterdepartsfromtherestofthetextbyprovidingcompleteand
carefulimplementationsforthesearchtreesandpairingheap.Thematerialisstructuredso
thattheinstructorcanintegratesectionsintodiscussionsfromotherchapters.Forexample,
thetop-down red-blacktreeinChapter12canbediscussedalong with AVLtrees(in
Chapter4).
Chapters1to9provideenoughmaterialformostone-semesterdatastructurescourses.
easilybereferredtointheearlierchapters.ThediscussionofNP-completenessinChapter9
xviii
Preface
workonNP-completenesstoaugmentthistext.
Exercises
Exercises,providedattheendofeachchapter,matchtheorderinwhichmaterialispre-
Difﬁcultexercisesaremarkedwithanasterisk,andmorechallengingexerciseshavetwo
asterisks.
References
Referencesareplacedattheendofeachchapter.Generallythereferenceseitherarehis-
torical,representingtheoriginalsourceofthematerial,ortheyrepresentextensionsand
improvements tothe results given in thetext. Some references representsolutionsto
exercises.
Supplements
Sourcecodeforexampleprograms
Errata
In addition,thefollowing materialis availableonly toqualiﬁed instructorsatPearson
InstructorResourceCenter(www.pearsonhighered.com/irc).VisittheIRCorcontactyour
PearsonEducationsalesrepresentativeforaccess.
Solutionstoselectedexercises
Figuresfromthebook
Errata
Acknowledgments
Many,manypeoplehavehelpedmeinthepreparationofbooksinthisseries.Someare
listedinotherversionsofthebook;thankstoall.
tothankmyeditor,TracyJohnson,andproductioneditor,MarilynLloyd.Mywonderful
wifeJilldeservesextraspecialthanksforeverythingshedoes.
pointedouterrorsorinconsistenciesinearlierversions.Mywebsitewww.cis.ﬁu.edu/~weiss
willalsocontainupdatedsourcecode(inC
++
bugreports.
M.A.W.
Miami,Florida
C H A P P T E R
1
Programming:AGeneral
Overview
Inthischapter,wediscusstheaimsandgoalsofthistextandbrieﬂyreviewprogramming
conceptsanddiscretemathematics.Wewill...
Seethathowaprogramperformsforreasonablylargeinputisjustasimportantasits
performanceonmoderateamountsofinput.
Summarizethebasicmathematicalbackgroundneededfortherestofthebook.
Brieﬂyreviewrecursion.
SummarizesomeimportantfeaturesofC
++
thatareusedthroughoutthetext.
SupposeyouhaveagroupofNnumbersandwouldliketodeterminethekthlargest.This
ortwowouldhavenodifﬁcultywritingaprogramtosolvethisproblem.Therearequitea
few“obvious”solutions.
arrayindecreasingorderbysomesimplealgorithmsuchasbubblesort,andthenreturn
theelementinpositionk.