Detailed Table of Contents

Detailed Table of Contents


1. Basic C++ Programming

	1.1 Basic C++ Programming Elements, 3
	        The C++ Programming Model, 3
	    1.1.1 A Simple C++ Program, 4
	        Highlighting the C++ Elements, 4
	    1.1.2 Fundamental Types, 6
	        Characters, 6
	        Integers, 7
	        Enumerations, 7
	        Floating Point, 8
	    1.1.3 Pointers, Arrays, and Structures, 8
	        Pointers, 8
	        Arrays, 9
	        Pointers and Arrays, 10
	        Strings, 10
	        C-Style Structures, 11
	        Pointers, Dynamic Memory, and the `new' Operator, 12
	        Memory Leaks, 13
	        References, 14
	    1.1.4 Scope and Namespaces, 14
	        Constants and Typedef, 14
	        Local and Global Scopes, 15
	        Namespaces, 16
	        The Using Statement, 16
	1.2 Expressions, 17
	        Member Selection and Indexing, 17
	        Arithmetic Operators, 17
	        Increment and Decrement Operators, 17
	        Relational and Logical Operators, 18
	        Bitwise Operators, 19
	        Assignment Operators, 19
	        Other Operators, 20
	        Operator Precedence, 21
	    1.2.1 Casting in Expressions, 21
	        Traditional C-Style Casting, 22
	        Explicit Cast Operators, 22
	        Static Casting, 23
	        Implicit Casting, 23
	1.3 Control Flow, 24
	        If Statement, 24
	        Switch Statement, 24
	        While and Do-While Loops, 25
	        For Loop, 26
	        Break and Continue Statements, 27
	1.4 Functions, 28
	    1.4.1 Argument Passing, 29
	        Constant References as Arguments, 30
	        Array Arguments, 30
	    1.4.2 Overloading, 31
	        Function Overloading, 31
	        Operator Overloading, 31
	        Using Overloading, 32
	1.5 Classes, 33
	    1.5.1 Class Structure, 33
	        Access Control, 33
	        Member Functions, 34
	        In-Class Function Definition, 35
	    1.5.2 Constructors and Destructors, 36
	        Constructors, 36
	        Initializing Class Members with Initializer Lists, 38
	        Destructors, 39
	    1.5.3 Classes and Memory Allocation, 40
	    1.5.4 Class Friends and Class Members, 42
	        Nesting Classes and Types within Classes, 44
	    1.5.5 The Standard Template Library, 44
	        Templates and the STL Vector Class, 45
	1.6 C++ Program and File Organization, 46
	        Source Files, 46
	        Header Files, 46
	    1.6.1 An Example Program, 47
	        The CreditCard Class, 47
	        The Main Test Program, 49
	        Avoiding Multiple Header Expansions, 50
	1.7 Writing a C++ Program, 52
	    1.7.1 Design, 52
	    1.7.2 Coding, 53
	        Readability and Style, 54
	    1.7.3 Testing and Debugging, 55
	        Testing, 55
	        Debugging, 56
	1.8 Exercises, 57

2. Object-Oriented Design

	2.1 Goals and Principles, 63
	    2.1.1 Object-Oriented Design Goals, 63
	        Robustness, 63
	        Adaptability, 64
	        Reusability, 65
	    2.1.2 Object-Oriented Design Principles, 65
	        Abstraction, 66
	        Encapsulation, 66
	        Modularity, 67
	2.2 Inheritance and Polymorphism, 69
	    2.2.1 Inheritance in C++, 69
	        Member Functions, 71
	        Protected Members, 72
	        Illustrating Class Protection, 73
	        Constructors and Destructors, 74
	        Static Binding, 75
	        Dynamic Binding and Virtual Functions, 75
	        Virtual Destructors, 76
	    2.2.2 Polymorphism, 77
	        Specialization, 77
	        Extension, 78
	    2.2.3 Examples of Inheritance in C++, 78
	        Arithmetic and Geometric Progression Classes, 80
	        A Fibonacci Progression Class, 81
	        Combining the Progression Classes, 82
	    2.2.4 Multiple Inheritance and Class Casting, 84
	        Multiple and Restricted Inheritance, 84
	        Casting in an Inheritance Hierarchy, 85
	    2.2.5 Interfaces and Abstract Classes, 86
	        Abstract Classes, 87
	        Interfaces and Abstract Base Classes, 88
	2.3 Templates, 89
	    2.3.1 Function Templates, 89
	    2.3.2 Class Templates, 90
	        Templated Arguments, 91
	        Template Members, 91
	2.4 Exceptions, 92
	    2.4.1 Exception Objects, 92
	        Using Inheritance to Define New Exception Types, 93
	    2.4.2 Throwing and Catching Exceptions, 93
	    2.4.3 Exception Specification, 95
	        Generic Exception Class, 96
	2.5 Recursion and Other Design Patterns, 97
	    2.5.1 Recursion, 98
	        The Factorial Function, 98
	        A Recursive Implementation of the Factorial Function, 99
	        Drawing an English Ruler, 100
	        A Recursive Approach to Ruler Drawing, 100
	        Illustrating Ruler Drawing using a Recursion Trace, 102
	2.6 Exercises, 103

3. Analysis Tools

	3.1 Running Time and Pseudo-Code, 109
	    3.1.1 How Should Running Time be Measured?, 109
	        Requirements for a General Analysis Methodology, 110
	    3.1.2 Pseudo-Code, 110
	        A Pseudo-Code Example, 111
	        What Is Pseudo-Code?, 112
	3.2 A Quick Mathematical Review, 113
	    3.2.1 Summations, 113
	    3.2.2 Logarithms and Exponents, 115
	3.3 Justification Techniques (*), 116
	    3.3.1 By Example, 116
	    3.3.2 The `Contra' Attack, 116
	    3.3.3 Induction and Loop Invariants, 117
	        Induction, 117
	        Loop Invariants, 119
	3.4 Analysis of Algorithms, 120
	    3.4.1 Primitive Operations, 120
	        Counting Primitive Operations, 121
	    3.4.2 Average-Case and Worst-Case Analysis, 122
	3.5 Asymptotic Notation, 123
	        Simplifying the Analysis Further, 123
	    3.5.1 The `Big-Oh' Notation, 124
	    3.5.2 `Relatives' of the Big-Oh, 127
	        `Distant Cousins' of the Big-Oh, 128
	3.6 Asymptotic Analysis, 129
	        The Floor and Ceiling Functions, 129
	        The Importance of Asymptotics, 130
	    3.6.1 Using the Big-Oh Notation, 131
	        Some Words of Caution, 131
	    3.6.2 Examples of Asymptotic Algorithm Analysis, 132
	        A Quadratic-Time Algorithm, 133
	        A Linear-Time Algorithm, 134
	3.7 Exercises, 135

4. Stacks, Queues, and Recursion

	4.1 Using Recursion, 145
	    4.1.1 Linear Recursion, 146
	        Summing the Elements of an Array Recursively, 146
	        Analyzing Recursive Algorithms using Recursion Traces, 147
	        Reversing an Array by Recursion, 148
	        Computing Powers via Linear Recursion, 149
	        Tail Recursion, 150
	    4.1.2 Higher-Order Recursion, 151
	        Binary Recursion, 151
	        Computing Fibonacci Numbers via Binary Recursion, 152
	        Computing Fibonacci Numbers via Linear Recursion, 153
	        Multiple Recursion, 154
	4.2 Stacks, 156
	    4.2.1 The Stack Abstract Data Type, 157
	        A Stack Interface, 158
	        Access to Elements, 159
	    4.2.2 A Simple Array-Based Implementation, 161
	        A C++ Implementation of a Stack, 162
	        Running Time, 165
	    4.2.3 Implementing Recursion and Function Calls, 166
	        The C++ Run-time Stack, 166
	        How Functions are Called, 166
	        Implementing Call by Value, 167
	        Implementing Call by Reference, 168
	        Implementing Recursion with a Stack, 168
	4.3 Queues, 169
	    4.3.1 The Queue Abstract Data Type, 169
	        A Queue Interface, 170
	        Example Applications, 170
	    4.3.2 A Simple Array-Based Implementation, 171
	        Using an Array in a Circular Way, 172
	        Using the Modulo Operator to Implement a Circular Array, 173
	    4.3.3 Memory Allocation in C++, 175
	4.4 Linked Lists, 176
	    4.4.1 Singly Linked Lists, 176
	    4.4.2 Implementing a Stack with a Singly Linked List, 178
	        Housekeeping Functions, 179
	    4.4.3 Implementing a Queue with a Singly Linked List, 182
	4.5 Double-Ended Queues, 183
	    4.5.1 The Deque Abstract Data Type, 183
	    4.5.2 Implementing a Deque with a Doubly Linked List, 184
	        A C++ Deque Implementation, 186
	    4.5.3 The Adapter Design Pattern, 187
	        Defining the Adapter Design Pattern, 189
	4.6 Sample Case Study Application, 190
	        The Stock Span Problem, 190
	    4.6.1 A Quadratic-Time Algorithm, 191
	    4.6.2 A Linear-Time Algorithm, 192
	        Summarizing the Running Time, 193
	    4.6.3 C++ Implementation, 195
	4.7 Exercises, 196

5. Vectors, Lists, and Sequences

	5.1 Vectors, 205
	    5.1.1 The Vector Abstract Data Type, 206
	    5.1.2 A Simple Array-Based Implementation, 207
	    5.1.3 An Extendable Array Implementation, 209
	        Fixed Length Capacity Increment, 213
	    5.1.4 The STL vector Class, 214
	5.2 Lists, 215
	    5.2.1 Node-Based Operations and Positions, 215
	        Positions, 216
	    5.2.2 The List Abstract Data Type, 217
	    5.2.3 Doubly Linked List Implementation, 220
	        Using Positions, 224
	    5.2.4 The STL list Class, 227
	        Similarities and Differences with Our List ADT, 227
	5.3 Sequences, 228
	    5.3.1 The Sequence Abstract Data Type, 228
	        Multiple Inheritance in the Sequence ADT, 228
	    5.3.2 Implementing a Sequence with a Doubly Linked List, 229
	    5.3.3 Implementing a Sequence with an Array, 233
	    5.3.4 Comparing Sequence Implementations, 234
	5.4 Case Study: Bubble-Sort on a Sequence, 235
	    5.4.1 The Bubble-Sort Algorithm, 235
	    5.4.2 A Sequence-Based Analysis of Bubble-Sort, 236
	5.5 Iterators, 238
	    5.5.1 Iterator Functions, 238
	        STL Iterators, 239
	    5.5.2 More About Iterators, 240
	        When Iterators Become Invalid, 240
	        Iterators and Positions, 240
	        Using Iterators, 241
	        Implementing Iterators, 241
	        Forward and Backward Iterators, 241
	5.6 A Hierarchy of Sequence ADTs, 242
	    5.6.1 Functions of a Container, 242
	        The Container ADT, 242
	    5.6.2 Inspectable Containers, 243
	    5.6.3 Inheritance Structure of Sequence ADTs, 244
	5.7 Exercises, 245

6. Trees

	6.1 The Tree Abstract Data Type, 255
	    6.1.1 Terminology and Basic Properties, 255
	        Ordered Trees, 257
	    6.1.2 Tree Functions, 259
	    6.1.3 A Tree Interface, 261
	6.2 Basic Algorithms on Trees, 262
	    6.2.1 Running-Time Assumptions, 262
	    6.2.2 Depth and Height, 263
	    6.2.3 Preorder Traversal, 266
	        Tree Printing: An Application of Preorder Traversal, 267
	        Using Preorder Traversal for Representing a Tree, 268
	    6.2.4 Postorder Traversal, 269
	        An Illustrative Use of the Postorder Traversal, 270
	        A Postorder Algorithm for Computing Disk Usage, 272
	        Other Kinds of Traversals, 272
	6.3 Binary Trees, 273
	    6.3.1 The Binary Tree ADT, 273
	    6.3.2 A Binary Tree Interface, 274
	    6.3.3 Properties of Binary Trees, 275
	    6.3.4 Traversals of a Binary Tree, 277
	        Preorder Traversal of a Binary Tree, 277
	        Postorder Traversal of a Binary Tree, 277
	        Evaluating an Arithmetic Expression, 278
	        Inorder Traversal of a Binary Tree, 279
	        Binary Search Trees, 280
	        Using Inorder Traversal for Tree Drawing, 281
	        A Unified Tree Traversal Framework, 281
	        The Euler Tour Traversal of a Binary Tree, 282
	    6.3.5 The Template Function Pattern, 284
	        Euler Tour with the Template Function Pattern, 284
	        Template Function Examples, 285
	        C++ Implementation, 286
	6.4 Data Structures for Representing Trees, 289
	    6.4.1 A Vector-Based Structure for Binary Trees, 289
	    6.4.2 A Linked Structure for Binary Trees, 291
	        Nodes and Positions in a Binary Tree, 292
	        Binary Tree Update Functions, 294
	        Copying a Binary Tree, 297
	    6.4.3 A Linked Structure for General Trees, 298
	    6.4.4 Representing General Trees with Binary Trees, 299
	6.5 Exercises, 301

7. Priority Queues

	7.1 The Priority Queue Abstract Data Type, 313
	    7.1.1 Keys, Priorities, and Total Order Relations, 313
	        Comparing Keys with Total Orders, 314
	    7.1.2 Sorting with a Priority Queue, 315
	    7.1.3 Functions of a Priority Queue, 316
	        Simplicity of the Priority Queue ADT, 316
	    7.1.4 Compositions and Comparators, 318
	        The Composition Pattern, 318
	        The Comparator Pattern, 319
	        Using Comparator Objects, 321
	    7.1.5 The STL priority_queue Class, 322
	7.2 Implementing a Priority Queue with a Sequence, 323
	    7.2.1 Implementation with an Unsorted Sequence, 323
	    7.2.2 Implementation with a Sorted Sequence, 324
	        Comparing the Two Implementations, 324
	    7.2.3 Selection-Sort and Insertion-Sort, 327
	        Selection-Sort, 327
	        Insertion-Sort, 328
	7.3 Heaps, 330
	    7.3.1 The Heap Data Structure, 330
	    7.3.2 Implementing a Priority Queue with a Heap, 333
	        The Vector Representation of a Heap, 334
	        Insertion, 335
	        Up-Heap Bubbling after an Insertion, 335
	        Removal, 337
	        Down-Heap Bubbling after a Removal, 337
	        Analysis, 339
	    7.3.3 C++ Implementation, 340
	    7.3.4 Heap-Sort, 343
	        Implementing Heap-Sort In-Place, 343
	    7.3.5 Bottom-Up Heap Construction (*), 345
	7.4 The Locator Design Pattern, 349
	        Tracking Elements as they Move, 349
	        Defining the Locator Pattern, 349
	        Using Locators with Data Structures, 350
	        Locator Member Functions, 350
	    7.4.1 Locator-Based Priority Queue Functions (*), 351
	        Extending the Priority Queue ADT, 351
	    7.4.2 Implementing Locator-Based Priority Queues (*), 353
	7.5 Exercises, 357

8. Dictionaries

	8.1 The Dictionary Abstract Data Type, 365
	    8.1.1 The Dictionary ADT, 366
	    8.1.2 Log Files, 369
	        Unordered Sequence Implementation, 369
	        Analysis of the Log File Data Structure, 370
	        Applications for Log Files, 370
	8.2 Hash Tables, 371
	    8.2.1 Bucket Arrays, 371
	        Analysis of the Bucket Array Structure, 372
	    8.2.2 Hash Functions, 372
	    8.2.3 Hash Codes, 373
	        Hash Codes in C++, 373
	        Casting to an Integer, 373
	        Summing Components, 373
	        A Small C++ Example, 374
	        Polynomial Hash Codes, 374
	        Cyclic Shift Hash Codes, 375
	        Experimental Results, 376
	        Hashing Floating-Point Quantities, 377
	    8.2.4 Compression Maps, 377
	        The Division Method, 378
	        The MAD Method, 378
	    8.2.5 Collision-Handling Schemes, 379
	        Separate Chaining, 379
	        Open Addressing, 381
	        Linear Probing, 381
	        Quadratic Probing, 382
	        Double Hashing, 382
	    8.2.6 Load Factors and Rehashing, 383
	        Rehashing into a New Table, 383
	    8.2.7 A C++ Hash Table Implementation, 384
	8.3 Ordered Dictionaries, 388
	    8.3.1 The Ordered Dictionary ADT, 388
	    8.3.2 Look-Up Tables, 388
	    8.3.3 Binary Search, 389
	        Analysis of Binary Search, 391
	        Using Look-Up Tables as Ordered Dictionaries, 392
	        Comparing Simple Ordered Dictionary Implementations, 392
	    8.3.4 The C++ Standard Template Library map Class, 393
	8.4 Skip Lists, 394
	    8.4.1 Searching, 396
	    8.4.2 Update Operations, 397
	        Insertion, 397
	        Removal, 399
	        Maintaining the Top-most Level, 400
	    8.4.3 A Probabilistic Analysis of Skip Lists (*), 400
	        A Simplified Analysis, 401
	        Bounding the Height of a Skip List, 401
	        Bounding the Search Time on Each Level, 401
	        Space Usage, 402
	        Performance Summary, 402
	8.5 Locator-Based Dictionary Functions (*), 403
	        Key-Based Containers, 404
	8.6 Exercises, 405

9. Search Trees

	9.1 Binary Search Trees, 414
	    9.1.1 Searching, 415
	        Analysis of Binary Tree Searching, 416
	    9.1.2 Update Operations, 417
	        Insertion, 417
	        Removal, 418
	        Best-case versus Worst-case, 420
	    9.1.3 C++ Implementation, 420
	        A Binary Search Tree in C++, 421
	    9.1.4 Performance, 425
	9.2 AVL Trees, 426
	        Definition, 426
	    9.2.1 Update Operations, 428
	        Insertion, 428
	        Removal, 432
	    9.2.2 C++ Implementation, 433
	    9.2.3 Performance, 436
	9.3 Multi-Way Search Trees, 437
	        Definition, 437
	        Searching in a Multi-Way Tree, 439
	        Data Structures, 439
	9.4 (2,4) Trees, 441
	    9.4.1 Update Operations, 443
	        Insertion, 443
	        Analysis of Insertion in a $(2,4)$ Tree, 445
	        Removal, 446
	    9.4.2 Performance, 448
	9.5 Red-Black Trees, 449
	    9.5.1 Update Operations, 451
	        Insertion, 451
	        Removal, 456
	    9.5.2 C++ Implementation, 463
	    9.5.3 Performance, 467
	9.6 Locator-Based Search Trees (*), 468
	9.7 External Searching (*), 470
	    9.7.1 $(a,b)$ Trees, 471
	        Update Operations, 472
	    9.7.2 B-Trees, 474
	9.8 Exercises, 475

10. Sorting, Sets, and Selection

	10.1 Merge-Sort, 485
	    10.1.1 Divide-and-Conquer, 485
	        Using Divide-and-Conquer for Sorting, 485
	        Merging Two Sorted Sequences, 491
	        The Running Time of Merge-Sort, 492
	    10.1.2 A C++ Implementation of Merge-Sort, 494
	    10.1.3 Merge-Sort and Recurrence Relations (*), 496
	        Confirming the Analysis via Induction, 497
	10.2 The Set ADT, 498
	    10.2.1 A Simple Set Implementation, 499
	        Sets in STL, 499
	        Using a Sorted Sequence to Implement a Set, 499
	        Generic Merging as a Template Method Pattern, 500
	        Using Inheritence to Derive Set Operations, 502
	        Performance of Generic Merging, 502
	10.3 Quick-Sort, 504
	        High-Level Description of Quick-Sort, 504
	    10.3.1 In-Place Quick-Sort, 509
	        Running Time of Quick-Sort, 512
	    10.3.2 Randomized Quick-Sort, 513
	10.4 A Lower Bound on Comparison-Based Sorting, 515
	10.5 Bucket-Sort and Radix-Sort, 517
	    10.5.1 Bucket-Sort, 517
	        Stable Sorting, 518
	    10.5.2 Radix-Sort, 518
	10.6 Comparison of Sorting Algorithms, 520
	        Insertion-Sort, 520
	        Merge-Sort, 520
	        Quick-Sort, 521
	        Heap-Sort, 521
	        Bucket-Sort and Radix-Sort, 521
	10.7 Selection, 522
	    10.7.1 Prune-and-Search, 522
	    10.7.2 Randomized Quick-Select, 523
	    10.7.3 Analyzing Randomized Quick-Select (*), 524
	        The Linearity of Expectation, 524
	        Characterizing the Expected Time for Quick-Select, 524
	        Obtaining a Closed Form Analysis, 525
	10.8 Exercises, 526

11. Text Processing

	11.1 String Operations, 535
	        Substrings, 535
	    11.1.1 The STL String Class, 536
	        Further Observations about STL Strings, 537
	11.2 Pattern Matching Algorithms, 538
	    11.2.1 Brute Force, 538
	        Brute-Force Pattern Matching, 538
	        Performance, 539
	    11.2.2 The Boyer-Moore Algorithm, 540
	    11.2.3 The Knuth-Morris-Pratt Algorithm, 545
	        The Failure Function, 545
	        Performance, 547
	        Constructing the KMP Failure Function, 548
	11.3 Tries, 550
	    11.3.1 Standard Tries, 550
	    11.3.2 Compressed Tries, 554
	    11.3.3 Suffix Tries, 556
	        Saving Space, 556
	        Construction, 556
	        Using a Suffix Trie, 557
	        Performance, 559
	    11.3.4 Search Engines, 560
	        Inverted Files, 560
	11.4 Text Compression, 561
	    11.4.1 The Huffman Coding Algorithm, 562
	    11.4.2 The Greedy Method, 563
	11.5 Text Similarity Testing, 564
	    11.5.1 The Longest Common Subsequence Problem, 564
	        Problem Definition, 564
	    11.5.2 Dynamic Programming, 565
	    11.5.3 Applying Dynamic Programming to the LCS Problem, 565
	        The LCS Algorithm, 567
	        Performance, 567
	11.6 Exercises, 569

12. Graphs

	12.1 The Graph Abstract Data Type, 577
	    12.1.1 Graph Functions, 582
	        General Functions, 583
	        Functions Dealing with Directed Edges, 583
	        Functions for Updating Graphs, 584
	12.2 Data Structures for Graphs, 585
	    12.2.1 The Edge List Structure, 585
	        Vertex Objects, 585
	        Edge Objects, 586
	        The Edge List, 586
	        Performance, 588
	    12.2.2 The Adjacency List Structure, 589
	        The Adjacency List, 589
	        Performance, 591
	    12.2.3 The Adjacency Matrix Structure, 592
	        Performance, 594
	12.3 Graph Traversal, 595
	    12.3.1 Depth-First Search, 595
	        The Decorator Pattern, 599
	        Polymorphic Objects, 600
	        A Generic DFS Implementation in C++, 602
	        Using the Template Method Pattern for DFS, 602
	    12.3.2 Breadth-First Search, 608
	12.4 Directed Graphs, 611
	        Comparing BFS and DFS for Directed and Undirected
		Graphs, 611
	        Reachability, 611
	    12.4.1 Traversing a Digraph, 613
	        Testing for Strong Connectivity, 615
	        Directed Breadth-First Search, 615
	    12.4.2 Transitive Closure, 615
	    12.4.3 Directed Acyclic Graphs, 617
	        Testing if a Directed Graph is Acyclic, 622
	    12.4.4 Application: Garbage Collection (*), 622
	        Determining Live Objects, 623
	        The Mark-Sweep Algorithm, 623
	        Performing DFS In-place, 624
	12.5 Weighted Graphs, 625
	12.6 Shortest Paths, 626
	    12.6.1 Dijkstra's Algorithm, 627
	        A Greedy Method for Finding Shortest Paths, 627
	        Edge Relaxation, 627
	        Why It Works, 630
	        The Running Time of Dijkstra's Algorithm, 632
	        An Alternative Implementation for Dijkstra's Algorithm, 633
	        Comparing the Two Implementations, 633
	        Programming Dijkstra's Algorithm in C++, 633
	12.7 Minimum Spanning Trees, 637
	        Problem Definition, 637
	        A Crucial Fact about Minimum Spanning Trees, 638
	    12.7.1 Kruskal's Algorithm, 639
	        The Running Time of Kruskal's Algorithm, 642
	    12.7.2 The Prim-Jarnik Algorithm, 643
	        A Comparison of the Above MST Algorithms, 646
	12.8 Exercises, 647

Appendix A: Useful Mathematical Facts

	        Logarithms and Exponents, 657
	        Integer Functions and Relations, 658
	        Summations, 659
	        Basic Probability, 661
	        Useful Mathematical Techniques, 663

Bibliography

Index

Sections marked with a star (*) are optional.