Introduction1
1.1.WhatstheBookAbout?1
1.2.MathematicsReview3
1.2.1.Exponents3
1.2.2.Logarithms3
1.2.3.Series4
1.2.4.ModularArithmetic5
1.2.5.ThePWord6
1.3.ABriefIntroductiontoRecursion
Summary12
Exercises12
References13
2AlgorithmAnalysis15
2.1.MathematicalBackground15
2.2.Model18
2.3.WhattoAnalyze18
2.4.RunningTuneCalculations20
2.4.1.ASimpleExample21
2.4.2.GeneralRules21
2.4.3.SolutionsfortheMaximumSubsequenceSumProblem24
2.4.4.LogarithmsintheRunningTune28
2.4.5.CheckingYourAnalysis33
2.4.6.AGrainofSalt33
Summary34
Exercises35
References39
3Lists,Stacks,andQueues41
3.1.AbstractDataTypes(AnTs)41
3.2.TheListADT42
3.2.1.SimpleArrayImplementationofLists43
3.2.2.LinkedLists43
3.2.3.ProgrammingDetails44
3.2.4.CommonErrors49
3.2.5.DoublyLinkedLists51
3.2.6.CircularlyUnkedLists52
3.2.7.Examples52
3.2.8.CursorImplementationofLinkedLists57
3.3.TheStackADT62
3.3.1.StackModel62
3.3.2.ImplementationofStacks63
3.3.3.Applications71
3.4.TheQueueADT79
3.4.1.QueueModel79
3.4.2.ArrayImplementationofQueues79
3.4.3.ApplicationsofQueues84
Summary85
Exercises85
4Trees89
4.1.Preliminaries89
4.1.1.ImplementationofTrees90
4.1.2.TreeTraversalswithanApplication91
4.2.BinaryTrees95
4.2.1.Implementation96
4.2.2.ExpressionTrees97
4.3.TheSearchTreeADT-BinarySearchTrees100
4.3.1.MakeEmpty101
4.3.2.Find101
4.3.3.FindMinandFindMax103
4.3.4.Insert104
4.3.5.Delete105
4.3.6.Average-CaseAnalysis107
4.4.AvITrees110
4.4.1.SingleRotation112
4.4.2.DoubleRotation115
4.5.SplayTrees123
4.5.1.ASimpleIdea(ThatDoesNotWork)124
4.5.2.Splaying126
4.6.TreeTraversals(Revisited)132
4.7.B-Trees133
Summary138
Exercises139
References146
5Hashing149
5.1.GeneralIdea149
5.2.HashFunction150
5.3.SeparateChaining152
5.4.OpenAddressing157
5.4.1.LinearProbing157
5.4.2.QuadraticProbing160
5.4.3.DoubleHashing164
5.5.Rehashing165
5.6.ExtendibleHashing168
Summary171
Exercises172
References175
6PriorityQueues(Heaps)177
6.1.Model177
6.2.SimpleImplementations178
6.3.BinaryHeap179
6.3.1.StroctureProperty179
6.3.2.HeapOrderProperty180
6.3.3.BasicHeapOperations182
6.3.4.OtherHeapOperations186
6.4.ApplicationsofPriorityQueues189
6.4.1.TheSelectionProblem189
6.4.2.EventSimulation191
6.5.d-Heaps192
6.6.LeftistHeaps193
6.6.1.LeftistHeapProperly193
6.6.2.LeftistHeapOperations194
6.7.SkewHeaps200
6.8.BinomialQueues202
6.8.1.BinomialQueueStructure202
6.8.2.BinomialQueueOperations204
6.8.3.ImplementationofBinomialQueues205
Summary212
Exercises212
References216
7Sorting219
7.1.Preliminaries219
7.2.InsertionSort220
7.2.1.TheAlgorithm220
7.2.2.AnalysisofInsertionSort221
7.3.ALowerBoundforSimpleSortingAlgorithms221
7.4.SheUsort222
7.4.1.Worst-CaseAnalysisofShellsort224
7.5.Heapsort226
7.5.1.AnalysisofHeapsort228
7.6.Mergesort230
7.6.1.AnalysisofMergesort232
7.7.Quicksort235
7.7.1.PickingthePivot236
7.7.2.PartitioningStrategy237
7.7.3.SmallArrays240
7.7.4.ActualQuicksortRoutines240
7.7.5.AnalysisofQuicksort241
7.7.6.ALinear-Expected-TimeAlgorithmforSelection245
7.8.SortingLargeStructures247
7.9.AGeneralLowerBoundforSorting247
7.9.1.DecisionTrees247
7.10.BucketSort250
7.11.ExternalSorting250
7.11.1.WhyWeNeedNewAlgorithms251
7.11.2.ModelforExternalSorting251
……
8TheDisjointSetADT
9GraphAlgorithms
10AlgorithmDesignTechniques
11AmortizedAnalysis
12AdvancedDataStructuresandImplementation