Data structures and algorithm analysis in C++

methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from centuries to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored. Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. This book is suitable for either an advanced data structures course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers, recursion, and object-based programming, as well as some background in discrete math. Cover 1 Title Page 4 Copyright Page 5 Contents 8 Preface 16 Chapter 1 Programming: A General Overview 20 1.1 What’s This Book About? 20 1.2 Mathematics Review 21 1.2.1 Exponents 22 1.2.2 Logarithms 22 1.2.3 Series 23 1.2.4 Modular Arithmetic 24 1.2.5 The P Word 25 1.3 A Brief Introduction to Recursion 27 1.4 C++ Classes 31 1.4.1 Basic class Syntax 31 1.4.2 Extra Constructor Syntax and Accessors 32 1.4.3 Separation of Interface and Implementation 35 1.4.4 vector and string 38 1.5 C++ Details 40 1.5.1 Pointers 40 1.5.2 Lvalues, Rvalues, and References 42 1.5.3 Parameter Passing 44 1.5.4 Return Passing 46 1.5.5 std::swap and std::move 48 1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 49 1.5.7 C-style Arrays and Strings 54 1.6 Templates 55 1.6.1 Function Templates 56 1.6.2 Class Templates 57 1.6.3 Object, Comparable, and an Example 58 1.6.4 Function Objects 60 1.6.5 Separate Compilation of Class Templates 63 1.7 Using Matrices 63 1.7.1 The Data Members, Constructor, and Basic Accessors 63 1.7.2 operator[] 64 1.7.3 Big-Five 65 Summary 65 Exercises 65 References 67 Chapter 2 Algorithm Analysis 70 2.1 Mathematical Background 70 2.2 Model 73 2.3 What to Analyze 73 2.4 Running-Time Calculations 76 2.4.1 A Simple Example 77 2.4.2 General Rules 77 2.4.3 Solutions for the Maximum Subsequence Sum Problem 79 2.4.4 Logarithms in the Running Time 85 2.4.5 Limitations of Worst-Case Analysis 89 Summary 89 Exercises 90 References 95 Chapter 3 Lists, Stacks, and Queues 96 3.1 Abstract Data Types (ADTs) 96 3.2 The List ADT 97 3.2.1 Simple Array Implementation of Lists 97 3.2.2 Simple Linked Lists 98 3.3 vector and list in the STL 99 3.3.1 Iterators 101 3.3.2 Example: Using erase on a List 102 3.3.3 const_iterators 103 3.4 Implementation of vector 105 3.5 Implementation of list 110 3.6 The Stack ADT 122 3.6.1 Stack Model 122 3.6.2 Implementation of Stacks 123 3.6.3 Applications 123 3.7 The Queue ADT 131 3.7.1 Queue Model 132 3.7.2 Array Implementation of Queues 132 3.7.3 Applications of Queues 134 Summary 135 Exercises 135 Chapter 4 Trees 140 4.1 Preliminaries 140 4.1.1 Implementation of Trees 141 4.1.2 Tree Traversals with an Application 142 4.2 Binary Trees 145 4.2.1 Implementation 147 4.2.2 An Example: Expression Trees 147 4.3 The Search Tree ADT—Binary Search Trees 151 4.3.1 contains 153 4.3.2 findMin and findMax 154 4.3.3 insert 155 4.3.4 remove 158 4.3.5 Destructor and Copy Constructor 160 4.3.6 Average-Case Analysis 160 4.4 AVL Trees 163 4.4.1 Single Rotation 166 4.4.2 Double Rotation 168 4.5 Splay Trees 177 4.5.1 A Simple Idea (That Does Not Work) 177 4.5.2 Splaying 179 4.6 Tree Traversals (Revisited) 185 4.7 B-Trees 187 4.8 Sets and Maps in the Standard Library 192 4.8.1 Sets 192 4.8.2 Maps 193 4.8.3 Implementation of set and map 194 4.8.4 An Example That Uses Several Maps 195 Summary 200 Exercises 201 References 208 Chapter 5 Hashing 212 5.1 General Idea 212 5.2 Hash Function 213 5.3 Separate Chaining 215 5.4 Hash Tables without Linked Lists 220 5.4.1 Linear Probing 220 5.4.2 Quadratic Probing 221 5.4.3 Double Hashing 226 5.5 Rehashing 227 5.6 Hash Tables in the Standard Library 229 5.7 Hash Tables with Worst-Case O(1) Access 231 5.7.1 Perfect Hashing 232 5.7.2 Cuckoo Hashing 234 5.7.3 Hopscotch Hashing 246 5.8 Universal Hashing 249 5.9 Extendible Hashing 252 Summary 255 Exercises 256 References 260 Chapter 6 Priority Queues (Heaps) 264 6.1 Model 264 6.2 Simple Implementations 265 6.3 Binary Heap 266 6.3.1 Structure Property 266 6.3.2 Heap-Order Property 267 6.3.3 Basic Heap Operations 268 6.3.4 Other Heap Operations 271 6.4 Applications of Priority Queues 276 6.4.1 The Selection Problem 277 6.4.2 Event Simulation 278 6.5 d-Heaps 279 6.6 Leftist Heaps 280 6.6.1 Leftist Heap Property 280 6.6.2 Leftist Heap Operations 281 6.7 Skew Heaps 288 6.8 Binomial Queues 290 6.8.1 Binomial Queue Structure 290 6.8.2 Binomial Queue Operations 290 6.8.3 Implementation of Binomial Queues 295 6.9 Priority Queues in the Standard Library 301 Summary 302 Exercises 302 References 307 Chapter 7 Sorting 310 7.1 Preliminaries 310 7.2 Insertion Sort 311 7.2.1 The Algorithm 311 7.2.2 STL Implementation of Insertion Sort 312 7.2.3 Analysis of Insertion Sort 313 7.3 A Lower Bound for Simple Sorting Algorithms 314 7.4 Shellsort 315 7.4.1 Worst-Case Analysis of Shellsort 316 7.5 Heapsort 319 7.5.1 Analysis of Heapsort 320 7.6 Mergesort 323 7.6.1 Analysis of Mergesort 325 7.7 Quicksort 328 7.7.1 Picking the Pivot 330 7.7.2 Partitioning Strategy 332 7.7.3 Small Arrays 334 7.7.4 Actual Quicksort Routines 334 7.7.5 Analysis of Quicksort 337 7.7.6 A Linear-Expected-Time Algorithm for Selection 340 7.8 A General Lower Bound for Sorting 342 7.8.1 Decision Trees 342 7.9 Decision-Tree Lower Bounds for Selection Problems 344 7.10 Adversary Lower Bounds 347 7.11 Linear-Time Sorts: Bucket Sort and Radix Sort 350 7.12 External Sorting 355 7.12.1 Why We Need New Algorithms 355 7.12.2 Model for External Sorting 355 7.12.3 The Simple Algorithm 356 7.12.4 Multiway Merge 357 7.12.5 Polyphase Merge 358 7.12.6 Replacement Selection 359 Summary 360 Exercises 360 References 366 Chapter 8 The Disjoint Sets Class 370 8.1 Equivalence Relations 370 8.2 The Dynamic Equivalence Problem 371 8.3 Basic Data Structure 372 8.4 Smart Union Algorithms 376 8.5 Path Compression 379 8.6 Worst Case for Union-by-Rank and Path Compression 380 8.6.1 Slowly Growing Functions 381 8.6.2 An Analysis by Recursive Decomposition 381 8.6.3 An O( M log *N ) Bound 388 8.6.4 An O( M α(M, N) ) Bound 389 8.7 An Application 391 Summary 393 Exercises 394 References 395 Chapter 9 Graph Algorithms 398 9.1 Definitions 398 9.1.1 Representation of Graphs 399 9.2 Topological Sort 401 9.3 Shortest-Path Algorithms 405 9.3.1 Unweighted Shortest Paths 406 9.3.2 Dijkstra’s Algorithm 410 9.3.3 Graphs with Negative Edge Costs 419 9.3.4 Acyclic Graphs 419 9.3.5 All-Pairs Shortest Path 423 9.3.6 Shortest Path Example 423 9.4 Network Flow Problems 425 9.4.1 A Simple Maximum-Flow Algorithm 427 9.5 Minimum Spanning Tree 432 9.5.1 Prim’s Algorithm 433 9.5.2 Kruskal’s Algorithm 436 9.6 Applications of Depth-First Search 438 9.6.1 Undirected Graphs 439 9.6.2 Biconnectivity 440 9.6.3 Euler Circuits 444 9.6.4 Directed Graphs 448 9.6.5 Finding Strong Components 450 9.7 Introduction to NP-Completeness 451 9.7.1 Easy vs. Hard 452 9.7.2 The Class NP 453 9.7.3 NP-Complete Problems 453 Summary 456 Exercises 456 References 464 Chapter 10 Algorithm Design Techniques 468 10.1 Greedy Algorithms 468 10.1.1 A Simple Scheduling Problem 469 10.1.2 Huffman Codes 472 10.1.3 Approximate Bin Packing 478 10.2 Divide and Conquer 486 10.2.1 Running Time of Divide-and-Conquer Algorithms 487 10.2.2 Closest-Points Problem 489 10.2.3 The Selection Problem 494 10.2.4 Theoretical Improvements for Arithmetic Problems 497 10.3 Dynamic Programming 501 10.3.1 Using a Table Instead of Recursion 502 10.3.2 Ordering Matrix Multiplications 504 10.3.3 Optimal Binary Search Tree 506 10.3.4 All-Pairs Shortest Path 510 10.4 Randomized Algorithms 513 10.4.1 Random-Number Generators 514 10.4.2 Skip Lists 519 10.4.3 Primality Testing 522 10.5 Backtracking Algorithms 525 10.5.1 The Turnpike Reconstruction Problem 525 10.5.2 Games 530 Summary 537 Exercises 537 References 546 Chapter 11 Amortized Analysis 552 11.1 An Unrelated Puzzle 553 11.2 Binomial Queues 553 11.3 Skew Heaps 558 11.4 Fibonacci Heaps 560 11.4.1 Cutting Nodes in Leftist Heaps 561 11.4.2 Lazy Merging for Binomial Queues 563 11.4.3 The Fibonacci Heap Operations 567 11.4.4 Proof of the Time Bound 568 11.5 Splay Trees 570 Summary 574 Exercises 575 References 576 Chapter 12 Advanced Data Structures and Implementation 578 12.1 Top-Down Splay Trees 578 12.2 Red-Black Trees 585 12.2.1 Bottom-Up Insertion 586 12.2.2 Top-Down Red-Black Trees 587 12.2.3 Top-Down Deletion 589 12.3 Treaps 595 12.4 Sufix Arrays and Sufix Trees 598 12.4.1 Sufix Arrays 599 12.4.2 Sufix Trees 602 12.4.3 Linear-Time Construction of Sufix Arrays and Sufix Trees 605 12.5 k-d Trees 615 12.6 Pairing Heaps 621 Summary 625 Exercises 627 References 631 Appendix A: Separate Compilation of Class Templates 634 A.1 Everything in the Header 635 A.2 Explicit Instantiation 635 Index 638 A 638 B 639 C 640 D 641 E 642 F 643 G 644 H 644 I 645 J 645 K 645 L 646 M 646 N 647 O 648 P 648 Q 650 R 650 S 651 T 653 U 653 V 654 W 654 X 654 Y 654 Z 654

Data Structures and Algorithm Analysis in C++ is an advanced algorithms book that bridges the gap between traditional CS2 and Algorithms Analysis courses.

As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs using the C++ programming language.

This book explains topics from binary heaps to sorting to NP-completeness, and dedicates a full chapter to amortized analysis and advanced data structures and their implementation. Figures and examples illustrating successive stages of algorithms contribute to Weiss’ careful, rigorous and in-depth analysis of each type of algorithm.

Data structures and algorithm analysis in C++ is an advanced algorithms book that bridges the gap between traditional CS2 and Algorithms Analysis courses. As the speed and power of computers increases, so does the need for effective programming and algorithm analysis. By approaching these skills in tandem, Mark Allen Weiss teaches readers to develop well-constructed, maximally efficient programs using the C++ programming language