Data Structures and Algorithm Analysis in C++

Mark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelor’s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.Professor Weiss is the author of numerous publications in top-rated journals and was recipient of the University’s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually.In addition to his Research Award in 1994, Professor Weiss is also the recipient of the University’s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007).

• Chapter 1 Programming: A General Overview 11.1 What’s This Book About? 11.2 Mathematics Review 21.2.1 Exponents 31.2.2 Logarithms 31.2.3 Series 41.2.4 Modular Arithmetic 51.2.5 The P Word 61.3 A Brief Introduction to Recursion 81.4 C++ Classes 121.4.1 Basic class Syntax 121.4.2 Extra Constructor Syntax and Accessors 131.4.3 Separation of Interface and Implementation 161.4.4 vector and string 191.5 C++ Details 211.5.1 Pointers 211.5.2 Lvalues, Rvalues, and References 231.5.3 Parameter Passing 251.5.4 Return Passing 271.5.5 std::swap and std::move 291.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 301.5.7 C-style Arrays and Strings 351.6 Templates 361.6.1 Function Templates 371.6.2 Class Templates 381.6.3 Object, Comparable, and an Example 391.6.4 Function Objects 411.6.5 Separate Compilation of Class Templates 441.7 Using Matrices 441.7.1 The Data Members, Constructor, and Basic Accessors 441.7.2 operator[] 451.7.3 Big-Five 46Summary 46Exercises 46References 48  Chapter 2 Algorithm Analysis 512.1 Mathematical Background 512.2 Model 542.3 What to Analyze 542.4 Running-Time Calculations 572.4.1 A Simple Example 582.4.2 General Rules 582.4.3 Solutions for the Maximum Subsequence Sum Problem 602.4.4 Logarithms in the Running Time 662.4.5 Limitations of Worst Case Analysis 70Summary 70Exercises 71References 76  Chapter 3 Lists, Stacks, and Queues 773.1 Abstract Data Types (ADTs) 773.2 The List ADT 783.2.1 Simple Array Implementation of Lists 783.2.2 Simple Linked Lists 793.3 vector and list in the STL 803.3.1 Iterators 823.3.2 Example: Using erase on a List 833.3.3 const_iterators 843.4 Implementation of vector 863.5 Implementation of list 913.6 The Stack ADT 1033.6.1 Stack Model 1033.6.2 Implementation of Stacks 1043.6.3 Applications 1043.7 The Queue ADT 1123.7.1 Queue Model 1133.7.2 Array Implementation of Queues 1133.7.3 Applications of Queues 115Summary 116Exercises 116  Chapter 4 Trees 1214.1 Preliminaries 1214.1.1 Implementation of Trees 1224.1.2 Tree Traversals with an Application 1234.2 Binary Trees 1264.2.1 Implementation 1284.2.2 An Example: Expression Trees 1284.3 The Search Tree ADT–Binary Search Trees 1324.3.1 contains 1344.3.2 findMin and findMax 1354.3.3 insert 1364.3.4 remove 1394.3.5 Destructor and Copy Constructor 1414.3.6 Average-Case Analysis 1414.4 AVL Trees 1444.4.1 Single Rotation 1474.4.2 Double Rotation 1494.5 Splay Trees 1584.5.1 A Simple Idea (That Does Not Work) 1584.5.2 Splaying 1604.6 Tree Traversals (Revisited) 1664.7 B-Trees 1684.8 Sets and Maps in the Standard Library 1734.8.1 Sets 1734.8.2 Maps 1744.8.3 Implementation of set and map 1754.8.4 An Example That Uses Several Maps 176Summary 181Exercises 182References 189  Chapter 5 Hashing 1935.1 General Idea 1935.2 Hash Function 1945.3 Separate Chaining 1965.4 Hash Tables without Linked Lists 2015.4.1 Linear Probing 2015.4.2 Quadratic Probing 2025.4.3 Double Hashing 2075.5 Rehashing 2085.6 Hash Tables in the Standard Library 2105.7 Hash Tables with Worst-Case O(1) Access 2125.7.1 Perfect Hashing 2135.7.2 Cuckoo Hashing 2155.7.3 Hopscotch Hashing 2245.8 Universal Hashing 2305.9 Extendible Hashing 233Summary 236Exercises 238References 242  Chapter 6 Priority Queues (Heaps) 2456.1 Model 2456.2 Simple Implementations 2466.3 Binary Heap 2476.3.1 Structure Property 2476.3.2 Heap-Order Property 2486.3.3 Basic Heap Operations 2496.3.4 Other Heap Operations 2526.4 Applications of Priority Queues 2576.4.1 The Selection Problem 2586.4.2 Event Simulation 2596.5 d-Heaps 2606.6 Leftist Heaps 2616.6.1 Leftist Heap Property 2616.6.2 Leftist Heap Operations 2626.7 Skew Heaps 2696.8 Binomial Queues 2716.8.1 Binomial Queue Structure 2716.8.2 Binomial Queue Operations 2716.8.3 Implementation of Binomial Queues 2766.9 Priority Queues in the Standard Library 283Summary 283Exercises 283References 288  Chapter 7 Sorting 2917.1 Preliminaries 2917.2 Insertion Sort 2927.2.1 The Algorithm 2927.2.2 STL Implementation of Insertion Sort 2937.2.3 Analysis of Insertion Sort 2947.3 A Lower Bound for Simple Sorting Algorithms 2957.4 Shellsort 2967.4.1 Worst-Case Analysis of Shellsort 2977.5 Heapsort 3007.5.1 Analysis of Heapsort 3017.6 Mergesort 3047.6.1 Analysis of Mergesort 3067.7 Quicksort 3097.7.1 Picking the Pivot 3117.7.2 Partitioning Strategy 3137.7.3 Small Arrays 3157.7.4 Actual Quicksort Routines 3157.7.5 Analysis of Quicksort 3187.7.6 A Linear-Expected-Time Algorithm for Selection 3217.8 A General Lower Bound for Sorting 3237.8.1 Decision Trees 3237.9 Decision-Tree Lower Bounds for Selection Problems 3257.10 Adversary Lower Bounds 3287.11 Linear-Time Sorts: Bucket Sort and Radix Sort 3317.12 External Sorting 3367.12.1 Why We Need New Algorithms 3367.12.2 Model for External Sorting 3367.12.3 The Simple Algorithm 3377.12.4 Multiway Merge 3387.12.5 Polyphase Merge 3397.12.6 Replacement Selection 340Summary 341Exercises 341References 347  Chapter 8 The Disjoint Sets Class 3518.1 Equivalence Relations 3518.2 The Dynamic Equivalence Problem 3528.3 Basic Data Structure 3538.4 Smart Union Algorithms 3578.5 Path Compression 3608.6 Worst Case for Union-by-Rank and Path Compression 3618.6.1 Slowly Growing Functions 3628.6.2 An Analysis by Recursive Decomposition 3628.6.3 An O( M log *N ) Bound 3698.6.4 An O( M α(M, N) ) Bound 3708.7 An Application 372Summary 374Exercises 375References 376  Chapter 9 Graph Algorithms 3799.1 Definitions 3799.1.1 Representation of Graphs 3809.2 Topological Sort 3829.3 Shortest-Path Algorithms 3869.3.1 Unweighted Shortest Paths 3879.3.2 Dijkstra’s Algorithm 3919.3.3 Graphs with Negative Edge Costs 4009.3.4 Acyclic Graphs 4009.3.5 All-Pairs Shortest Path 4049.3.6 Shortest Path Example 4049.4 Network Flow Problems 4069.4.1 A Simple Maximum-Flow Algorithm 4089.5 Minimum Spanning Tree 4139.5.1 Prim’s Algorithm 4149.5.2 Kruskal’s Algorithm 4179.6 Applications of Depth-First Search 4199.6.1 Undirected Graphs 4209.6.2 Biconnectivity 4219.6.3 Euler Circuits 4259.6.4 Directed Graphs 4299.6.5 Finding Strong Components 4319.7 Introduction to NP-Completeness 4329.7.1 Easy vs. Hard 4339.7.2 The Class NP 4349.7.3 NP-Complete Problems 434Summary 437Exercises 437References 445  Chapter 10 Algorithm Design Techniques 44910.1 Greedy Algorithms 44910.1.1 A Simple Scheduling Problem 45010.1.2 Huffman Codes 45310.1.3 Approximate Bin Packing 45910.2 Divide and Conquer 46710.2.1 Running Time of Divide-and-Conquer Algorithms 46810.2.2 Closest-Points Problem 47010.2.3 The Selection Problem 47510.2.4 Theoretical Improvements for Arithmetic Problems 47810.3 Dynamic Programming 48210.3.1 Using a Table Instead of Recursion 48310.3.2 Ordering Matrix Multiplications 48510.3.3 Optimal Binary Search Tree 48710.3.4 All-Pairs Shortest Path 49110.4 Randomized Algorithms 49410.4.1 Random-Number Generators 49510.4.2 Skip Lists 50010.4.3 Primality Testing 50310.5 Backtracking Algorithms 50610.5.1 The Turnpike Reconstruction Problem 50610.5.2 Games 511Summary 518Exercises 518References 527  Chapter 11 Amortized Analysis 53311.1 An Unrelated Puzzle 53411.2 Binomial Queues 53411.3 Skew Heaps 53911.4 Fibonacci Heaps 54111.4.1 Cutting Nodes in Leftist Heaps 54211.4.2 Lazy Merging for Binomial Queues 54411.4.3 The Fibonacci Heap Operations 54811.4.4 Proof of the Time Bound 54911.5 Splay Trees 551Summary 555Exercises 556References 557  Chapter 12 Advanced Data Structures and Implementation 55912.1 Top-Down Splay Trees 55912.2 Red-Black Trees 56612.2.1 Bottom-Up Insertion 56712.2.2 Top-Down Red-Black Trees 56812.2.3 Top-Down Deletion 57012.3 Treaps 57612.4 Suffix Arrays and Suffix Trees 57912.4.1 Suffix Arrays 58012.4.2 Suffix Trees 58312.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees 58612.5 k-d Trees 59612.6 Pairing Heaps 602Summary 606Exercises 608References 612  Appendix A Separate Compilation of Class Templates 615A.1 Everything in the Header 616A.2 Explicit Instantiation 616Index 619