

1  (40) 

1.1. What's the Book About? 


1  (2) 


3  (4) 


3  (1) 


3  (1) 


4  (1) 

1.2.4. Modular Arithmetic 


5  (1) 


5  (2) 

1.3. A Brief Introduction to Recursion 


7  (4) 


11  (8) 

1.4.1. Basic class Syntax 


12  (1) 

1.4.2. Extra Constructor Syntax and Accessors 


13  (2) 

1.4.3. Separation of Interface and Implementation 


15  (3) 


18  (1) 


19  (11) 


19  (2) 


21  (1) 


22  (1) 

1.5.4. Reference Variables 


23  (1) 

1.5.5. The Big Three: Destructor, Copy Constructor, operator= 


23  (5) 


28  (2) 


30  (6) 

1.6.1. Function Templates 


30  (2) 


32  (2) 

1.6.3. Object, Comparable, and an Example 


34  (2) 


36  (1) 

1.7.1. The Data Members, Constructor, and Basic Accessors 


36  (1) 


36  (1) 

1.7.3. Destructor, Copy Assignment, Copy Constructor 


37  (1) 


37  (1) 


37  (2) 


39  (2) 

Chapter 2 Algorithm Analysis 


41  (28) 

2.1. Mathematical Background 


41  (3) 


44  (1) 


44  (3) 

2.4. Running Time Calculations 


47  (14) 


47  (1) 


48  (2) 

2.4.3. Solutions for the Maximum Subsequence Sum Problem 


50  (6) 

2.4.4. Logarithms in the Running Time 


56  (3) 

2.4.5. Checking Your Analysis 


59  (2) 


61  (1) 


61  (1) 


62  (5) 


67  (2) 

Chapter 3 Lists, Stacks, and Queues 


69  (52) 

3.1. Abstract Data Types (ADTs) 


69  (1) 


70  (23) 

3.2.1. Simple Array Implementation of Lists 


70  (1) 


71  (1) 

3.2.3. Programming Details 


72  (6) 

3.2.4. Memory Reclamation and the Big Three 


78  (1) 

3.2.5. Doubly Linked Lists 


79  (1) 

3.2.6. Circular Linked Lists 


80  (1) 


81  (5) 

3.2.8. Cursor Implementation of Linked Lists 


86  (7) 


93  (17) 


93  (1) 

3.3.2. Implementation of Stacks 


93  (1) 


100  (10) 


110  (5) 


110  (1) 

3.4.2. Array Implementation of Queues 


110  (4) 

3.4.3. Applications of Queues 


114  (1) 


115  (1) 


116  (5) 


121  (60) 


121  (6) 

4.1.1. Implementation of Trees 


122  (1) 

4.1.2. Tree Traversals with and Application 


123  (4) 


127  (4) 


127  (1) 

4.2.2. An Example: Expression Trees 


128  (3) 

4.3. The Search Tree ADTBinary Search Trees 


131  (12) 


134  (1) 

4.3.2. findMin and findMax 


134  (2) 


136  (1) 


137  (2) 

4.3.5. Destructor and Copy Assignment Operator 


139  (1) 

4.3.6. AverageCase Analysis 


140  (3) 


143  (12) 


145  (3) 


148  (7) 


155  (8) 

4.5.1. A Simple Idea (That Does Not Work) 


155  (2) 


157  (6) 

4.6. Tree Traversals (Revisited) 


163  (2) 


165  (5) 


170  (1) 


170  (7) 


177  (4) 


181  (30) 


181  (1) 


182  (2) 


184  (4) 


188  (9) 


189  (2) 


191  (5) 


196  (1) 


197  (3) 


200  (3) 


203  (1) 


204  (3) 


207  (4) 

Chapter 6 Priority Queues (Heaps) 


211  (42) 


211  (1) 

6.2. Simple Implementations 


212  (1) 


213  (10) 

6.3.1. Structure Property 


213  (1) 

6.3.2. HeapOrder Property 


214  (1) 

6.3.3. Basic Heap Operations 


215  (4) 

6.3.4. Other Heap Operations 


219  (4) 

6.4. Applications of Priority Queues 


223  (2) 

6.4.1. The Selection Problem 


223  (1) 


224  (1) 


225  (1) 


226  (7) 

6.6.1. Leftist Heap Property 


226  (1) 

6.6.2. Leftist Heap Operations 


227  (6) 


233  (3) 


236  (10) 

6.8.1. Binomial Queue Structure 


236  (1) 

6.8.2. Binomial Queue Operations 


237  (3) 

6.8.3. Implementation of Binomial Queues 


240  (6) 


246  (1) 


246  (5) 


251  (2) 


253  (50) 


253  (1) 


254  (1) 


254  (1) 

7.2.2. Analysis of Insertion Sort 


254  (1) 

7.3. A Lower Bound for Simple Sorting Algorithms 


255  (1) 


256  (4) 

7.4.1. WorstCase Analysis of Shellsort 


257  (3) 


260  (4) 

7.5.1. Analysis of Heapsort 


263  (1) 


264  (5) 

7.6.1. Analysis of Mergesort 


266  (3) 


269  (12) 


271  (1) 

7.7.2. Partitioning Strategy 


271  (3) 


274  (1) 

7.7.4. Actual Quicksort Routines 


274  (1) 

7.7.5. Analysis of Quicksort 


275  (4) 

7.7.6. A LinearExpectedTime Algorithm for Selection 


279  (2) 


281  (5) 

7.8.1. vector [Comparable *] Does Not Work 


283  (1) 

7.8.2. Smart Pointer Class 


283  (1) 

7.8.3. Overloading operator (XXX) 


284  (1) 

7.8.4. Dereferencing a Pointer with * 


