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

Robert Sedgewick has thoroughly rewritten and substantially expanded and updated his popular work to provide current and comprehensive coverage of important algorithms and data structures. Christopher Van Wyk and Sedgewick have developed new C++ implementations that both express the methods in a concise and direct manner, and also 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 250,000 programmers! This particular book, Parts 1n4, 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 Van Wyk and Sedgewick also exploit the natural match between C++ classes and ADT implementations. **Highlights*** Expanded coverage of arrays, linked lists, strings, trees, and other basic data structures * Greater emphasis on abstract data types (ADTs), modular programming, object-oriented programming, and C++ classes than in previous editions * Over 100 algorithms for sorting, selection, priority queue ADT implementations, and symbol table ADT (searching) implementations * New implementations of binomial queues, multiway radix sorting, randomized BSTs, splay trees, skip lists, multiway tries, B trees, extendible hashing, and much more * Increased quantitative information about the algorithms, giving you a basis for comparing them * Over 1000 new exercises to help you learn the properties of 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. 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

robert Sedgewick Has Thoroughly Rewritten And Substantially Expanded And Updated His Popular Work To Provide Current And Comprehensive Coverage Of Important Algorithms And Data Structures. Christopher Van Wyk And Sedgewick Have Developed New C++ Implementations That Both Express The Methods In A Concise And Direct Manner, And Also 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 250,000 Programmers!

this Particular Book, Parts 1n4, 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 Van Wyk And Sedgewick Also Exploit The Natural Match Between C++ Classes And Adt Implementations.

highlights

• expanded Coverage Of Arrays, Linked Lists, Strings, Trees, And Other Basic Data Structures
• greater Emphasis On Abstract Data Types (adts), Modular Programming, Object-oriented Programming, And C++ Classes Than In Previous Editions
• over 100 Algorithms For Sorting, Selection, Priority Queue Adt Implementations, And Symbol Table Adt (searching) Implementations
• new Implementations Of Binomial Queues, Multiway Radix Sorting, Randomized Bsts, Splay Trees, Skip Lists, Multiway Tries, B Trees, Extendible Hashing, And Much More
• increased Quantitative Information About The Algorithms, Giving You A Basis For Comparing Them
• over 1000 New Exercises To Help You Learn The Properties Of 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.

the Algorithms Included Here Cover A Broad Range Of Fundamental And More Advanced Methods: Sorting, Searching, String-processing, Geometric, Graph, And Mathematical Algorithms. Readers Will See How Key Algorithms Can Be Implemented, Run, Debugged, And Used In Real Applications--plus Why Some Algorithms Are To Be Preferred Over Others.

Robert Sedgewick has thoroughly rewritten and substantially expanded his popular work to provide current and comprehensive coverage of important algorithms and data structures. 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 250,000 programmers! Whether you are a student learning the algorithms for the first time or a professional interested in having up-to-date reference material, you will find a wealth of useful information in this book. Algorithms in C++ contains exercises to help students learn the properties of algorithms with a greater emphasis on abstract data types, modular programming, object oriented programming and C++ classes THE OBJECTIVE OF this book is to study a broad variety of important and useful algorithms: methods for solving problems that are suited for computer implementation.