Data Structures and Algorithm Analysis in C++

<style>¿ </style> <p style="margin:0px;">Chapter 1 Programming: A General Overview 1</p> <p style="margin:0px;">1.1 What’s This Book About? 1</p> <p style="margin:0px;">1.2 Mathematics Review 2</p> <p style="margin:0px;">1.2.1 Exponents 3</p> <p style="margin:0px;">1.2.2 Logarithms 3</p> <p style="margin:0px;">1.2.3 Series 4</p> <p style="margin:0px;">1.2.4 Modular Arithmetic 5</p> <p style="margin:0px;">1.2.5 The P Word 6</p> <p style="margin:0px;">1.3 A Brief Introduction to Recursion 8</p> <p style="margin:0px;">1.4 C++ Classes 12</p> <p style="margin:0px;">1.4.1 Basic class Syntax 12</p> <p style="margin:0px;">1.4.2 Extra Constructor Syntax and Accessors 13</p> <p style="margin:0px;">1.4.3 Separation of Interface and Implementation 16</p> <p style="margin:0px;">1.4.4 vector and string 19</p> <p style="margin:0px;">1.5 C++ Details 21</p> <p style="margin:0px;">1.5.1 Pointers 21</p> <p style="margin:0px;">1.5.2 Lvalues, Rvalues, and References 23</p> <p style="margin:0px;">1.5.3 Parameter Passing 25</p> <p style="margin:0px;">1.5.4 Return Passing 27</p> <p style="margin:0px;">1.5.5 std::swap and std::move 29</p> <p style="margin:0px;">1.5.6 The Big-Five: Destructor, Copy Constructor, Move Constructor, Copy Assignment operator=, Move Assignment operator= 30</p> <p style="margin:0px;">1.5.7 C-style Arrays and Strings 35</p> <p style="margin:0px;">1.6 Templates 36</p> <p style="margin:0px;">1.6.1 Function Templates 37</p> <p style="margin:0px;">1.6.2 Class Templates 38</p> <p style="margin:0px;">1.6.3 Object, Comparable, and an Example 39</p> <p style="margin:0px;">1.6.4 Function Objects 41</p> <p style="margin:0px;">1.6.5 Separate Compilation of Class Templates 44</p> <p style="margin:0px;">1.7 Using Matrices 44</p> <p style="margin:0px;">1.7.1 The Data Members, Constructor, and Basic Accessors 44</p> <p style="margin:0px;">1.7.2 operator[] 45</p> <p style="margin:0px;">1.7.3 Big-Five 46</p> <p style="margin:0px;">Summary 46</p> <p style="margin:0px;">Exercises 46</p> <p style="margin:0px;">References 48</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 2 Algorithm Analysis 51</p> <p style="margin:0px;">2.1 Mathematical Background 51</p> <p style="margin:0px;">2.2 Model 54</p> <p style="margin:0px;">2.3 What to Analyze 54</p> <p style="margin:0px;">2.4 Running-Time Calculations 57</p> <p style="margin:0px;">2.4.1 A Simple Example 58</p> <p style="margin:0px;">2.4.2 General Rules 58</p> <p style="margin:0px;">2.4.3 Solutions for the Maximum Subsequence Sum Problem 60</p> <p style="margin:0px;">2.4.4 Logarithms in the Running Time 66</p> <p style="margin:0px;">2.4.5 Limitations of Worst Case Analysis 70</p> <p style="margin:0px;">Summary 70</p> <p style="margin:0px;">Exercises 71</p> <p style="margin:0px;">References 76</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 3 Lists, Stacks, and Queues 77</p> <p style="margin:0px;">3.1 Abstract Data Types (ADTs) 77</p> <p style="margin:0px;">3.2 The List ADT 78</p> <p style="margin:0px;">3.2.1 Simple Array Implementation of Lists 78</p> <p style="margin:0px;">3.2.2 Simple Linked Lists 79</p> <p style="margin:0px;">3.3 vector and list in the STL 80</p> <p style="margin:0px;">3.3.1 Iterators 82</p> <p style="margin:0px;">3.3.2 Example: Using erase on a List 83</p> <p style="margin:0px;">3.3.3 const_iterators 84</p> <p style="margin:0px;">3.4 Implementation of vector 86</p> <p style="margin:0px;">3.5 Implementation of list 91</p> <p style="margin:0px;">3.6 The Stack ADT 103</p> <p style="margin:0px;">3.6.1 Stack Model 103</p> <p style="margin:0px;">3.6.2 Implementation of Stacks 104</p> <p style="margin:0px;">3.6.3 Applications 104</p> <p style="margin:0px;">3.7 The Queue ADT 112</p> <p style="margin:0px;">3.7.1 Queue Model 113</p> <p style="margin:0px;">3.7.2 Array Implementation of Queues 113</p> <p style="margin:0px;">3.7.3 Applications of Queues 115</p> <p style="margin:0px;">Summary 116</p> <p style="margin:0px;">Exercises 116</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 4 Trees 121</p> <p style="margin:0px;">4.1 Preliminaries 121</p> <p style="margin:0px;">4.1.1 Implementation of Trees 122</p> <p style="margin:0px;">4.1.2 Tree Traversals with an Application 123</p> <p style="margin:0px;">4.2 Binary Trees 126</p> <p style="margin:0px;">4.2.1 Implementation 128</p> <p style="margin:0px;">4.2.2 An Example: Expression Trees 128</p> <p style="margin:0px;">4.3 The Search Tree ADT–Binary Search Trees 132</p> <p style="margin:0px;">4.3.1 contains 134</p> <p style="margin:0px;">4.3.2 findMin and findMax 135</p> <p style="margin:0px;">4.3.3 insert 136</p> <p style="margin:0px;">4.3.4 remove 139</p> <p style="margin:0px;">4.3.5 Destructor and Copy Constructor 141</p> <p style="margin:0px;">4.3.6 Average-Case Analysis 141</p> <p style="margin:0px;">4.4 AVL Trees 144</p> <p style="margin:0px;">4.4.1 Single Rotation 147</p> <p style="margin:0px;">4.4.2 Double Rotation 149</p> <p style="margin:0px;">4.5 Splay Trees 158</p> <p style="margin:0px;">4.5.1 A Simple Idea (That Does Not Work) 158</p> <p style="margin:0px;">4.5.2 Splaying 160</p> <p style="margin:0px;">4.6 Tree Traversals (Revisited) 166</p> <p style="margin:0px;">4.7 B-Trees 168</p> <p style="margin:0px;">4.8 Sets and Maps in the Standard Library 173</p> <p style="margin:0px;">4.8.1 Sets 173</p> <p style="margin:0px;">4.8.2 Maps 174</p> <p style="margin:0px;">4.8.3 Implementation of set and map 175</p> <p style="margin:0px;">4.8.4 An Example That Uses Several Maps 176</p> <p style="margin:0px;">Summary 181</p> <p style="margin:0px;">Exercises 182</p> <p style="margin:0px;">References 189</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 5 Hashing 193</p> <p style="margin:0px;">5.1 General Idea 193</p> <p style="margin:0px;">5.2 Hash Function 194</p> <p style="margin:0px;">5.3 Separate Chaining 196</p> <p style="margin:0px;">5.4 Hash Tables without Linked Lists 201</p> <p style="margin:0px;">5.4.1 Linear Probing 201</p> <p style="margin:0px;">5.4.2 Quadratic Probing 202</p> <p style="margin:0px;">5.4.3 Double Hashing 207</p> <p style="margin:0px;">5.5 Rehashing 208</p> <p style="margin:0px;">5.6 Hash Tables in the Standard Library 210</p> <p style="margin:0px;">5.7 Hash Tables with Worst-Case O(1) Access 212</p> <p style="margin:0px;">5.7.1 Perfect Hashing 213</p> <p style="margin:0px;">5.7.2 Cuckoo Hashing 215</p> <p style="margin:0px;">5.7.3 Hopscotch Hashing 224</p> <p style="margin:0px;">5.8 Universal Hashing 230</p> <p style="margin:0px;">5.9 Extendible Hashing 233</p> <p style="margin:0px;">Summary 236</p> <p style="margin:0px;">Exercises 238</p> <p style="margin:0px;">References 242</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 6 Priority Queues (Heaps) 245</p> <p style="margin:0px;">6.1 Model 245</p> <p style="margin:0px;">6.2 Simple Implementations 246</p> <p style="margin:0px;">6.3 Binary Heap 247</p> <p style="margin:0px;">6.3.1 Structure Property 247</p> <p style="margin:0px;">6.3.2 Heap-Order Property 248</p> <p style="margin:0px;">6.3.3 Basic Heap Operations 249</p> <p style="margin:0px;">6.3.4 Other Heap Operations 252</p> <p style="margin:0px;">6.4 Applications of Priority Queues 257</p> <p style="margin:0px;">6.4.1 The Selection Problem 258</p> <p style="margin:0px;">6.4.2 Event Simulation 259</p> <p style="margin:0px;">6.5 d-Heaps 260</p> <p style="margin:0px;">6.6 Leftist Heaps 261</p> <p style="margin:0px;">6.6.1 Leftist Heap Property 261</p> <p style="margin:0px;">6.6.2 Leftist Heap Operations 262</p> <p style="margin:0px;">6.7 Skew Heaps 269</p> <p style="margin:0px;">6.8 Binomial Queues 271</p> <p style="margin:0px;">6.8.1 Binomial Queue Structure 271</p> <p style="margin:0px;">6.8.2 Binomial Queue Operations 271</p> <p style="margin:0px;">6.8.3 Implementation of Binomial Queues 276</p> <p style="margin:0px;">6.9 Priority Queues in the Standard Library 283</p> <p style="margin:0px;">Summary 283</p> <p style="margin:0px;">Exercises 283</p> <p style="margin:0px;">References 288</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 7 Sorting 291</p> <p style="margin:0px;">7.1 Preliminaries 291</p> <p style="margin:0px;">7.2 Insertion Sort 292</p> <p style="margin:0px;">7.2.1 The Algorithm 292</p> <p style="margin:0px;">7.2.2 STL Implementation of Insertion Sort 293</p> <p style="margin:0px;">7.2.3 Analysis of Insertion Sort 294</p> <p style="margin:0px;">7.3 A Lower Bound for Simple Sorting Algorithms 295</p> <p style="margin:0px;">7.4 Shellsort 296</p> <p style="margin:0px;">7.4.1 Worst-Case Analysis of Shellsort 297</p> <p style="margin:0px;">7.5 Heapsort 300</p> <p style="margin:0px;">7.5.1 Analysis of Heapsort 301</p> <p style="margin:0px;">7.6 Mergesort 304</p> <p style="margin:0px;">7.6.1 Analysis of Mergesort 306</p> <p style="margin:0px;">7.7 Quicksort 309</p> <p style="margin:0px;">7.7.1 Picking the Pivot 311</p> <p style="margin:0px;">7.7.2 Partitioning Strategy 313</p> <p style="margin:0px;">7.7.3 Small Arrays 315</p> <p style="margin:0px;">7.7.4 Actual Quicksort Routines 315</p> <p style="margin:0px;">7.7.5 Analysis of Quicksort 318</p> <p style="margin:0px;">7.7.6 A Linear-Expected-Time Algorithm for Selection 321</p> <p style="margin:0px;">7.8 A General Lower Bound for Sorting 323</p> <p style="margin:0px;">7.8.1 Decision Trees 323</p> <p style="margin:0px;">7.9 Decision-Tree Lower Bounds for Selection Problems 325</p> <p style="margin:0px;">7.10 Adversary Lower Bounds 328</p> <p style="margin:0px;">7.11 Linear-Time Sorts: Bucket Sort and Radix Sort 331</p> <p style="margin:0px;">7.12 External Sorting 336</p> <p style="margin:0px;">7.12.1 Why We Need New Algorithms 336</p> <p style="margin:0px;">7.12.2 Model for External Sorting 336</p> <p style="margin:0px;">7.12.3 The Simple Algorithm 337</p> <p style="margin:0px;">7.12.4 Multiway Merge 338</p> <p style="margin:0px;">7.12.5 Polyphase Merge 339</p> <p style="margin:0px;">7.12.6 Replacement Selection 340</p> <p style="margin:0px;">Summary 341</p> <p style="margin:0px;">Exercises 341</p> <p style="margin:0px;">References 347</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 8 The Disjoint Sets Class 351</p> <p style="margin:0px;">8.1 Equivalence Relations 351</p> <p style="margin:0px;">8.2 The Dynamic Equivalence Problem 352</p> <p style="margin:0px;">8.3 Basic Data Structure 353</p> <p style="margin:0px;">8.4 Smart Union Algorithms 357</p> <p style="margin:0px;">8.5 Path Compression 360</p> <p style="margin:0px;">8.6 Worst Case for Union-by-Rank and Path Compression 361</p> <p style="margin:0px;">8.6.1 Slowly Growing Functions 362</p> <p style="margin:0px;">8.6.2 An Analysis by Recursive Decomposition 362</p> <p style="margin:0px;">8.6.3 An O( M log *N ) Bound 369</p> <p style="margin:0px;">8.6.4 An O( M α(M, N) ) Bound 370</p> <p style="margin:0px;">8.7 An Application 372</p> <p style="margin:0px;">Summary 374</p> <p style="margin:0px;">Exercises 375</p> <p style="margin:0px;">References 376</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 9 Graph Algorithms 379</p> <p style="margin:0px;">9.1 Definitions 379</p> <p style="margin:0px;">9.1.1 Representation of Graphs 380</p> <p style="margin:0px;">9.2 Topological Sort 382</p> <p style="margin:0px;">9.3 Shortest-Path Algorithms 386</p> <p style="margin:0px;">9.3.1 Unweighted Shortest Paths 387</p> <p style="margin:0px;">9.3.2 Dijkstra’s Algorithm 391</p> <p style="margin:0px;">9.3.3 Graphs with Negative Edge Costs 400</p> <p style="margin:0px;">9.3.4 Acyclic Graphs 400</p> <p style="margin:0px;">9.3.5 All-Pairs Shortest Path 404</p> <p style="margin:0px;">9.3.6 Shortest Path Example 404</p> <p style="margin:0px;">9.4 Network Flow Problems 406</p> <p style="margin:0px;">9.4.1 A Simple Maximum-Flow Algorithm 408</p> <p style="margin:0px;">9.5 Minimum Spanning Tree 413</p> <p style="margin:0px;">9.5.1 Prim’s Algorithm 414</p> <p style="margin:0px;">9.5.2 Kruskal’s Algorithm 417</p> <p style="margin:0px;">9.6 Applications of Depth-First Search 419</p> <p style="margin:0px;">9.6.1 Undirected Graphs 420</p> <p style="margin:0px;">9.6.2 Biconnectivity 421</p> <p style="margin:0px;">9.6.3 Euler Circuits 425</p> <p style="margin:0px;">9.6.4 Directed Graphs 429</p> <p style="margin:0px;">9.6.5 Finding Strong Components 431</p> <p style="margin:0px;">9.7 Introduction to NP-Completeness 432</p> <p style="margin:0px;">9.7.1 Easy vs. Hard 433</p> <p style="margin:0px;">9.7.2 The Class NP 434</p> <p style="margin:0px;">9.7.3 NP-Complete Problems 434</p> <p style="margin:0px;">Summary 437</p> <p style="margin:0px;">Exercises 437</p> <p style="margin:0px;">References 445</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 10 Algorithm Design Techniques 449</p> <p style="margin:0px;">10.1 Greedy Algorithms 449</p> <p style="margin:0px;">10.1.1 A Simple Scheduling Problem 450</p> <p style="margin:0px;">10.1.2 Huffman Codes 453</p> <p style="margin:0px;">10.1.3 Approximate Bin Packing 459</p> <p style="margin:0px;">10.2 Divide and Conquer 467</p> <p style="margin:0px;">10.2.1 Running Time of Divide-and-Conquer Algorithms 468</p> <p style="margin:0px;">10.2.2 Closest-Points Problem 470</p> <p style="margin:0px;">10.2.3 The Selection Problem 475</p> <p style="margin:0px;">10.2.4 Theoretical Improvements for Arithmetic Problems 478</p> <p style="margin:0px;">10.3 Dynamic Programming 482</p> <p style="margin:0px;">10.3.1 Using a Table Instead of Recursion 483</p> <p style="margin:0px;">10.3.2 Ordering Matrix Multiplications 485</p> <p style="margin:0px;">10.3.3 Optimal Binary Search Tree 487</p> <p style="margin:0px;">10.3.4 All-Pairs Shortest Path 491</p> <p style="margin:0px;">10.4 Randomized Algorithms 494</p> <p style="margin:0px;">10.4.1 Random-Number Generators 495</p> <p style="margin:0px;">10.4.2 Skip Lists 500</p> <p style="margin:0px;">10.4.3 Primality Testing 503</p> <p style="margin:0px;">10.5 Backtracking Algorithms 506</p> <p style="margin:0px;">10.5.1 The Turnpike Reconstruction Problem 506</p> <p style="margin:0px;">10.5.2 Games 511</p> <p style="margin:0px;">Summary 518</p> <p style="margin:0px;">Exercises 518</p> <p style="margin:0px;">References 527</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 11 Amortized Analysis 533</p> <p style="margin:0px;">11.1 An Unrelated Puzzle 534</p> <p style="margin:0px;">11.2 Binomial Queues 534</p> <p style="margin:0px;">11.3 Skew Heaps 539</p> <p style="margin:0px;">11.4 Fibonacci Heaps 541</p> <p style="margin:0px;">11.4.1 Cutting Nodes in Leftist Heaps 542</p> <p style="margin:0px;">11.4.2 Lazy Merging for Binomial Queues 544</p> <p style="margin:0px;">11.4.3 The Fibonacci Heap Operations 548</p> <p style="margin:0px;">11.4.4 Proof of the Time Bound 549</p> <p style="margin:0px;">11.5 Splay Trees 551</p> <p style="margin:0px;">Summary 555</p> <p style="margin:0px;">Exercises 556</p> <p style="margin:0px;">References 557</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Chapter 12 Advanced Data Structures and Implementation 559</p> <p style="margin:0px;">12.1 Top-Down Splay Trees 559</p> <p style="margin:0px;">12.2 Red-Black Trees 566</p> <p style="margin:0px;">12.2.1 Bottom-Up Insertion 567</p> <p style="margin:0px;">12.2.2 Top-Down Red-Black Trees 568</p> <p style="margin:0px;">12.2.3 Top-Down Deletion 570</p> <p style="margin:0px;">12.3 Treaps 576</p> <p style="margin:0px;">12.4 Suffix Arrays and Suffix Trees 579</p> <p style="margin:0px;">12.4.1 Suffix Arrays 580</p> <p style="margin:0px;">12.4.2 Suffix Trees 583</p> <p style="margin:0px;">12.4.3 Linear-Time Construction of Suffix Arrays and Suffix Trees 586</p> <p style="margin:0px;">12.5 k-d Trees 596</p> <p style="margin:0px;">12.6 Pairing Heaps 602</p> <p style="margin:0px;">Summary 606</p> <p style="margin:0px;">Exercises 608</p> <p style="margin:0px;">References 612</p> <p style="margin:0px;">&nbsp;</p> <p style="margin:0px;">Appendix A Separate Compilation of Class Templates 615</p> <p style="margin:0px;">A.1 Everything in the Header 616</p> <p style="margin:0px;">A.2 Explicit Instantiation 616</p> <p style="margin:0px;">Index 619</p>