284  (1) 

7.8.5. Overloading the Type Conversion Operator 


284  (1) 

7.8.6. Implicit Type Conversions Are Everywhere 


285  (1) 

7.8.7. DualDirection Implicit Conversions Can Cause Ambiguities 


285  (1) 

7.8.8. Pointer Subtraction Is Legal 


286  (1) 

7.9. A General Lower Bound for Sorting 


286  (2) 


286  (2) 


288  (1) 


289  (5) 

7.11.1. Why We Need New Algorithms 


289  (1) 

7.11.2. Model for External Sorting 


289  (1) 

7.11.3. The Simple Algorithm 


290  (1) 


291  (1) 


292  (1) 

7.11.6. Replacement Selection 


293  (1) 


294  (1) 


295  (5) 


300  (3) 

Chapter 8 The Disjoint Set ADT 


303  (24) 

8.1. Equivalence Relations 


303  (1) 

8.2. The Dynamic Equivalence Problem 


304  (2) 

8.3. Basic Data Structure 


306  (3) 

8.4. Smart Union Algorithms 


309  (3) 


312  (1) 

8.6. Worst Case for UnionbyRank and Path Compression 


313  (7) 

8.6.1. Analysis of the Union/Find Algorithm 


314  (6) 


320  (2) 


322  (1) 


322  (2) 


324  (3) 

Chapter 9 Graph Algorithms 


327  (64) 


327  (3) 

9.1.1. Representation of Graphs 


328  (2) 


330  (3) 

9.3. ShortestPath Algorithms 


333  (18) 

9.3.1. Unweighted Shortest Paths 


335  (4) 

9.3.2. Dijkstra's Algorithm 


339  (8) 

9.3.3. Graphs with Negative Edge Costs 


347  (1) 


348  (3) 

9.3.5. AllPairs Shortest Path 


351  (1) 

9.4. Network Flow Problems 


351  (5) 

9.4.1. A Simple MaximumFlow Algorithm 


352  (4) 

9.5. Minimum Spanning Tree 


356  (6) 


356  (4) 

9.5.2. Kruskal's Algorithm 


360  (2) 

9.6. Applications of DepthFirst Search 


362  (12) 


362  (1) 


363  (5) 


368  (3) 


371  (2) 

9.6.5. Finding Strong Components 


373  (1) 

9.7. Introduction to NPCompleteness 


374  (5) 


375  (1) 


376  (1) 

9.7.3. NPComplete Problems 


377  (2) 


379  (1) 


379  (7) 


386  (5) 

Chapter 10 Algorithm Design Techniques 


391  (78) 


391  (18) 

10.1.1. A Simple Scheduling Problem 


392  (3) 


395  (6) 

10.1.3. Approximate Bin Packing 


401  (8) 


409  (14) 

10.2.1. Running Time of Divide and Conquer Algorithms 


410  (2) 

10.2.2. ClosestPoints Problem 


412  (4) 

10.2.3. The Selection Problem 


416  (3) 

10.2.4. Theoretical Improvements for Arithmetic Problems 


419  (4) 

10.3. Dynamic Programming 


423  (11) 

10.3.1. Using a Table Instead of Recursion 


423  (2) 

10.3.2. Ordering Matrix Multiplications 


425  (4) 

10.3.3. Optimal Binary Search Tree 


429  (3) 

10.3.4. AllPairs Shortest Path 


432  (2) 

10.4. Randomized Algorithms 


434  (10) 

10.4.1. Random Number Generators 


436  (4) 


440  (2) 

10.4.3. Primality Testing 


442  (2) 

10.5. Backtracking Algorithms 


444  (11) 

10.5.1. The Turnpike Reconstruction Problem 


445  (4) 


449  (6) 


455  (1) 


455  (9) 


464  (5) 

Chapter 11 Amortized Analysis 


469  (26) 

11.1. An Unrelated Puzzle 


470  (1) 


470  (5) 


475  (2) 


477  (10) 

11.4.1. Cutting Nodes in Leftist Heaps 


478  (3) 

11.4.2. Lazy Merging for Binomial Queues 


481  (3) 

11.4.3. The Fibonacci Heap Operations 


484  (1) 

11.4.4. Proof of the Time Bound 


485  (2) 


487  (4) 


491  (1) 


491  (2) 


493  (2) 

Chapter 12 Advanced Data Structures and Implementation 


495  (48) 

12.1. TopDown Splay Trees 


495  (8) 


503  (9) 

12.2.1. BottomUp Insertion 


503  (2) 

12.2.2. TopDown RedBlack Trees 


505  (1) 

12.2.3. TopDown Deletion 


506  (6) 

12.3. Deterministic Skip Lists 


512  (6) 


518  (6) 


524  (3) 


527  (3) 


530  (6) 


536  (1) 


536  (4) 


540  (3) 

Appendix A The Standard Template Library 


543  (24) 


543  (1) 


544  (3) 

A.2.1. Header Files and the using Directive 


544  (1) 


544  (1) 


545  (1) 


546  (1) 


546  (1) 

A.3. Unordered Sequences: vector and list 


547  (3) 

A.3.1. vector versus list 


547  (2) 


549  (1) 


550  (1) 


551  (1) 

A.6. Example: Generating a Concordance 


552  (5) 


552  (2) 

A.6.2. Version without Using the STL 


554  (3) 

A.7. Example: ShortestPath Calculation 


557  (9) 

A.7.1. STL Implementation 


557  (3) 

A.7.2. Version without Using the STL 


560  (6) 


566  (1) 

Appendix B vector and string Classes 


567  (10) 

B.1. FirstClass versus SecondClass Objects 


567  (1) 


567  (3) 


570  (7) 
Index 

577  