Bibliographic record and links to related information available from the Library of Congress catalog.
Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.
Contents Chapter 1 Introduction 1 1.1. What's the Book About? 1 1.2. Mathematics Review 3 1.2.1. Exponents 3 1.2.2. Logarithms 3 1.2.3. Series 4 1.2.4. Modular Arithmetic 5 1.2.5. The it P Word 5 1.3. A Brief Introduction to Recursion 7 1.4. C++ Classes 11 1.4.1. Basic tt class Syntax 12 1.4.2. Extra Constructor Syntax and Accessors 13 1.4.3. Separation of Interface and Implementation 15 1.4.4. tt vector and tt string 18 1.5. C++ Details 19 1.5.1. Pointers 19 1.5.2. Parameter Passing 21 1.5.3. Return Passing 22 1.5.4. Reference Variables 23 1.5.5. The Big Three: Destructor, Copy Constructor, tt operator= 23 1.5.6. The World of C 28 1.6. Templates 30 1.6.1. Function Templates 30 1.6.2. Class Templates 32 1.6.3. tt Object , tt Comparable , and an Example 34 1.7. Using Matrices 36 1.7.1. The Data Members, Constructor, and Basic Accessors 36 1.7.2. tt operator 36 1.7.3. Destructor, Copy Assignment, Copy Constructor 37 Summary 37 Exercises 37 References 39 Chapter 2 Algorithm Analysis 41 2.1. Mathematical Background 41 2.2. Model 44 2.3. What to Analyze 44 2.4. Running Time Calculations 47 2.4.1. A Simple Example 47 2.4.2. General Rules 48 2.4.3. Solutions for the Maximum Subsequence Sum Problem 50 2.4.4. Logarithms in the Running Time 56 2.4.5. Checking Your Analysis 59 2.4.6. A Grain of Salt 61 Summary 61 Exercises 62 References 67 Chapter 3 Lists, Stacks, and Queues 69 3.1. Abstract Data Types ( sc ADT s) 69 3.2. The List sc ADT 70 3.2.1. Simple Array Implementation of Lists 70 3.2.2. Linked Lists 71 3.2.3. Programming Details 72 3.2.4. Memory Reclamation and the Big Three 78 3.2.5. Doubly Linked Lists 79 3.2.6. Circular Linked Lists 80 3.2.7. Examples 81 3.2.8. Cursor Implementation of Linked Lists 86 3.3. The Stack sc ADT 93 3.3.1. Stack Model 93 3.3.2. Implementation of Stacks 93 3.3.3. Applications 100 3.4. The Queue sc ADT 110 3.4.1. Queue Model 110 3.4.2. Array Implementation of Queues 110 3.4.3. Applications of Queues 114 Summary 115 Exercises 116 Chapter 4 Trees 121 4.1. Preliminaries 121 4.1.1. Implementation of Trees 122 4.1.2. Tree Traversals with an Application 123 4.2. Binary Trees 127 4.2.1. Implementation 127 4.2.2. An Example: Expression Trees 128 4.3. The Search Tree sc ADT ---Binary Search Trees 131 4.3.1. tt find 134 4.3.2. tt findMin and tt findMax 134 4.3.3. tt insert 136 4.3.4. tt remove 137 4.3.5. Destructor and Copy Assignment Operator 139 4.3.6. Average-Case Analysis 140 4.4. sc AVL Trees 143 4.4.1. Single Rotation 145 4.4.2. Double Rotation 148 4.5. Splay Trees 155 4.5.1. A Simple Idea (That Does Not Work) 155 4.5.2. Splaying 157 4.6. Tree Traversals (Revisited) 163 4.7. B-Trees 165 Summary 170 Exercises 170 References 177 Chapter 5 Hashing 181 5.1. General Idea 181 5.2. Hash Function 182 5.3. Separate Chaining 184 5.4. Open Addressing 188 5.4.1. Linear Probing 189 5.4.2. Quadratic Probing 191 5.4.3. Double Hashing 196 5.5. Rehashing 197 5.6. Extendible Hashing 200 Summary 203 Exercises 204 References 207 Chapter 6 Priority Queues (Heaps) 211 6.1. Model 211 6.2. Simple Implementations 212 6.3. Binary Heap 213 6.3.1. Structure Property 213 6.3.2. Heap-Order Property 214 6.3.3. Basic Heap Operations 215 6.3.4. Other Heap Operations 219 6.4. Applications of Priority Queues 223 6.4.1. The Selection Problem 223 6.4.2. Event Simulation 224 6.5. $d$-Heaps 225 6.6. Leftist Heaps 226 6.6.1. Leftist Heap Property 226 6.6.2. Leftist Heap Operations 227 6.7. Skew Heaps 233 6.8. Binomial Queues 236 6.8.1. Binomial Queue Structure 236 6.8.2. Binomial Queue Operations 237 6.8.3. Implementation of Binomial Queues 240 Summary 246 Exercises 246 References 251 Chapter 7 Sorting 253 7.1. Preliminaries 253 7.2. Insertion Sort 254 7.2.1. The Algorithm 254 7.2.2. Analysis of Insertion Sort 254 7.3. A Lower Bound for Simple Sorting Algorithms 255 7.4. Shellsort 256 7.4.1. Worst-Case Analysis of Shellsort 257 7.5. Heapsort 260 7.5.1. Analysis of Heapsort 263 7.6. Mergesort 264 7.6.1. Analysis of Mergesort 266 7.7. Quicksort 269 7.7.1. Picking the Pivot 271 7.7.2. Partitioning Strategy 271 7.7.3. Small Arrays 274 7.7.4. Actual Quicksort Routines 274 7.7.5. Analysis of Quicksort 275 7.7.6. A Linear-Expected-Time Algorithm for Selection 279 7.8. Indirect Sorting 281 7.8.1. tt vector<Comparable *> Does Not Work 283 7.8.2. Smart Pointer Class 283 7.8.3. Overloading tt operator< 284 7.8.4. Dereferencing a Pointer with tt * 284 7.8.5. Overloading the Type Conversion Operator 284 7.8.6. Implicit Type Conversions Are Everywhere 285 7.8.7. Dual-Direction Implicit Conversions Can Cause Ambiguities 285 7.8.8. Pointer Subtraction Is Legal 286 7.9. A General Lower Bound for Sorting 286 7.9.1. Decision Trees 286 7.10. Bucket Sort 288 7.11. External Sorting 289 7.11.1. Why We Need New Algorithms 289 7.11.2. Model for External Sorting 289 7.11.3. The Simple Algorithm 290 7.11.4. Multiway Merge 291 7.11.5. Polyphase Merge 292 7.11.6. Replacement Selection 293 Summary 294 Exercises 295 References 300 Chapter 8 The Disjoint Set sc ADT 303 8.1. Equivalence Relations 303 8.2. The Dynamic Equivalence Problem 304 8.3. Basic Data Structure 306 8.4. Smart Union Algorithms 309 8.5. Path Compression 312 8.6. Worst Case for Union-by-Rank and Path Compression 313 8.6.1. Analysis of the Union/Find Algorithm 314 8.7. An Application 320 Summary 322 Exercises 322 References 324 Chapter 9 Graph Algorithms 327 9.1. Definitions 327 9.1.1. Representation of Graphs 328 9.2. Topological Sort 330 9.3. Shortest-Path Algorithms 333 9.3.1. Unweighted Shortest Paths 335 9.3.2. Dijkstra's Algorithm 339 9.3.3. Graphs with Negative Edge Costs 347 9.3.4. Acyclic Graphs 348 9.3.5. All-Pairs Shortest Path 351 9.4. Network Flow Problems 351 9.4.1. A Simple Maximum-Flow Algorithm 352 9.5. Minimum Spanning Tree 356 9.5.1. Prim's Algorithm 356 9.5.2. Kruskal's Algorithm 360 9.6. Applications of Depth-First Search 362 9.6.1. Undirected Graphs 362 9.6.2. Biconnectivity 363 9.6.3. Euler Circuits 368 9.6.4. Directed Graphs 371 9.6.5. Finding Strong Components 373 9.7. Introduction to NP-Completeness 374 9.7.1. Easy vs. Hard 375 9.7.2. The Class NP 376 9.7.3. NP-Complete Problems 377 Summary 379 Exercises 379 References 386 Chapter 10 Algorithm Design Techniques 391 10.1. Greedy Algorithms 391 10.1.1. A Simple Scheduling Problem 392 10.1.2. Huffman Codes 395 10.1.3. Approximate Bin Packing 401 10.2. Divide and Conquer 409 10.2.1. Running Time of Divide and Conquer Algorithms 410 10.2.2. Closest-Points Problem 412 10.2.3. The Selection Problem 416 10.2.4. Theoretical Improvements for Arithmetic Problems 419 10.3. Dynamic Programming 423 10.3.1. Using a Table Instead of Recursion 423 10.3.2. Ordering Matrix Multiplications 425 10.3.3. Optimal Binary Search Tree 429 10.3.4. All-Pairs Shortest Path 432 10.4. Randomized Algorithms 434 10.4.1. Random Number Generators 436 10.4.2. Skip Lists 440 10.4.3. Primality Testing 442 10.5. Backtracking Algorithms 444 10.5.1. The Turnpike Reconstruction Problem 445 10.5.2. Games 449 Summary 455 Exercises 455 References 464 Chapter 11 Amortized Analysis 469 11.1. An Unrelated Puzzle 470 11.2. Binomial Queues 470 11.3. Skew Heaps 475 11.4. Fibonacci Heaps 477 11.4.1. Cutting Nodes in Leftist Heaps 478 11.4.2. Lazy Merging for Binomial Queues 481 11.4.3. The Fibonacci Heap Operations 484 11.4.4. Proof of the Time Bound 485 11.5. Splay Trees 487 Summary 491 Exercises 491 References 493 Chapter 12 Advanced Data Structures and Implementation 495 12.1. Top-Down Splay Trees 495 12.2. Red-Black Trees 503 12.2.1. Bottom-Up Insertion 503 12.2.2. Top-Down Red-Black Trees 505 12.2.3. Top-Down Deletion 506 12.3. Deterministic Skip Lists 512 12.4. AA-Trees 518 12.5. Treaps 524 12.6. $k$-d Trees 527 12.7. Pairing Heaps 530 Summary 536 Exercises 536 References 540 Appendix A The Standard Template Library 543 A.1. Introduction 543 A.2. Basic sc STL Concepts 544 A.2.1. Header Files and the tt using Directive 544 A.2.2. Containers 544 A.2.3. tt iterator 545 A.2.4. Pairs 546 A.2.5. Function Objects 546 A.3. Unordered Sequences: tt vector and tt list 547 A.3.1. tt vector versus tt list 547 A.3.2. Stacks and Queues 549 A.4. Sets 550 A.5. Maps 551 A.6. Example: Generating a Concordance 552 A.6.1. sc STL Version 552 A.6.2. Version without Using the sc STL 554 A.7. Example: Shortest-Path Calculation 557 A.7.1. sc STL Implementation 557 A.7.2. Version without Using the sc STL 560 A.8. Other sc STL Features 566 Appendix B tt vector and tt string Classes 567 B.1. First-Class versus Second-Class Objects 567 B.2. tt vector Class 567 B.3. tt string Class 570 Index 577
Library of Congress Subject Headings for this publication:
C++ (Computer program language).
Data structures (Computer science).
Computer algorithms.