Algorithms in Java, Third Edition (Parts 1-4)

By blending theory and practice, this book appeals equally to both the academic and professional markets. For the first time, Sedgewick's seminal work on algorithms and data structures is available with implementations in Java. The author has developed new Java code that both expresses the methods in a concise and direct manner, and also provides programmers with the practical means to test them on real applications. 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 This edition of Robert Sedgewick's popular work provides current and comprehensive coverage of important algorithms for Java programmers. Michael Schidlowsky and Sedgewick have developed new Java implementations that both express the methods in a concise and direct manner and provide programmers with the practical means to test them on real applications. Many new algorithms are presented, and the explanations of each algorithm are much more detailed than in previous editions. A new text design and detailed, innovative figures, with accompanying commentary, greatly enhance the presentation. The third edition retains the successful blend of theory and practice that has made Sedgewick's work an invaluable resource for more than 400,000 programmers! This particular book, Parts 1-4, represents the essential first half of Sedgewick's complete work. It provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. Although the substance of the book applies to programming in any language, the implementations by Schidlowsky and Sedgewick also exploit the natural match between Java classes and abstract data type (ADT) implementations. Highlights Java class implementations of more than 100 important practical algorithms Emphasis on ADTs, modular programming, and object-oriented programming Extensive coverage of arrays, linked lists, trees, and other fundamental data structures Thorough treatment of algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT implementations (search algorithms) Complete implementations for binomial queues, multiway radix sorting, randomized BSTs, splay trees, skip lists, multiway tries, B trees, extendible hashing, and many other advanced methods Quantitative information about the algorithms that gives you a basis for comparing them More than 1,000 exercises and more than 250 detailed figures to help you learn properties of the algorithms Whether you are learning the algorithms for the first time or wish to have up-to-date reference material that incorporates new programming styles with classic and new algorithms, you will find a wealth of useful information in this book. Provides extensive coverage of fundamental data structures and algorithms for sorting, searching, and related applications. This book includes Java class implementations of more than 100 important practical algorithms. It emphasises on ADTs, modular programming, and object-oriented programming. It also covers arrays, linked lists, trees, and more. In these volumes, Robert Sedgewick focuses on practical applications, giving readers all the information, diagrams and real code they need to confidently implement, debug and use the algorithms he presents