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

✍ Scribed by Sedgewick, Robert;Wyk, Christopher J Van

• Publisher: Addison-Wesley Professional
• Year: 1998
• Tongue: English
• Leaves: 739
• Category: Library

✦ Synopsis

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.HighlightsExpanded 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.

✦ Table of Contents

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

✦ Subjects

Computer Science;Programming;Science;Algorithms;Technical;Nonfiction;Coding;Computers;Technology;Reference