{"product_id":"data-structures-and-algorithms-in-c-isbn-9780470383278","title":"Data Structures and Algorithms in C++","description":"This second edition of Data Structures and Algorithms in C++ is designed to provide an introduction to data structures and algorithms, including their design, analysis, and implementation. The authors offer an introduction to object-oriented design with C++ and design patterns, including the use of class inheritance and generic programming through class and function templates, and retain a consistent object-oriented viewpoint throughout the book.  \u003cp\u003eThis is a “sister” book to Goodrich \u0026amp; Tamassia’s Data Structures and Algorithms in Java, but uses C++ as the basis language instead of Java. This C++ version retains the same pedagogical approach and general structure as the Java version so schools that teach data structures in both C++ and Java can share the same core syllabus.\u003c\/p\u003e \u003cp\u003eIn terms of curricula based on the IEEE\/ACM 2001 Computing Curriculum, this book is appropriate for use in the courses CS102 (I\/O\/B versions), CS103 (I\/O\/B versions), CS111 (A version), and CS112 (A\/I\/O\/F\/H versions).\u003c\/p\u003e \u003cp\u003e\u003cb\u003e1 A \u003c\/b\u003e\u003cb\u003eC++ \u003c\/b\u003e\u003cb\u003ePrimer 1\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e1.1 Basic C++ Programming Elements 2\u003c\/p\u003e \u003cp\u003e1.1.1 A Simple C++ Program 2\u003c\/p\u003e \u003cp\u003e1.1.2 Fundamental Types 4\u003c\/p\u003e \u003cp\u003e1.1.3 Pointers, Arrays, and Structures 7\u003c\/p\u003e \u003cp\u003e1.1.4 Named Constants, Scope, and Namespaces 13\u003c\/p\u003e \u003cp\u003e1.2 Expressions 16\u003c\/p\u003e \u003cp\u003e1.2.1 Changing Types through Casting 20\u003c\/p\u003e \u003cp\u003e1.3 Control Flow 23\u003c\/p\u003e \u003cp\u003e1.4 Functions 26\u003c\/p\u003e \u003cp\u003e1.4.1 Argument Passing 28\u003c\/p\u003e \u003cp\u003e1.4.2 Overloading and Inlining 30\u003c\/p\u003e \u003cp\u003e1.5 Classes 32\u003c\/p\u003e \u003cp\u003e1.5.1 Class Structure 33\u003c\/p\u003e \u003cp\u003e1.5.2 Constructors and Destructors 37\u003c\/p\u003e \u003cp\u003e1.5.3 Classes and Memory Allocation 40\u003c\/p\u003e \u003cp\u003e1.5.4 Class Friends and Class Members 43\u003c\/p\u003e \u003cp\u003e1.5.5 The Standard Template Library 45\u003c\/p\u003e \u003cp\u003e1.6 C++ Program and File Organization 47\u003c\/p\u003e \u003cp\u003e1.6.1 An Example Program 48\u003c\/p\u003e \u003cp\u003e1.7 Writing a C++ Program53\u003c\/p\u003e \u003cp\u003e1.7.1 Design 54\u003c\/p\u003e \u003cp\u003e1.7.2 Pseudo-Code 54\u003c\/p\u003e \u003cp\u003e1.7.3 Coding 55\u003c\/p\u003e \u003cp\u003e1.7.4 Testing and Debugging 57\u003c\/p\u003e \u003cp\u003e1.8 Exercises 60\u003c\/p\u003e \u003cp\u003e\u003cb\u003e2 Object-Oriented Design 65\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e2.1 Goals, Principles, and Patterns 66\u003c\/p\u003e \u003cp\u003e2.1.1 Object-Oriented Design Goals 66\u003c\/p\u003e \u003cp\u003e2.1.2 Object-Oriented Design Principles 67\u003c\/p\u003e \u003cp\u003e2.1.3 Design Patterns 70\u003c\/p\u003e \u003cp\u003e2.2 Inheritance and Polymorphism 71\u003c\/p\u003e \u003cp\u003e2.2.1 Inheritance in C++ 71\u003c\/p\u003e \u003cp\u003e2.2.2 Polymorphism 78\u003c\/p\u003e \u003cp\u003e2.2.3 Examples of Inheritance in C++ 79\u003c\/p\u003e \u003cp\u003e2.2.4 Multiple Inheritance and Class Casting 84\u003c\/p\u003e \u003cp\u003e2.2.5 Interfaces and Abstract Classes 87\u003c\/p\u003e \u003cp\u003e2.3 Templates 90\u003c\/p\u003e \u003cp\u003e2.3.1 Function Templates 90\u003c\/p\u003e \u003cp\u003e2.3.2 Class Templates 91\u003c\/p\u003e \u003cp\u003e2.4 Exceptions 93\u003c\/p\u003e \u003cp\u003e2.4.1 Exception Objects 93\u003c\/p\u003e \u003cp\u003e2.4.2 Throwing and Catching Exceptions 94\u003c\/p\u003e \u003cp\u003e2.4.3 Exception Specification 96\u003c\/p\u003e \u003cp\u003e2.5 Exercises 98\u003c\/p\u003e \u003cp\u003e\u003cb\u003e3 Arrays, Linked Lists, and Recursion 103\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e3.1 Using Arrays 104\u003c\/p\u003e \u003cp\u003e3.1.1 Storing Game Entries in an Array 104\u003c\/p\u003e \u003cp\u003e3.1.2 Sorting an Array 109\u003c\/p\u003e \u003cp\u003e3.1.3 Two-Dimensional Arrays and Positional Games 111\u003c\/p\u003e \u003cp\u003e3.2 Singly Linked Lists 117\u003c\/p\u003e \u003cp\u003e3.2.1 Implementing a Singly Linked List 117\u003c\/p\u003e \u003cp\u003e3.2.2 Insertion to the Front of a Singly Linked List 119\u003c\/p\u003e \u003cp\u003e3.2.3 Removal from the Front of a Singly Linked List 119\u003c\/p\u003e \u003cp\u003e3.2.4 Implementing a Generic Singly Linked List 121\u003c\/p\u003e \u003cp\u003e3.3 Doubly Linked Lists 123\u003c\/p\u003e \u003cp\u003e3.3.1 Insertion into a Doubly Linked List 123\u003c\/p\u003e \u003cp\u003e3.3.2 Removal from a Doubly Linked List 124\u003c\/p\u003e \u003cp\u003e3.3.3 A C++ Implementation 125\u003c\/p\u003e \u003cp\u003e3.4 Circularly Linked Lists and List Reversal 129\u003c\/p\u003e \u003cp\u003e3.4.1 Circularly Linked Lists 129\u003c\/p\u003e \u003cp\u003e3.4.2 Reversing a Linked List 133\u003c\/p\u003e \u003cp\u003e3.5 Recursion 134\u003c\/p\u003e \u003cp\u003e3.5.1 Linear Recursion 140\u003c\/p\u003e \u003cp\u003e3.5.2 Binary Recursion 144\u003c\/p\u003e \u003cp\u003e3.5.3 Multiple Recursion 147\u003c\/p\u003e \u003cp\u003e3.6 Exercises 149\u003c\/p\u003e \u003cp\u003e\u003cb\u003e4 Analysis Tools 153\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e4.1 The Seven Functions Used in This Book 154\u003c\/p\u003e \u003cp\u003e4.1.1 The Constant Function 154\u003c\/p\u003e \u003cp\u003e4.1.2 The Logarithm Function 154\u003c\/p\u003e \u003cp\u003e4.1.3 The Linear Function 156\u003c\/p\u003e \u003cp\u003e4.1.4 The N-Log-N Function 156\u003c\/p\u003e \u003cp\u003e4.1.5 The Quadratic Function 156\u003c\/p\u003e \u003cp\u003e4.1.6 The Cubic Function and Other Polynomials 158\u003c\/p\u003e \u003cp\u003e4.1.7 The Exponential Function 159\u003c\/p\u003e \u003cp\u003e4.1.8 Comparing Growth Rates 161\u003c\/p\u003e \u003cp\u003e4.2 Analysis of Algorithms 162\u003c\/p\u003e \u003cp\u003e4.2.1 Experimental Studies 163\u003c\/p\u003e \u003cp\u003e4.2.2 Primitive Operations 164\u003c\/p\u003e \u003cp\u003e4.2.3 Asymptotic Notation 166\u003c\/p\u003e \u003cp\u003e4.2.4 Asymptotic Analysis 170\u003c\/p\u003e \u003cp\u003e4.2.5 Using the Big-Oh Notation 172\u003c\/p\u003e \u003cp\u003e4.2.6 A Recursive Algorithm for Computing Powers 176\u003c\/p\u003e \u003cp\u003e4.2.7 Some More Examples of Algorithm Analysis 177\u003c\/p\u003e \u003cp\u003e4.3 Simple Justification Techniques 181\u003c\/p\u003e \u003cp\u003e4.3.1 By Example 181\u003c\/p\u003e \u003cp\u003e4.3.2 The “Contra” Attack 181\u003c\/p\u003e \u003cp\u003e4.3.3 Induction and Loop Invariants 182\u003c\/p\u003e \u003cp\u003e4.4 Exercises 185\u003c\/p\u003e \u003cp\u003e\u003cb\u003e5 Stacks, Queues, and Deques 193\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e5.1 Stacks 194\u003c\/p\u003e \u003cp\u003e5.1.1 The Stack Abstract Data Type 195\u003c\/p\u003e \u003cp\u003e5.1.2 The STL Stack 196\u003c\/p\u003e \u003cp\u003e5.1.3 A C++ Stack Interface 196\u003c\/p\u003e \u003cp\u003e5.1.4 A Simple Array-Based Stack Implementation 198\u003c\/p\u003e \u003cp\u003e5.1.5 Implementing a Stack with a Generic Linked List 202\u003c\/p\u003e \u003cp\u003e5.1.6 Reversing a Vector Using a Stack 203\u003c\/p\u003e \u003cp\u003e5.1.7 Matching Parentheses and HTML Tags 204\u003c\/p\u003e \u003cp\u003e5.2 Queues 208\u003c\/p\u003e \u003cp\u003e5.2.1 The Queue Abstract Data Type 208\u003c\/p\u003e \u003cp\u003e5.2.2 The STL Queue 209\u003c\/p\u003e \u003cp\u003e5.2.3 A C++ Queue Interface 210\u003c\/p\u003e \u003cp\u003e5.2.4 A Simple Array-Based Implementation 211\u003c\/p\u003e \u003cp\u003e5.2.5 Implementing a Queue with a Circularly Linked List 213\u003c\/p\u003e \u003cp\u003e5.3 Double-Ended Queues 217\u003c\/p\u003e \u003cp\u003e5.3.1 The Deque Abstract Data Type 217\u003c\/p\u003e \u003cp\u003e5.3.2 The STL Deque 218\u003c\/p\u003e \u003cp\u003e5.3.3 Implementing a Deque with a Doubly Linked List 218\u003c\/p\u003e \u003cp\u003e5.3.4 Adapters and the Adapter Design Pattern 220\u003c\/p\u003e \u003cp\u003e5.4 Exercises 223\u003c\/p\u003e \u003cp\u003e\u003cb\u003e6 List and Iterator ADTs 227\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e6.1 Vectors 228\u003c\/p\u003e \u003cp\u003e6.1.1 The Vector Abstract Data Type 228\u003c\/p\u003e \u003cp\u003e6.1.2 A Simple Array-Based Implementation 229\u003c\/p\u003e \u003cp\u003e6.1.3 An Extendable Array Implementation 231\u003c\/p\u003e \u003cp\u003e6.1.4 STL Vectors 236\u003c\/p\u003e \u003cp\u003e6.2 Lists 238\u003c\/p\u003e \u003cp\u003e6.2.1 Node-Based Operations and Iterators 238\u003c\/p\u003e \u003cp\u003e6.2.2 The List Abstract Data Type 240\u003c\/p\u003e \u003cp\u003e6.2.3 Doubly Linked List Implementation 242\u003c\/p\u003e \u003cp\u003e6.2.4 STL Lists 247\u003c\/p\u003e \u003cp\u003e6.2.5 STL Containers and Iterators 248\u003c\/p\u003e \u003cp\u003e6.3 Sequences 255\u003c\/p\u003e \u003cp\u003e6.3.1 The Sequence Abstract Data Type 255\u003c\/p\u003e \u003cp\u003e6.3.2 Implementing a Sequence with a Doubly Linked List .255\u003c\/p\u003e \u003cp\u003e6.3.3 Implementing a Sequence with an Array 257\u003c\/p\u003e \u003cp\u003e6.4 Case Study: Bubble-Sort on a Sequence 259\u003c\/p\u003e \u003cp\u003e6.4.1 The Bubble-Sort Algorithm 259\u003c\/p\u003e \u003cp\u003e6.4.2 A Sequence-Based Analysis of Bubble-Sort 260\u003c\/p\u003e \u003cp\u003e6.5 Exercises 262\u003c\/p\u003e \u003cp\u003e\u003cb\u003e7 Trees 267\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e7.1 General Trees 268\u003c\/p\u003e \u003cp\u003e7.1.1 Tree Definitions and Properties 269\u003c\/p\u003e \u003cp\u003e7.1.2 Tree Functions 272\u003c\/p\u003e \u003cp\u003e7.1.3 A C++ Tree Interface 273\u003c\/p\u003e \u003cp\u003e7.1.4 A Linked Structure for General Trees 274\u003c\/p\u003e \u003cp\u003e7.2 Tree Traversal Algorithms 275\u003c\/p\u003e \u003cp\u003e7.2.1 Depth and Height 275\u003c\/p\u003e \u003cp\u003e7.2.2 Preorder Traversal 278\u003c\/p\u003e \u003cp\u003e7.2.3 Postorder Traversal 281\u003c\/p\u003e \u003cp\u003e7.3 Binary Trees 284\u003c\/p\u003e \u003cp\u003e7.3.1 The Binary Tree ADT 285\u003c\/p\u003e \u003cp\u003e7.3.2 A C++ Binary Tree Interface 286\u003c\/p\u003e \u003cp\u003e7.3.3 Properties of Binary Trees 287\u003c\/p\u003e \u003cp\u003e7.3.4 A Linked Structure for Binary Trees 289\u003c\/p\u003e \u003cp\u003e7.3.5 A Vector-Based Structure for Binary Trees 295\u003c\/p\u003e \u003cp\u003e7.3.6 Traversals of a Binary Tree 297\u003c\/p\u003e \u003cp\u003e7.3.7 The Template Function Pattern 303\u003c\/p\u003e \u003cp\u003e7.3.8 Representing General Trees with Binary Trees 309\u003c\/p\u003e \u003cp\u003e7.4 Exercises 310\u003c\/p\u003e \u003cp\u003e\u003cb\u003e8 Heaps and Priority Queues 321\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e8.1 The Priority Queue Abstract Data Type 322\u003c\/p\u003e \u003cp\u003e8.1.1 Keys, Priorities, and Total Order Relations 322\u003c\/p\u003e \u003cp\u003e8.1.2 Comparators 324\u003c\/p\u003e \u003cp\u003e8.1.3 The Priority Queue ADT 327\u003c\/p\u003e \u003cp\u003e8.1.4 A C++ Priority Queue Interface 328\u003c\/p\u003e \u003cp\u003e8.1.5 Sorting with a Priority Queue 329\u003c\/p\u003e \u003cp\u003e8.1.6 The STL priority queue Class 330\u003c\/p\u003e \u003cp\u003e8.2 Implementing a Priority Queue with a List 331\u003c\/p\u003e \u003cp\u003e8.2.1 A C++ Priority Queue Implementation using a List 333\u003c\/p\u003e \u003cp\u003e8.2.2 Selection-Sort and Insertion-Sort 335\u003c\/p\u003e \u003cp\u003e8.3 Heaps 337\u003c\/p\u003e \u003cp\u003e8.3.1 The Heap Data Structure 337\u003c\/p\u003e \u003cp\u003e8.3.2 Complete Binary Trees and Their Representation 340\u003c\/p\u003e \u003cp\u003e8.3.3 Implementing a Priority Queue with a Heap 344\u003c\/p\u003e \u003cp\u003e8.3.4 C++ Implementation 349\u003c\/p\u003e \u003cp\u003e8.3.5 Heap-Sort 351\u003c\/p\u003e \u003cp\u003e8.3.6 Bottom-Up Heap Construction ⋆ 353\u003c\/p\u003e \u003cp\u003e8.4 Adaptable Priority Queues 357\u003c\/p\u003e \u003cp\u003e8.4.1 A List-Based Implementation 358\u003c\/p\u003e \u003cp\u003e8.4.2 Location-Aware Entries 360\u003c\/p\u003e \u003cp\u003e8.5 Exercises 361\u003c\/p\u003e \u003cp\u003e\u003cb\u003e9 Hash Tables, Maps, and Skip Lists 367\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e9.1 Maps 368\u003c\/p\u003e \u003cp\u003e9.1.1 The Map ADT 369\u003c\/p\u003e \u003cp\u003e9.1.2 A C++ Map Interface 371\u003c\/p\u003e \u003cp\u003e9.1.3 The STL map Class 372\u003c\/p\u003e \u003cp\u003e9.1.4 A Simple List-Based Map Implementation 374\u003c\/p\u003e \u003cp\u003e9.2 Hash Tables 375\u003c\/p\u003e \u003cp\u003e9.2.1 Bucket Arrays 375\u003c\/p\u003e \u003cp\u003e9.2.2 Hash Functions 376\u003c\/p\u003e \u003cp\u003e9.2.3 Hash Codes 376\u003c\/p\u003e \u003cp\u003e9.2.4 Compression Functions 380\u003c\/p\u003e \u003cp\u003e9.2.5 Collision-Handling Schemes 382\u003c\/p\u003e \u003cp\u003e9.2.6 Load Factors and Rehashing 386\u003c\/p\u003e \u003cp\u003e9.2.7 A C++ Hash Table Implementation 387\u003c\/p\u003e \u003cp\u003e9.3 Ordered Maps 394\u003c\/p\u003e \u003cp\u003e9.3.1 Ordered Search Tables and Binary Search 395\u003c\/p\u003e \u003cp\u003e9.3.2 Two Applications of Ordered Maps 399\u003c\/p\u003e \u003cp\u003e9.4 Skip Lists 402\u003c\/p\u003e \u003cp\u003e9.4.1 Search and Update Operations in a Skip List 404\u003c\/p\u003e \u003cp\u003e9.4.2 A Probabilistic Analysis of Skip Lists ⋆ 408\u003c\/p\u003e \u003cp\u003e9.5 Dictionaries 411\u003c\/p\u003e \u003cp\u003e9.5.1 The Dictionary ADT 411\u003c\/p\u003e \u003cp\u003e9.5.2 A C++ Dictionary Implementation 413\u003c\/p\u003e \u003cp\u003e9.5.3 Implementations with Location-Aware Entries 415\u003c\/p\u003e \u003cp\u003e9.6 Exercises 417\u003c\/p\u003e \u003cp\u003e\u003cb\u003e10 Search Trees 423\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e10.1 Binary Search Trees 424\u003c\/p\u003e \u003cp\u003e10.1.1 Searching 426\u003c\/p\u003e \u003cp\u003e10.1.2 Update Operations 428\u003c\/p\u003e \u003cp\u003e10.1.3 C++ Implementation of a Binary Search Tree 432\u003c\/p\u003e \u003cp\u003e10.2 AVL Trees438\u003c\/p\u003e \u003cp\u003e10.2.1 Update Operations 440\u003c\/p\u003e \u003cp\u003e10.2.2 C++ Implementation of an AVL Tree 446\u003c\/p\u003e \u003cp\u003e10.3 Splay Trees 450\u003c\/p\u003e \u003cp\u003e10.3.1 Splaying 450\u003c\/p\u003e \u003cp\u003e10.3.2 When to Splay 454\u003c\/p\u003e \u003cp\u003e10.3.3 Amortized Analysis of Splaying ⋆456\u003c\/p\u003e \u003cp\u003e10.4 (2,4) Trees 461\u003c\/p\u003e \u003cp\u003e10.4.1 Multi-Way Search Trees 461\u003c\/p\u003e \u003cp\u003e10.4.2 Update Operations for (2,4) Trees 467\u003c\/p\u003e \u003cp\u003e10.5 Red-Black Trees473\u003c\/p\u003e \u003cp\u003e10.5.1 Update Operations 475\u003c\/p\u003e \u003cp\u003e10.5.2 C++ Implementation of a Red-Black Tree 488\u003c\/p\u003e \u003cp\u003e10.6 Exercises 492\u003c\/p\u003e \u003cp\u003e\u003cb\u003e11 Sorting, Sets, and Selection 499\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e11.1 Merge-Sort500\u003c\/p\u003e \u003cp\u003e11.1.1 Divide-and-Conquer 500\u003c\/p\u003e \u003cp\u003e11.1.2 Merging Arrays and Lists 505\u003c\/p\u003e \u003cp\u003e11.1.3 The Running Time of Merge-Sort 508\u003c\/p\u003e \u003cp\u003e11.1.4 C++ Implementations of Merge-Sort 509\u003c\/p\u003e \u003cp\u003e11.1.5 Merge-Sort and Recurrence Equations ⋆ 511\u003c\/p\u003e \u003cp\u003e11.2 Quick-Sort 513\u003c\/p\u003e \u003cp\u003e11.2.1 Randomized Quick-Sort 521\u003c\/p\u003e \u003cp\u003e11.2.2 C++ Implementations and Optimizations 523\u003c\/p\u003e \u003cp\u003e11.3 Studying Sorting through an Algorithmic Lens 526\u003c\/p\u003e \u003cp\u003e11.3.1 A Lower Bound for Sorting 526\u003c\/p\u003e \u003cp\u003e11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528\u003c\/p\u003e \u003cp\u003e11.3.3 Comparing Sorting Algorithms 531\u003c\/p\u003e \u003cp\u003e11.4 Sets and Union\/Find Structures 533\u003c\/p\u003e \u003cp\u003e11.4.1 The Set ADT 533\u003c\/p\u003e \u003cp\u003e11.4.2 Mergable Sets and the Template Method Pattern 534\u003c\/p\u003e \u003cp\u003e11.4.3 Partitions with Union-Find Operations 538\u003c\/p\u003e \u003cp\u003e11.5 Selection 542\u003c\/p\u003e \u003cp\u003e11.5.1 Prune-and-Search 542\u003c\/p\u003e \u003cp\u003e11.5.2 Randomized Quick-Select 543\u003c\/p\u003e \u003cp\u003e11.5.3 Analyzing Randomized Quick-Select 544\u003c\/p\u003e \u003cp\u003e11.6 Exercises 545\u003c\/p\u003e \u003cp\u003e\u003cb\u003e12 Strings and Dynamic Programming 553\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e12.1 String Operations 554\u003c\/p\u003e \u003cp\u003e12.1.1 The STL String Class 555\u003c\/p\u003e \u003cp\u003e12.2 Dynamic Programming 557\u003c\/p\u003e \u003cp\u003e12.2.1 Matrix Chain-Product 557\u003c\/p\u003e \u003cp\u003e12.2.2 DNA and Text Sequence Alignment 560\u003c\/p\u003e \u003cp\u003e12.3 Pattern Matching Algorithms 564\u003c\/p\u003e \u003cp\u003e12.3.1 Brute Force 564\u003c\/p\u003e \u003cp\u003e12.3.2 The Boyer-Moore Algorithm 566\u003c\/p\u003e \u003cp\u003e12.3.3 The Knuth-Morris-Pratt Algorithm 570\u003c\/p\u003e \u003cp\u003e12.4 Text Compression and the Greedy Method 575\u003c\/p\u003e \u003cp\u003e12.4.1 The Huffman-Coding Algorithm 576\u003c\/p\u003e \u003cp\u003e12.4.2 The Greedy Method 577\u003c\/p\u003e \u003cp\u003e12.5 Tries 578\u003c\/p\u003e \u003cp\u003e12.5.1 Standard Tries 578\u003c\/p\u003e \u003cp\u003e12.5.2 Compressed Tries 582\u003c\/p\u003e \u003cp\u003e12.5.3 Suffix Tries 584\u003c\/p\u003e \u003cp\u003e12.5.4 Search Engines 586\u003c\/p\u003e \u003cp\u003e12.6 Exercises 587\u003c\/p\u003e \u003cp\u003e\u003cb\u003e13 Graph Algorithms 593\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e13.1 Graphs 594\u003c\/p\u003e \u003cp\u003e13.1.1 The Graph ADT 599\u003c\/p\u003e \u003cp\u003e13.2 Data Structures for Graphs 600\u003c\/p\u003e \u003cp\u003e13.2.1 The Edge List Structure 600\u003c\/p\u003e \u003cp\u003e13.2.2 The Adjacency List Structure 603\u003c\/p\u003e \u003cp\u003e13.2.3 The Adjacency Matrix Structure 605\u003c\/p\u003e \u003cp\u003e13.3 Graph Traversals 607\u003c\/p\u003e \u003cp\u003e13.3.1 Depth-First Search 607\u003c\/p\u003e \u003cp\u003e13.3.2 Implementing Depth-First Search 611\u003c\/p\u003e \u003cp\u003e13.3.3 A Generic DFS Implementation in C++ 613\u003c\/p\u003e \u003cp\u003e13.3.4 Polymorphic Objects and Decorator Values ⋆ 621\u003c\/p\u003e \u003cp\u003e13.3.5 Breadth-First Search 623\u003c\/p\u003e \u003cp\u003e13.4 Directed Graphs 626\u003c\/p\u003e \u003cp\u003e13.4.1 Traversing a Digraph 628\u003c\/p\u003e \u003cp\u003e13.4.2 Transitive Closure 630\u003c\/p\u003e \u003cp\u003e13.4.3 Directed Acyclic Graphs 633\u003c\/p\u003e \u003cp\u003e13.5 Shortest Paths 637\u003c\/p\u003e \u003cp\u003e13.5.1 Weighted Graphs 637\u003c\/p\u003e \u003cp\u003e13.5.2 Dijkstra’s Algorithm 639\u003c\/p\u003e \u003cp\u003e13.6 Minimum Spanning Trees 645\u003c\/p\u003e \u003cp\u003e13.6.1 Kruskal’s Algorithm 647\u003c\/p\u003e \u003cp\u003e13.6.2 The Prim-Jarn´ık Algorithm 651\u003c\/p\u003e \u003cp\u003e13.7 Exercises 654\u003c\/p\u003e \u003cp\u003e\u003cb\u003e14 Memory Management and B-Trees 665\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e14.1 Memory Management 666\u003c\/p\u003e \u003cp\u003e14.1.1 Memory Allocation in C++ 669\u003c\/p\u003e \u003cp\u003e14.1.2 Garbage Collection 671\u003c\/p\u003e \u003cp\u003e14.2 External Memory and Caching 673\u003c\/p\u003e \u003cp\u003e14.2.1 The Memory Hierarchy 673\u003c\/p\u003e \u003cp\u003e14.2.2 Caching Strategies 674\u003c\/p\u003e \u003cp\u003e14.3 External Searching and B-Trees679\u003c\/p\u003e \u003cp\u003e14.3.1 (a,b) Trees 680\u003c\/p\u003e \u003cp\u003e14.3.2 B-Trees 682\u003c\/p\u003e \u003cp\u003e14.4 External-Memory Sorting 683\u003c\/p\u003e \u003cp\u003e14.4.1 Multi-Way Merging 684\u003c\/p\u003e \u003cp\u003e14.5 Exercises 685\u003c\/p\u003e \u003cp\u003eA Useful Mathematical Facts 689\u003c\/p\u003e \u003cp\u003eBibliography 697\u003c\/p\u003e \u003cp\u003eIndex 702\u003c\/p\u003e \u003cdiv id=\"_mcePaste\" style=\"position: absolute; left: -10000px; top: 0px; width: 1px; height: 1px; overflow: hidden;\"\u003e \u003cp\u003e\u003cb\u003e1 A \u003c\/b\u003e\u003cb\u003eC++ \u003c\/b\u003e\u003cb\u003ePrimer 1\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e1.1 Basic C++ Programming Elements 2\u003c\/p\u003e \u003cp\u003e1.1.1 A Simple C++ Program 2\u003c\/p\u003e \u003cp\u003e1.1.2 Fundamental Types 4\u003c\/p\u003e \u003cp\u003e1.1.3 Pointers, Arrays, and Structures 7\u003c\/p\u003e \u003cp\u003e1.1.4 Named Constants, Scope, and Namespaces 13\u003c\/p\u003e \u003cp\u003e1.2 Expressions 16\u003c\/p\u003e \u003cp\u003e1.2.1 Changing Types through Casting 20\u003c\/p\u003e \u003cp\u003e1.3 Control Flow 23\u003c\/p\u003e \u003cp\u003e1.4 Functions 26\u003c\/p\u003e \u003cp\u003e1.4.1 Argument Passing 28\u003c\/p\u003e \u003cp\u003e1.4.2 Overloading and Inlining 30\u003c\/p\u003e \u003cp\u003e1.5 Classes 32\u003c\/p\u003e \u003cp\u003e1.5.1 Class Structure 33\u003c\/p\u003e \u003cp\u003e1.5.2 Constructors and Destructors 37\u003c\/p\u003e \u003cp\u003e1.5.3 Classes and Memory Allocation 40\u003c\/p\u003e \u003cp\u003e1.5.4 Class Friends and Class Members 43\u003c\/p\u003e \u003cp\u003e1.5.5 The Standard Template Library 45\u003c\/p\u003e \u003cp\u003e1.6 C++ Program and File Organization 47\u003c\/p\u003e \u003cp\u003e1.6.1 An Example Program 48\u003c\/p\u003e \u003cp\u003e1.7 Writing a C++ Program53\u003c\/p\u003e \u003cp\u003e1.7.1 Design 54\u003c\/p\u003e \u003cp\u003e1.7.2 Pseudo-Code 54\u003c\/p\u003e \u003cp\u003e1.7.3 Coding 55\u003c\/p\u003e \u003cp\u003e1.7.4 Testing and Debugging 57\u003c\/p\u003e \u003cp\u003e1.8 Exercises 60\u003c\/p\u003e \u003cp\u003e\u003cb\u003e2 Object-Oriented Design 65\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e2.1 Goals, Principles, and Patterns 66\u003c\/p\u003e \u003cp\u003e2.1.1 Object-Oriented Design Goals 66\u003c\/p\u003e \u003cp\u003e2.1.2 Object-Oriented Design Principles 67\u003c\/p\u003e \u003cp\u003e2.1.3 Design Patterns 70\u003c\/p\u003e \u003cp\u003e2.2 Inheritance and Polymorphism 71\u003c\/p\u003e \u003cp\u003e2.2.1 Inheritance in C++ 71\u003c\/p\u003e \u003cp\u003e2.2.2 Polymorphism 78\u003c\/p\u003e \u003cp\u003e2.2.3 Examples of Inheritance in C++ 79\u003c\/p\u003e \u003cp\u003e2.2.4 Multiple Inheritance and Class Casting 84\u003c\/p\u003e \u003cp\u003e2.2.5 Interfaces and Abstract Classes 87\u003c\/p\u003e \u003cp\u003e2.3 Templates 90\u003c\/p\u003e \u003cp\u003e2.3.1 Function Templates 90\u003c\/p\u003e \u003cp\u003e2.3.2 Class Templates 91\u003c\/p\u003e \u003cp\u003e2.4 Exceptions 93\u003c\/p\u003e \u003cp\u003e2.4.1 Exception Objects 93\u003c\/p\u003e \u003cp\u003e2.4.2 Throwing and Catching Exceptions 94\u003c\/p\u003e \u003cp\u003e2.4.3 Exception Specification 96\u003c\/p\u003e \u003cp\u003e2.5 Exercises 98\u003c\/p\u003e \u003cp\u003e\u003cb\u003e3 Arrays, Linked Lists, and Recursion 103\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e3.1 Using Arrays 104\u003c\/p\u003e \u003cp\u003e3.1.1 Storing Game Entries in an Array 104\u003c\/p\u003e \u003cp\u003e3.1.2 Sorting an Array 109\u003c\/p\u003e \u003cp\u003e3.1.3 Two-Dimensional Arrays and Positional Games 111\u003c\/p\u003e \u003cp\u003e3.2 Singly Linked Lists 117\u003c\/p\u003e \u003cp\u003e3.2.1 Implementing a Singly Linked List 117\u003c\/p\u003e \u003cp\u003e3.2.2 Insertion to the Front of a Singly Linked List 119\u003c\/p\u003e \u003cp\u003e3.2.3 Removal from the Front of a Singly Linked List 119\u003c\/p\u003e \u003cp\u003e3.2.4 Implementing a Generic Singly Linked List 121\u003c\/p\u003e \u003cp\u003e3.3 Doubly Linked Lists 123\u003c\/p\u003e \u003cp\u003e3.3.1 Insertion into a Doubly Linked List 123\u003c\/p\u003e \u003cp\u003e3.3.2 Removal from a Doubly Linked List 124\u003c\/p\u003e \u003cp\u003e3.3.3 A C++ Implementation 125\u003c\/p\u003e \u003cp\u003e3.4 Circularly Linked Lists and List Reversal 129\u003c\/p\u003e \u003cp\u003e3.4.1 Circularly Linked Lists 129\u003c\/p\u003e \u003cp\u003e3.4.2 Reversing a Linked List 133\u003c\/p\u003e \u003cp\u003e3.5 Recursion 134\u003c\/p\u003e \u003cp\u003e3.5.1 Linear Recursion 140\u003c\/p\u003e \u003cp\u003e3.5.2 Binary Recursion 144\u003c\/p\u003e \u003cp\u003e3.5.3 Multiple Recursion 147\u003c\/p\u003e \u003cp\u003e3.6 Exercises 149\u003c\/p\u003e \u003cp\u003e\u003cb\u003e4 Analysis Tools 153\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e4.1 The Seven Functions Used in This Book 154\u003c\/p\u003e \u003cp\u003e4.1.1 The Constant Function 154\u003c\/p\u003e \u003cp\u003e4.1.2 The Logarithm Function 154\u003c\/p\u003e \u003cp\u003e4.1.3 The Linear Function 156\u003c\/p\u003e \u003cp\u003e4.1.4 The N-Log-N Function 156\u003c\/p\u003e \u003cp\u003e4.1.5 The Quadratic Function 156\u003c\/p\u003e \u003cp\u003e4.1.6 The Cubic Function and Other Polynomials 158\u003c\/p\u003e \u003cp\u003e4.1.7 The Exponential Function 159\u003c\/p\u003e \u003cp\u003e4.1.8 Comparing Growth Rates 161\u003c\/p\u003e \u003cp\u003e4.2 Analysis of Algorithms 162\u003c\/p\u003e \u003cp\u003e4.2.1 Experimental Studies 163\u003c\/p\u003e \u003cp\u003e4.2.2 Primitive Operations 164\u003c\/p\u003e \u003cp\u003e4.2.3 Asymptotic Notation 166\u003c\/p\u003e \u003cp\u003e4.2.4 Asymptotic Analysis 170\u003c\/p\u003e \u003cp\u003e4.2.5 Using the Big-Oh Notation 172\u003c\/p\u003e \u003cp\u003e4.2.6 A Recursive Algorithm for Computing Powers 176\u003c\/p\u003e \u003cp\u003e4.2.7 Some More Examples of Algorithm Analysis 177\u003c\/p\u003e \u003cp\u003e4.3 Simple Justification Techniques 181\u003c\/p\u003e \u003cp\u003e4.3.1 By Example 181\u003c\/p\u003e \u003cp\u003e4.3.2 The “Contra” Attack 181\u003c\/p\u003e \u003cp\u003e4.3.3 Induction and Loop Invariants 182\u003c\/p\u003e \u003cp\u003e4.4 Exercises 185\u003c\/p\u003e \u003cp\u003e\u003cb\u003e5 Stacks, Queues, and Deques 193\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e5.1 Stacks 194\u003c\/p\u003e \u003cp\u003e5.1.1 The Stack Abstract Data Type 195\u003c\/p\u003e \u003cp\u003e5.1.2 The STL Stack 196\u003c\/p\u003e \u003cp\u003e5.1.3 A C++ Stack Interface 196\u003c\/p\u003e \u003cp\u003e5.1.4 A Simple Array-Based Stack Implementation 198\u003c\/p\u003e \u003cp\u003e5.1.5 Implementing a Stack with a Generic Linked List 202\u003c\/p\u003e \u003cp\u003e5.1.6 Reversing a Vector Using a Stack 203\u003c\/p\u003e \u003cp\u003e5.1.7 Matching Parentheses and HTML Tags 204\u003c\/p\u003e \u003cp\u003e5.2 Queues 208\u003c\/p\u003e \u003cp\u003e5.2.1 The Queue Abstract Data Type 208\u003c\/p\u003e \u003cp\u003e5.2.2 The STL Queue 209\u003c\/p\u003e \u003cp\u003e5.2.3 A C++ Queue Interface 210\u003c\/p\u003e \u003cp\u003e5.2.4 A Simple Array-Based Implementation 211\u003c\/p\u003e \u003cp\u003e5.2.5 Implementing a Queue with a Circularly Linked List 213\u003c\/p\u003e \u003cp\u003e5.3 Double-Ended Queues 217\u003c\/p\u003e \u003cp\u003e5.3.1 The Deque Abstract Data Type 217\u003c\/p\u003e \u003cp\u003e5.3.2 The STL Deque 218\u003c\/p\u003e \u003cp\u003e5.3.3 Implementing a Deque with a Doubly Linked List 218\u003c\/p\u003e \u003cp\u003e5.3.4 Adapters and the Adapter Design Pattern 220\u003c\/p\u003e \u003cp\u003e5.4 Exercises 223\u003c\/p\u003e \u003cp\u003e\u003cb\u003e6 List and Iterator ADTs 227\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e6.1 Vectors 228\u003c\/p\u003e \u003cp\u003e6.1.1 The Vector Abstract Data Type 228\u003c\/p\u003e \u003cp\u003e6.1.2 A Simple Array-Based Implementation 229\u003c\/p\u003e \u003cp\u003e6.1.3 An Extendable Array Implementation 231\u003c\/p\u003e \u003cp\u003e6.1.4 STL Vectors 236\u003c\/p\u003e \u003cp\u003e6.2 Lists 238\u003c\/p\u003e \u003cp\u003e6.2.1 Node-Based Operations and Iterators 238\u003c\/p\u003e \u003cp\u003e6.2.2 The List Abstract Data Type 240\u003c\/p\u003e \u003cp\u003e6.2.3 Doubly Linked List Implementation 242\u003c\/p\u003e \u003cp\u003e6.2.4 STL Lists 247\u003c\/p\u003e \u003cp\u003e6.2.5 STL Containers and Iterators 248\u003c\/p\u003e \u003cp\u003e6.3 Sequences255\u003c\/p\u003e \u003cp\u003e6.3.1 The Sequence Abstract Data Type 255\u003c\/p\u003e \u003cp\u003e6.3.2 Implementing a Sequence with a Doubly Linked List .255\u003c\/p\u003e \u003cp\u003e6.3.3 Implementing a Sequence with an Array 257\u003c\/p\u003e \u003cp\u003e6.4 Case Study: Bubble-Sort on a Sequence 259\u003c\/p\u003e \u003cp\u003e6.4.1 The Bubble-Sort Algorithm 259\u003c\/p\u003e \u003cp\u003e6.4.2 A Sequence-Based Analysis of Bubble-Sort 260\u003c\/p\u003e \u003cp\u003e6.5 Exercises 262\u003c\/p\u003e \u003cp\u003e\u003cb\u003e7 Trees 267\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e7.1 General Trees 268\u003c\/p\u003e \u003cp\u003e7.1.1 Tree Definitions and Properties 269\u003c\/p\u003e \u003cp\u003e7.1.2 Tree Functions 272\u003c\/p\u003e \u003cp\u003e7.1.3 A C++ Tree Interface 273\u003c\/p\u003e \u003cp\u003e7.1.4 A Linked Structure for General Trees 274\u003c\/p\u003e \u003cp\u003e7.2 Tree Traversal Algorithms 275\u003c\/p\u003e \u003cp\u003e7.2.1 Depth and Height 275\u003c\/p\u003e \u003cp\u003e7.2.2 Preorder Traversal 278\u003c\/p\u003e \u003cp\u003e7.2.3 Postorder Traversal 281\u003c\/p\u003e \u003cp\u003e7.3 Binary Trees 284\u003c\/p\u003e \u003cp\u003e7.3.1 The Binary Tree ADT 285\u003c\/p\u003e \u003cp\u003e7.3.2 A C++ Binary Tree Interface 286\u003c\/p\u003e \u003cp\u003e7.3.3 Properties of Binary Trees 287\u003c\/p\u003e \u003cp\u003e7.3.4 A Linked Structure for Binary Trees 289\u003c\/p\u003e \u003cp\u003e7.3.5 A Vector-Based Structure for Binary Trees 295\u003c\/p\u003e \u003cp\u003e7.3.6 Traversals of a Binary Tree 297\u003c\/p\u003e \u003cp\u003e7.3.7 The Template Function Pattern 303\u003c\/p\u003e \u003cp\u003e7.3.8 Representing General Trees with Binary Trees 309\u003c\/p\u003e \u003cp\u003e7.4 Exercises 310\u003c\/p\u003e \u003cp\u003e\u003cb\u003e8 Heaps and Priority Queues 321\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e8.1 The Priority Queue Abstract Data Type 322\u003c\/p\u003e \u003cp\u003e8.1.1 Keys, Priorities, and Total Order Relations 322\u003c\/p\u003e \u003cp\u003e8.1.2 Comparators 324\u003c\/p\u003e \u003cp\u003e8.1.3 The Priority Queue ADT 327\u003c\/p\u003e \u003cp\u003e8.1.4 A C++ Priority Queue Interface 328\u003c\/p\u003e \u003cp\u003e8.1.5 Sorting with a Priority Queue 329\u003c\/p\u003e \u003cp\u003e8.1.6 The STL priority queue Class 330\u003c\/p\u003e \u003cp\u003e8.2 Implementing a Priority Queue with a List 331\u003c\/p\u003e \u003cp\u003e8.2.1 A C++ Priority Queue Implementation using a List 333\u003c\/p\u003e \u003cp\u003e8.2.2 Selection-Sort and Insertion-Sort 335\u003c\/p\u003e \u003cp\u003e8.3 Heaps 337\u003c\/p\u003e \u003cp\u003e8.3.1 The Heap Data Structure 337\u003c\/p\u003e \u003cp\u003e8.3.2 Complete Binary Trees and Their Representation 340\u003c\/p\u003e \u003cp\u003e8.3.3 Implementing a Priority Queue with a Heap 344\u003c\/p\u003e \u003cp\u003e8.3.4 C++ Implementation 349\u003c\/p\u003e \u003cp\u003e8.3.5 Heap-Sort 351\u003c\/p\u003e \u003cp\u003e8.3.6 Bottom-Up Heap Construction ⋆353\u003c\/p\u003e \u003cp\u003e8.4 Adaptable Priority Queues 357\u003c\/p\u003e \u003cp\u003e8.4.1 A List-Based Implementation 358\u003c\/p\u003e \u003cp\u003e8.4.2 Location-Aware Entries 360\u003c\/p\u003e \u003cp\u003e8.5 Exercises 361\u003c\/p\u003e \u003cp\u003e\u003cb\u003e9 Hash Tables, Maps, and Skip Lists 367\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e9.1 Maps 368\u003c\/p\u003e \u003cp\u003e9.1.1 The Map ADT 369\u003c\/p\u003e \u003cp\u003e9.1.2 A C++ Map Interface 371\u003c\/p\u003e \u003cp\u003e9.1.3 The STL map Class 372\u003c\/p\u003e \u003cp\u003e9.1.4 A Simple List-Based Map Implementation 374\u003c\/p\u003e \u003cp\u003e9.2 Hash Tables 375\u003c\/p\u003e \u003cp\u003e9.2.1 Bucket Arrays 375\u003c\/p\u003e \u003cp\u003e9.2.2 Hash Functions 376\u003c\/p\u003e \u003cp\u003e9.2.3 Hash Codes 376\u003c\/p\u003e \u003cp\u003e9.2.4 Compression Functions 380\u003c\/p\u003e \u003cp\u003e9.2.5 Collision-Handling Schemes 382\u003c\/p\u003e \u003cp\u003e9.2.6 Load Factors and Rehashing 386\u003c\/p\u003e \u003cp\u003e9.2.7 A C++ Hash Table Implementation 387\u003c\/p\u003e \u003cp\u003e9.3 Ordered Maps 394\u003c\/p\u003e \u003cp\u003e9.3.1 Ordered Search Tables and Binary Search 395\u003c\/p\u003e \u003cp\u003e9.3.2 Two Applications of Ordered Maps 399\u003c\/p\u003e \u003cp\u003e9.4 Skip Lists 402\u003c\/p\u003e \u003cp\u003e9.4.1 Search and Update Operations in a Skip List 404\u003c\/p\u003e \u003cp\u003e9.4.2 A Probabilistic Analysis of Skip Lists ⋆408\u003c\/p\u003e \u003cp\u003e9.5 Dictionaries 411\u003c\/p\u003e \u003cp\u003e9.5.1 The Dictionary ADT 411\u003c\/p\u003e \u003cp\u003e9.5.2 A C++ Dictionary Implementation 413\u003c\/p\u003e \u003cp\u003e9.5.3 Implementations with Location-Aware Entries 415\u003c\/p\u003e \u003cp\u003e9.6 Exercises 417\u003c\/p\u003e \u003cp\u003e\u003cb\u003e10 Search Trees 423\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e10.1 Binary Search Trees 424\u003c\/p\u003e \u003cp\u003e10.1.1 Searching 426\u003c\/p\u003e \u003cp\u003e10.1.2 Update Operations 428\u003c\/p\u003e \u003cp\u003e10.1.3 C++ Implementation of a Binary Search Tree 432\u003c\/p\u003e \u003cp\u003e10.2 AVL Trees438\u003c\/p\u003e \u003cp\u003e10.2.1 Update Operations 440\u003c\/p\u003e \u003cp\u003e10.2.2 C++ Implementation of an AVL Tree 446\u003c\/p\u003e \u003cp\u003e10.3 Splay Trees 450\u003c\/p\u003e \u003cp\u003e10.3.1 Splaying 450\u003c\/p\u003e \u003cp\u003e10.3.2 When to Splay 454\u003c\/p\u003e \u003cp\u003e10.3.3 Amortized Analysis of Splaying ⋆456\u003c\/p\u003e \u003cp\u003e10.4 (2,4) Trees 461\u003c\/p\u003e \u003cp\u003e10.4.1 Multi-Way Search Trees 461\u003c\/p\u003e \u003cp\u003e10.4.2 Update Operations for (2,4) Trees 467\u003c\/p\u003e \u003cp\u003e10.5 Red-Black Trees473\u003c\/p\u003e \u003cp\u003e10.5.1 Update Operations 475\u003c\/p\u003e \u003cp\u003e10.5.2 C++ Implementation of a Red-Black Tree 488\u003c\/p\u003e \u003cp\u003e10.6 Exercises 492\u003c\/p\u003e \u003cp\u003e\u003cb\u003e11 Sorting, Sets, and Selection 499\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e11.1 Merge-Sort500\u003c\/p\u003e \u003cp\u003e11.1.1 Divide-and-Conquer 500\u003c\/p\u003e \u003cp\u003e11.1.2 Merging Arrays and Lists 505\u003c\/p\u003e \u003cp\u003e11.1.3 The Running Time of Merge-Sort 508\u003c\/p\u003e \u003cp\u003e11.1.4 C++ Implementations of Merge-Sort 509\u003c\/p\u003e \u003cp\u003e11.1.5 Merge-Sort and Recurrence Equations ⋆511\u003c\/p\u003e \u003cp\u003e11.2 Quick-Sort 513\u003c\/p\u003e \u003cp\u003e11.2.1 Randomized Quick-Sort 521\u003c\/p\u003e \u003cp\u003e11.2.2 C++ Implementations and Optimizations 523\u003c\/p\u003e \u003cp\u003e11.3 Studying Sorting through an Algorithmic Lens 526\u003c\/p\u003e \u003cp\u003e11.3.1 A Lower Bound for Sorting 526\u003c\/p\u003e \u003cp\u003e11.3.2 Linear-Time Sorting: Bucket-Sort and Radix-Sort 528\u003c\/p\u003e \u003cp\u003e11.3.3 Comparing Sorting Algorithms 531\u003c\/p\u003e \u003cp\u003e11.4 Sets and Union\/Find Structures 533\u003c\/p\u003e \u003cp\u003e11.4.1 The Set ADT 533\u003c\/p\u003e \u003cp\u003e11.4.2 Mergable Sets and the Template Method Pattern 534\u003c\/p\u003e \u003cp\u003e11.4.3 Partitions with Union-Find Operations 538\u003c\/p\u003e \u003cp\u003e11.5 Selection 542\u003c\/p\u003e \u003cp\u003e11.5.1 Prune-and-Search 542\u003c\/p\u003e \u003cp\u003e11.5.2 Randomized Quick-Select 543\u003c\/p\u003e \u003cp\u003e11.5.3 Analyzing Randomized Quick-Select 544\u003c\/p\u003e \u003cp\u003e11.6 Exercises 545\u003c\/p\u003e \u003cp\u003e\u003cb\u003e12 Strings and Dynamic Programming 553\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e12.1 String Operations 554\u003c\/p\u003e \u003cp\u003e12.1.1 The STL String Class 555\u003c\/p\u003e \u003cp\u003e12.2 Dynamic Programming 557\u003c\/p\u003e \u003cp\u003e12.2.1 Matrix Chain-Product 557\u003c\/p\u003e \u003cp\u003e12.2.2 DNA and Text Sequence Alignment 560\u003c\/p\u003e \u003cp\u003e12.3 Pattern Matching Algorithms 564\u003c\/p\u003e \u003cp\u003e12.3.1 Brute Force 564\u003c\/p\u003e \u003cp\u003e12.3.2 The Boyer-Moore Algorithm 566\u003c\/p\u003e \u003cp\u003e12.3.3 The Knuth-Morris-Pratt Algorithm 570\u003c\/p\u003e \u003cp\u003e12.4 Text Compression and the Greedy Method 575\u003c\/p\u003e \u003cp\u003e12.4.1 The Huffman-Coding Algorithm 576\u003c\/p\u003e \u003cp\u003e12.4.2 The Greedy Method 577\u003c\/p\u003e \u003cp\u003e12.5 Tries 578\u003c\/p\u003e \u003cp\u003e12.5.1 Standard Tries 578\u003c\/p\u003e \u003cp\u003e12.5.2 Compressed Tries 582\u003c\/p\u003e \u003cp\u003e12.5.3 Suffix Tries 584\u003c\/p\u003e \u003cp\u003e12.5.4 Search Engines 586\u003c\/p\u003e \u003cp\u003e12.6 Exercises 587\u003c\/p\u003e \u003cp\u003e\u003cb\u003e13 Graph Algorithms 593\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e13.1 Graphs 594\u003c\/p\u003e \u003cp\u003e13.1.1 The Graph ADT 599\u003c\/p\u003e \u003cp\u003e13.2 Data Structures for Graphs 600\u003c\/p\u003e \u003cp\u003e13.2.1 The Edge List Structure 600\u003c\/p\u003e \u003cp\u003e13.2.2 The Adjacency List Structure 603\u003c\/p\u003e \u003cp\u003e13.2.3 The Adjacency Matrix Structure 605\u003c\/p\u003e \u003cp\u003e13.3 Graph Traversals 607\u003c\/p\u003e \u003cp\u003e13.3.1 Depth-First Search 607\u003c\/p\u003e \u003cp\u003e13.3.2 Implementing Depth-First Search 611\u003c\/p\u003e \u003cp\u003e13.3.3 A Generic DFS Implementation in C++ 613\u003c\/p\u003e \u003cp\u003e13.3.4 Polymorphic Objects and Decorator Values ⋆621\u003c\/p\u003e \u003cp\u003e13.3.5 Breadth-First Search 623\u003c\/p\u003e \u003cp\u003e13.4 Directed Graphs 626\u003c\/p\u003e \u003cp\u003e13.4.1 Traversing a Digraph 628\u003c\/p\u003e \u003cp\u003e13.4.2 Transitive Closure 630\u003c\/p\u003e \u003cp\u003e13.4.3 Directed Acyclic Graphs 633\u003c\/p\u003e \u003cp\u003e13.5 Shortest Paths 637\u003c\/p\u003e \u003cp\u003e13.5.1 Weighted Graphs 637\u003c\/p\u003e \u003cp\u003e13.5.2 Dijkstra’s Algorithm 639\u003c\/p\u003e \u003cp\u003e13.6 Minimum Spanning Trees 645\u003c\/p\u003e \u003cp\u003e13.6.1 Kruskal’s Algorithm 647\u003c\/p\u003e \u003cp\u003e13.6.2 The Prim-Jarn´ık Algorithm 651\u003c\/p\u003e \u003cp\u003e13.7 Exercises 654\u003c\/p\u003e \u003cp\u003e\u003cb\u003e14 Memory Management and B-Trees 665\u003c\/b\u003e\u003c\/p\u003e \u003cp\u003e14.1 Memory Management 666\u003c\/p\u003e \u003cp\u003e14.1.1 Memory Allocation in C++ 669\u003c\/p\u003e \u003cp\u003e14.1.2 Garbage Collection 671\u003c\/p\u003e \u003cp\u003e14.2 External Memory and Caching 673\u003c\/p\u003e \u003cp\u003e14.2.1 The Memory Hierarchy 673\u003c\/p\u003e \u003cp\u003e14.2.2 Caching Strategies 674\u003c\/p\u003e \u003cp\u003e14.3 External Searching and B-Trees679\u003c\/p\u003e \u003cp\u003e14.3.1 (a,b) Trees 680\u003c\/p\u003e \u003cp\u003e14.3.2 B-Trees 682\u003c\/p\u003e \u003cp\u003e14.4 External-Memory Sorting 683\u003c\/p\u003e \u003cp\u003e14.4.1 Multi-Way Merging 684\u003c\/p\u003e \u003cp\u003e14.5 Exercises 685\u003c\/p\u003e \u003cp\u003eA Useful Mathematical Facts 689\u003c\/p\u003e \u003cp\u003eBibliography 697\u003c\/p\u003e \u003cp\u003eIndex 702\u003c\/p\u003e \u003c\/div\u003e  \u003cp\u003e\u003cstrong\u003eMichael Goodrich\u003c\/strong\u003e received his Ph.D. in computer science from Purdue University in 1987. He is currently a professor in the Department of Computer Science at University of California, Irvine. Previously, he was a professor at Johns Hopkins University. He is an editor for the \u003cem\u003eInternational Journal of Computational Geometry \u0026amp; Applications and Journal of Graph Algorithms and Applications\u003c\/em\u003e. \u003c\/p\u003e\u003cp\u003e\u003cstrong\u003eRoberto Tamassia\u003c\/strong\u003e received his Ph.D. in Electrical and Computer Engineering from the University of Illinois at Urbana-Champaign in 1988. He is currently a professor in the Department of Computer Science at Brown University. He is editor-in-chief for the \u003cem\u003eJournal of Graph Algorithms and Applications\u003c\/em\u003e and an editor for \u003cem\u003eComputational Geometry: Theory and Applications\u003c\/em\u003e. He previously served on the editorial board of \u003cem\u003eIEEE Transactions on Computers\u003c\/em\u003e.\u003c\/p\u003e","brand":"Wiley","offers":[{"title":"Default Title","offer_id":47989026226405,"sku":"NP9780470383278","price":143.5,"currency_code":"USD","in_stock":false}],"thumbnail_url":"\/\/cdn.shopify.com\/s\/files\/1\/1842\/7735\/files\/9780470383278.jpg?v=1761782490","url":"https:\/\/k12savings.com\/products\/data-structures-and-algorithms-in-c-isbn-9780470383278","provider":"K12savings","version":"1.0","type":"link"}