Algorithms in C++, Parts 1-4: Fundamentals, Data Structure, Sorting, Searching

Contents......Page 16
Fundamentals......Page 22
 Chapter 1. Introduction......Page 24
  1.1 Algorithms......Page 25
  1.2 A Sample Problem—Connectivity......Page 28
  1.3 Union-Find Algorithms......Page 32
  1.4 Perspective......Page 43
  1.5 Summary of Topics......Page 45
 Chapter 2. Principles of Algorithm Analysis......Page 48
  2.1 Implementation and Empirical Analysis......Page 49
  2.2 Analysis of Algorithms......Page 54
  2.3 Growth of Functions......Page 57
  2.4 Big-Oh Notation......Page 65
  2.5 Basic Recurrences......Page 70
  2.6 Examples of Algorithm Analysis......Page 74
  2.7 Guarantees, Predictions, and Limitations......Page 80
Data Structures......Page 88
 Chapter 3. Elementary Data Structures......Page 90
  3.1 Building Blocks......Page 91
  3.2 Arrays......Page 104
  3.3 Linked Lists......Page 112
  3.4 Elementary List Processing......Page 118
  3.5 Memory Allocation for Lists......Page 127
  3.6 Strings......Page 131
  3.7 Compound Data Structures......Page 137
 Chapter 4. Abstract Data Types......Page 150
  4.1 Abstract Objects and Collections of Objects......Page 161
  4.2 Pushdown Stack ADT......Page 165
  4.3 Examples of Stack ADT Clients......Page 168
  4.4 Stack ADT Implementations......Page 174
  4.5 Creation of a New ADT......Page 179
  4.6 FIFO Queues and Generalized Queues......Page 187
  4.7 Duplicate and Index Items......Page 196
  4.8 First-Class ADTs......Page 200
  4.9 Application-Based ADT Example......Page 213
  4.10 Perspective......Page 219
 Chapter 5. Recursion and Trees......Page 222
  5.1 Recursive Algorithms......Page 223
  5.2 Divide and Conquer......Page 231
  5.3 Dynamic Programming......Page 243
  5.4 Trees......Page 251
  5.5 Mathematical Properties of Trees......Page 261
  5.6 Tree Traversal......Page 264
  5.7 Recursive Binary-Tree Algorithms......Page 270
  5.8 Graph Traversal......Page 276
  5.9 Perspective......Page 282
Sorting......Page 286
 Chapter 6. Elementary Sorting Methods......Page 288
  6.1 Rules of the Game......Page 290
  6.2 Selection Sort......Page 296
  6.3 Insertion Sort......Page 297
  6.4 Bubble Sort......Page 300
  6.5 Performance Characteristics of Elementary Sorts......Page 302
  6.6 Shellsort......Page 308
  6.7 Sorting Other Types of Data......Page 316
  6.8 Index and Pointer Sorting......Page 322
  6.9 Sorting Linked Lists......Page 330
  6.10 Key-Indexed Counting......Page 335
 Chapter 7. Quicksort......Page 338
  7.1 The Basic Algorithm......Page 339
  7.2 Performance Characteristics of Quicksort......Page 344
  7.3 Stack Size......Page 348
  7.4 Small Subfiles......Page 351
  7.5 Median-of-Three Partitioning......Page 354
  7.6 Duplicate Keys......Page 359
  7.7 Strings and Vectors......Page 362
  7.8 Selection......Page 364
 Chapter 8. Merging and Mergesort......Page 370
  8.1 Two-Way Merging......Page 371
  8.2 Abstract In-Place Merge......Page 374
  8.3 Top-Down Mergesort......Page 376
  8.4 Improvements to the Basic Algorithm......Page 380
  8.5 Bottom-Up Mergesort......Page 382
  8.6 Performance Characteristics of Mergesort......Page 386
  8.7 Linked-List Implementations of Mergesort......Page 389
  8.8 Recursion Revisited......Page 393
 Chapter 9. Priority Queues and Heapsort......Page 396
  9.1 Elementary Implementations......Page 400
  9.2 Heap Data Structure......Page 404
  9.3 Algorithms on Heaps......Page 406
  9.4 Heapsort......Page 412
  9.5 Priority-Queue ADT......Page 419
  9.6 Priority Queues for Index Items......Page 425
  9.7 Binomial Queues......Page 429
 Chapter 10. Radix Sorting......Page 440
  10.1 Bits, Bytes, and Words......Page 442
  10.2 Binary Quicksort......Page 446
  10.3 MSD Radix Sort......Page 450
  10.4 Three-Way Radix Quicksort......Page 458
  10.5 LSD Radix Sort......Page 462
  10.6 Performance Characteristics of Radix Sorts......Page 465
  10.7 Sublinear-Time Sorts......Page 470
 Chapter 11. Special-Purpose Sorts......Page 474
  11.1 Batcher's Odd-Even Mergesort......Page 476
  11.2 Sorting Networks......Page 481
  11.3 External Sorting......Page 489
  11.4 Sort-Merge Implementations......Page 495
  11.5 Parallel Sort/Merge......Page 501
Searching......Page 510
 Chapter 12. Symbol Tables and BSTs......Page 512
  12.1 Symbol-Table Abstract Data Type......Page 514
  12.2 Key-Indexed Search......Page 522
  12.3 Sequential Search......Page 525
  12.4 Binary Search......Page 533
  12.5 Binary Search Trees (BSTs)......Page 538
  12.6 Performance Characteristics of BSTs......Page 544
  12.7 Index Implementations with Symbol Tables......Page 548
  12.8 Insertion at the Root in BSTs......Page 552
  12.9 BST Implementations of Other ADT Functions......Page 556
 Chapter 13. Balanced Trees......Page 566
  13.1 Randomized BSTs......Page 570
  13.2 Splay BSTs......Page 577
  13.3 Top-Down 2-3-4 Trees......Page 583
  13.4 Red-Black Trees......Page 588
  13.5 Skip Lists......Page 598
  13.6 Performance Characteristics......Page 606
 Chapter 14. Hashing......Page 610
  14.1 Hash Functions......Page 611
  14.2 Separate Chaining......Page 620
  14.3 Linear Probing......Page 625
  14.4 Double Hashing......Page 631
  14.5 Dynamic Hash Tables......Page 636
  14.6 Perspective......Page 640
 Chapter 15. Radix Search......Page 646
  15.1 Digital Search Trees......Page 647
  15.2 Tries......Page 651
  15.3 Patricia Tries......Page 660
  15.4 Multiway Tries and TSTs......Page 669
  15.5 Text String Index Applications......Page 687
 Chapter 16. External Searching......Page 692
  16.1 Rules of the Game......Page 694
  16.2 Indexed Sequential Access......Page 697
  16.3 B Trees......Page 699
  16.4 Extendible Hashing......Page 713
  16.5 Perspective......Page 725
 B......Page 730
 D......Page 731
 F......Page 732
 I......Page 733
 M......Page 734
 O......Page 735
 Q......Page 736
 S......Page 737
 T......Page 738
 Y......Page 739