This second edition brings together many useful algorithms and their associated data structures in a single, handy reference, featuring a new section on text manipulation algorithms and expanded coverage of arithmetical algorithms. Each algorithm is coded in both C and Pascal.
Author(s): G.H Gonnet, R. Baeza-Yates
Edition: 2nd
Year: 1991
Language: English
Pages: 424
Cover......Page 1
Handbookof Algorithms and Data Structures: In Pascal and C (Second Edition)......Page 4
0201416077......Page 5
Preface......Page 8
Contents......Page 10
1.1 Structure of the chapters ......Page 16
1.2 Naming of variables ......Page 18
1.3 Probabilities ......Page 19
1.5 About the programming languages ......Page 20
1.6 On the code for the algorithms ......Page 21
1.7 Complexity measures and real timings ......Page 22
2.1.1 Grammar for data objects ......Page 24
2.1.2 Constraints for data objects ......Page 27
2.1.2.4 Hierarchical balance ......Page 28
2.2 Algorithm descriptions ......Page 29
2.2.1 Basic (or atomic) operations ......Page 30
2.2.2.1 Composition ......Page 32
2.2.2.2 Alternation ......Page 36
2.2.2.3 Conformation ......Page 37
2.2.3 Interchangeability ......Page 38
3.1.1 Basic sequential search ......Page 40
3.1.2 Self-organizing sequential search: move-to-front method ......Page 43
3.1.3 Self-organizing sequential search: transpose method ......Page 46
3.1.4 Optimal sequential search ......Page 49
3.1.5 Jump search ......Page 50
3.2 Sorted array search ......Page 51
3.2.1 Binary search ......Page 52
3.2.2 Interpolation search ......Page 54
3.2.3 Interpolation-sequential search ......Page 57
3.3 Hashing ......Page 58
3.3.1 Practical hashing functions ......Page 62
3.3.2 Uniform probing hashing ......Page 63
3.3.3 Random probing hashing ......Page 65
3.3.4 Linear probing hashing ......Page 66
3.3.5 Double hashing ......Page 70
3.3.6 Quadratic hashing ......Page 72
3.3.7 Ordered and split-sequence hashing ......Page 74
3.3.8.1 Brent's algorithm ......Page 77
3.3.8.2 Binary tree hashing ......Page 79
3.3.8.3 Last-come-first-served hashing ......Page 82
3.3.8.4 Robin Hood hashing ......Page 84
3.3.9 Optimal hashing ......Page 85
3.3.10 Direct chaining hashing ......Page 86
3.3.11 Separate chaining hashing ......Page 89
3.3.12 Coalesced hashing ......Page 92
3.3.13 Extendible hashing ......Page 95
3.3.14 Linear hashing ......Page 97
3.3.15 External hashing using minin1al internal storage ......Page 100
3.3.16 Perfect hashing ......Page 102
3.3.17 Summary ......Page 105
3.4.1 Binary tree search ......Page 106
3.4.1.1 Randomly generated binary trees ......Page 109
3.4.1.2 Random binary trees ......Page 111
3.4.1.3 Height-balanced trees ......Page 112
3.4.1.4 Weight-balallced trees ......Page 115
3.4.1.5 Balancing by internal path reduction ......Page 117
3.4.1.6 Heuristic organization schemes on binary trees ......Page 120
3.4.1.7 Optimal binary tree search ......Page 124
3.4.1.8 Rotations in binary trees ......Page 127
3.4.1.9 Deletions in binary trees ......Page 129
3.4.1.10 m-ary search trees ......Page 131
3.4.2 B-trees ......Page 132
3.4.2.1 2-3 trees ......Page 139
3.4.2.2 Symmetric binary B-trees ......Page 141
3.4.2.3 1-2 trees ......Page 143
3.4.2.4 2-3-4 trees ......Page 144
3.4.3 Index and indexed sequential files ......Page 145
3.4.3.1 Index sequential access method ......Page 147
3.4.4 Digital trees ......Page 148
3.4.4.1 Hybrid tries ......Page 152
3.4.4.3 Digital search trees ......Page 153
3.4.4.5 Patricia trees ......Page 155
3.5 Multidimensional search ......Page 158
3.5.1 Quad trees ......Page 159
3.5.1.1 Quad tries ......Page 161
3.5.2 K-dimensional trees ......Page 164
4.1 Techniques for sorting arrays ......Page 168
4.1.1 Bubble sort ......Page 169
4.1.2 Linear insertion sort ......Page 171
4.1.3 Quicksort ......Page 173
4.1.4 Shellsort ......Page 176
4.1.5 Heapsort ......Page 179
4.1.6 Interpolation sort ......Page 181
4.1.7 Linear probing sort ......Page 183
4.1.8 Summary ......Page 185
4.2 Sorting other data structures ......Page 186
4.2.1 Merge sort ......Page 188
4.2.2 Quicksort for lists ......Page 189
4.2.3 Bucket sort ......Page 191
4.2.4 Radix sort ......Page 194
4.2.5 Hybrid methods of sorting ......Page 195
4.2.5.2 Distributive partitioning ......Page 196
4.2.6 Treesort ......Page 197
4.3 Merging ......Page 198
4.3.1 List merging ......Page 199
4.3.2 Array merging ......Page 200
4.3.3 Minimal-comparison merging ......Page 201
4.4 External sorting ......Page 202
4.4.1.1 Replacement selection ......Page 204
4.4.1.2 Natural selection ......Page 205
4.4.1.3 Alternating selection ......Page 206
4.4.1.4 Merging phase ......Page 207
4.4.2 Balanced merge sort ......Page 208
4.4.3 Cascade merge sort ......Page 210
4.4.4 Polyphase merge sort ......Page 211
4.4.5 Oscillating merge sort ......Page 215
4.4.6 External Quicksort ......Page 216
5.1 Priority queues ......Page 220
5.1.1 Sorted/unsorted lists ......Page 221
5.1.2 P-trees ......Page 224
5.1.3 Heaps ......Page 226
5.1.4 Van Emde-Boas priority queues ......Page 231
5.1.5 Pagodas ......Page 233
5.1.6.1 Leftist trees ......Page 236
5.1.6.2 Binary priority queues ......Page 238
5.1.6.3 Binary search trees as priority queues ......Page 240
5.1.7 Binomial queues ......Page 241
5.1.8 Summary ......Page 242
5.2 Selection of kth element ......Page 243
5.2.2 Selection by tail recursion ......Page 245
5.2.3 Selection of the mode ......Page 247
6.1 Basic operations, multiplication/division ......Page 250
6.2.1 Binary powering ......Page 255
6.2.2 Arithmetic-geometric mean ......Page 257
6.2.3 Transcendental functions ......Page 258
6.3 Matrix multiplication ......Page 260
6.3.1 Strassen's matrix multiplication ......Page 261
6.3.2 Further asymptotic improvements ......Page 262
6.4 Polynomial evaluation ......Page 263
7.1 Text searching without preprocessing ......Page 266
7.1.1 Brute force text searching ......Page 268
7.1.2 Knuth-Morris-Pratt text searching ......Page 269
7.1.3 Boyer-Moore text searching ......Page 271
7.1.4 Searching sets of strings ......Page 274
7.1.5 Karp-Rabin text searching ......Page 275
7.1.6 Searching text with automata ......Page 277
7.1.7 Shift-or text searching ......Page 281
7.1.8 String similarity searching ......Page 282
7.2 Searching preprocessed text ......Page 285
7.2.1 Inverted files ......Page 286
7.2.2 Trees used for text searching ......Page 288
7.2.3 Searching text with automata ......Page 290
7.2.4 Suffix arrays and PAT arrays ......Page 292
7.2.5 DAWG ......Page 294
7.2.6 Hashing methods for text searching ......Page 295
7.2.7 P-strings ......Page 296
7.3.1 Searching longest common subsequences ......Page 298
7.3.2 Two-dimensional searching ......Page 299
I.1 Zipf's law ......Page 304
I.1.2 Second generalization of a Zipfian distribution ......Page 305
I.2 Bradford's law ......Page 306
I.4 80%-20% rule ......Page 308
II. Asymptotic Expansions ......Page 312
II.1 Asymptotic expansions of sums ......Page 313
II.2 Gamma-type expansions ......Page 315
II.3 Exponential-type expansions ......Page 316
II.4 Asymptotic expansions of sums and definite integrals containing e^-(x^2) ......Page 317
II.5 Doubly exponential forms ......Page 318
II.6 Roots of polynomials ......Page 319
II.7 Sums containing descending factorials ......Page 320
II.8 Summation formulas ......Page 322
III.1 Textbooks ......Page 324
III.2 Papers ......Page 326
IV.1 Searching algorithms ......Page 390
IV.2 Sorting algorithms ......Page 402
IV.3 Selection algorithms ......Page 414
IV.4 Text algorithms ......Page 423
Index ......Page 430
