Algorithms in Java, Parts 1-4 Fundamentals, data structures, sorting, searching

Cover......Page 1
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 81
Data Structures......Page 88
 Chapter 3. Elementary Data Structures......Page 90
  3.1 Building Blocks......Page 91
  3.2 Arrays......Page 105
  3.3 Linked Lists......Page 112
  3.4 Elementary List Processing......Page 118
  3.5 Memory Allocation for Lists......Page 128
  3.6 Strings......Page 132
  3.7 Compound Data Structures......Page 137
 Chapter 4. Abstract Data Types......Page 148
  4.1 Collections of Items......Page 158
  4.2 Pushdown Stack ADT......Page 160
  4.3 Examples of Stack ADT Clients......Page 163
  4.4 Stack ADT Implementations......Page 169
  4.5 Generic Implementations......Page 175
  4.6 Creation of a New ADT......Page 178
  4.7 FIFO Queues and Generalized Queues......Page 186
  4.8 Duplicate and Index Items......Page 194
  4.9 First-Class ADTs......Page 198
  4.10 Application-Based ADT Example......Page 209
  4.11 Perspective......Page 215
 Chapter 5. Recursion and Trees......Page 218
  5.1 Recursive Algorithms......Page 219
  5.2 Divide and Conquer......Page 227
  5.3 Dynamic Programming......Page 240
  5.4 Trees......Page 248
  5.5 Mathematical Properties of Trees......Page 257
  5.6 Tree Traversal......Page 261
  5.7 Recursive Binary-Tree Algorithms......Page 267
  5.8 Graph Traversal......Page 272
  5.9 Perspective......Page 278
Sorting......Page 282
 Chapter 6. Elementary Sorting Methods......Page 284
  6.1 Rules of the Game......Page 286
  6.2 Generic Sort Implementations......Page 291
  6.3 Selection Sort......Page 304
  6.4 Insertion Sort......Page 306
  6.5 Bubble Sort......Page 309
  6.6 Performance Characteristics of Elementary Sorts......Page 310
  6.7 Algorithm Visualization......Page 316
  6.8 Shellsort......Page 321
  6.9 Sorting Linked Lists......Page 329
  6.10 Key-Indexed Counting......Page 333
 Chapter 7. Quicksort......Page 336
  7.1 The Basic Algorithm......Page 337
  7.2 Performance Characteristics of Quicksort......Page 342
  7.3 Stack Size......Page 346
  7.4 Small Subfiles......Page 349
  7.5 Median-of-Three Partitioning......Page 352
  7.6 Duplicate Keys......Page 357
  7.7 Strings and Vectors......Page 360
  7.8 Selection......Page 362
 Chapter 8. Merging and Mergesort......Page 368
  8.1 Two-Way Merging......Page 369
  8.2 Abstract In-Place Merge......Page 372
  8.3 Top-Down Mergesort......Page 374
  8.4 Improvements to the Basic Algorithm......Page 378
  8.5 Bottom-Up Mergesort......Page 380
  8.6 Performance Characteristics of Mergesort......Page 384
  8.7 Linked-List Implementations of Mergesort......Page 387
  8.8 Recursion Revisited......Page 391
 Chapter 9. Priority Queues and Heapsort......Page 394
  9.1 Elementary Implementations......Page 398
  9.2 Heap Data Structure......Page 402
  9.3 Algorithms on Heaps......Page 404
  9.4 Heapsort......Page 410
  9.5 Priority-Queue ADT......Page 417
  9.6 Priority Queues for Client Arrays......Page 423
  9.7 Binomial Queues......Page 427
 Chapter 10. Radix Sorting......Page 438
  10.1 Bits, Bytes, and Words......Page 440
  10.2 Binary Quicksort......Page 444
  10.3 MSD Radix Sort......Page 448
  10.4 Three-Way Radix Quicksort......Page 456
  10.5 LSD Radix Sort......Page 462
  10.6 Performance Characteristics of Radix Sorts......Page 465
  10.7 Sublinear-Time Sorts......Page 469
 Chapter 11. Special-Purpose Sorting Methods......Page 474
  11.1 Batcher's Odd–Even Mergesort......Page 476
  11.2 Sorting Networks......Page 481
  11.3 Sorting In Place......Page 489
  11.4 External Sorting......Page 495
  11.5 Sort–Merge Implementations......Page 501
  11.6 Parallel Sort–Merge......Page 507
Searching......Page 516
 Chapter 12. Symbol Tables and BSTs......Page 518
  12.1 Symbol-Table Abstract Data Type......Page 520
  12.2 Key-Indexed Search......Page 530
  12.3 Sequential Search......Page 534
  12.4 Binary Search......Page 542
  12.5 Index Implementations with Symbol Tables......Page 547
  12.6 Binary Search Trees......Page 554
  12.7 Performance Characteristics of BSTs......Page 560
  12.8 Insertion at the Root in BSTs......Page 565
  12.9 BST Implementations of Other ADT Operations......Page 569
 Chapter 13. Balanced Trees......Page 578
  13.1 Randomized BSTs......Page 582
  13.2 Splay BSTs......Page 589
  13.3 Top-Down 2-3-4 Trees......Page 595
  13.4 Red–Black Trees......Page 600
  13.5 Skip Lists......Page 610
  13.6 Performance Characteristics......Page 618
 Chapter 14. Hashing......Page 622
  14.1 Hash Functions......Page 623
  14.2 Separate Chaining......Page 633
  14.3 Linear Probing......Page 638
  14.4 Double Hashing......Page 643
  14.5 Dynamic Hash Tables......Page 648
  14.6 Perspective......Page 652
 Chapter 15. Radix Search......Page 658
  15.1 Digital Search Trees......Page 660
  15.2 Tries......Page 664
  15.3 Patricia Tries......Page 673
  15.4 Multiway Tries and TSTs......Page 683
  15.5 Text-String–Index Applications......Page 702
 Chapter 16. External Searching......Page 708
  16.1 Rules of the Game......Page 710
  16.2 Indexed Sequential Access......Page 713
  16.3 B Trees......Page 715
  16.4 Extendible Hashing......Page 729
  16.5 Perspective......Page 741
Appendix......Page 746
 B......Page 750
 C......Page 751
 E......Page 752
 I......Page 753
 L......Page 754
 N......Page 755
 P......Page 756
 R......Page 757
 S......Page 758
 U......Page 759
 Y......Page 760