Table of contents for Data structures and algorithm analysis in C++ / Mark Allen Weiss.

Bibliographic record and links to related information available from the Library of Congress catalog.

Note: Contents data are machine generated based on pre-publication provided by the publisher. Contents may have variations from the printed book or be incomplete or contain other coding.


Counter
 
Contents 
Chapter 1 Introduction 1 
 1.1. What's the Book
About? 1 
 1.2. Mathematics
Review 3 
 1.2.1. Exponents 3 
 1.2.2. Logarithms 3 
 1.2.3. Series 4 
 1.2.4. Modular
Arithmetic 5 
 1.2.5. The it P 
Word 5 
 1.3. A Brief Introduction to
Recursion 7 
 1.4. C++ 
Classes 11 
 1.4.1. Basic tt class 
Syntax 12 
 1.4.2. Extra Constructor Syntax and
Accessors 13 
 1.4.3. Separation of Interface and
Implementation 15 
 1.4.4. tt vector and
 tt string 18 
 1.5. C++ 
Details 19 
 1.5.1. Pointers 19 
 1.5.2. Parameter
Passing 21 
 1.5.3. Return
Passing 22 
 1.5.4. Reference
Variables 23 
 1.5.5. The Big Three: Destructor, Copy Constructor,
 tt operator= 23 
 1.5.6. The World of
C 28 
 1.6. Templates 30 
 1.6.1. Function
Templates 30 
 1.6.2. Class
Templates 32 
 1.6.3. tt Object , tt Comparable , and an
Example 34 
 1.7. Using
Matrices 36 
 1.7.1. The Data Members, Constructor, and Basic
Accessors 36 
 1.7.2. tt operator 36 
 1.7.3. Destructor, Copy Assignment, Copy
Constructor 37 
 Summary 37 
 Exercises 37 
 References 39 
Chapter 2 Algorithm
Analysis 41 
 2.1. Mathematical
Background 41 
 2.2. Model 44 
 2.3. What to
Analyze 44 
 2.4. Running Time
Calculations 47 
 2.4.1. A Simple
Example 47 
 2.4.2. General
Rules 48 
 2.4.3. Solutions for the Maximum Subsequence Sum
Problem 50 
 2.4.4. Logarithms in the Running
Time 56 
 2.4.5. Checking Your
Analysis 59 
 2.4.6. A Grain of
Salt 61 
 Summary 61 
 Exercises 62 
 References 67 
Chapter 3 Lists, Stacks, and
Queues 69 
 3.1. Abstract Data Types ( sc ADT s) 69 
 3.2. The List sc ADT 70 
 3.2.1. Simple Array Implementation of
Lists 70 
 3.2.2. Linked
Lists 71 
 3.2.3. Programming
Details 72 
 3.2.4. Memory Reclamation and the Big
Three 78 
 3.2.5. Doubly Linked
Lists 79 
 3.2.6. Circular Linked
Lists 80 
 3.2.7. Examples 81 
 3.2.8. Cursor Implementation of Linked
Lists 86 
 3.3. The Stack sc ADT 93 
 3.3.1. Stack
Model 93 
 3.3.2. Implementation of
Stacks 93 
 3.3.3. Applications 100 
 3.4. The Queue sc ADT 110 
 3.4.1. Queue
Model 110 
 3.4.2. Array Implementation of
Queues 110 
 3.4.3. Applications of
Queues 114 
 Summary 115 
 Exercises 116 
Chapter 4 Trees 121 
 4.1. Preliminaries 121 
 4.1.1. Implementation of
Trees 122 
 4.1.2. Tree Traversals with an
Application 123 
 4.2. Binary
Trees 127 
 4.2.1. Implementation 127 
 4.2.2. An Example: Expression
Trees 128 
 4.3. The Search Tree sc ADT ---Binary Search
Trees 131 
 4.3.1. tt find 134 
 4.3.2. tt findMin and
 tt findMax 134 
 4.3.3. tt insert 136 
 4.3.4. tt remove 137 
 4.3.5. Destructor and Copy Assignment
Operator 139 
 4.3.6. Average-Case
Analysis 140 
 4.4. sc AVL 
Trees 143 
 4.4.1. Single
Rotation 145 
 4.4.2. Double
Rotation 148 
 4.5. Splay
Trees 155 
 4.5.1. A Simple Idea (That Does Not
Work) 155 
 4.5.2. Splaying 157 
 4.6. Tree Traversals
(Revisited) 163 
 4.7. B-Trees 165 
 Summary 170 
 Exercises 170 
 References 177 
Chapter 5 Hashing 181 
 5.1. General
Idea 181 
 5.2. Hash
Function 182 
 5.3. Separate
Chaining 184 
 5.4. Open
Addressing 188 
 5.4.1. Linear
Probing 189 
 5.4.2. Quadratic
Probing 191 
 5.4.3. Double
Hashing 196 
 5.5. Rehashing 197 
 5.6. Extendible
Hashing 200 
 Summary 203 
 Exercises 204 
 References 207 
Chapter 6 Priority Queues
(Heaps) 211 
 6.1. Model 211 
 6.2. Simple
Implementations 212 
 6.3. Binary
Heap 213 
 6.3.1. Structure
Property 213 
 6.3.2. Heap-Order
Property 214 
 6.3.3. Basic Heap
Operations 215 
 6.3.4. Other Heap
Operations 219 
 6.4. Applications of Priority
Queues 223 
 6.4.1. The Selection
Problem 223 
 6.4.2. Event
Simulation 224 
 6.5. $d$-Heaps 225 
 6.6. Leftist
Heaps 226 
 6.6.1. Leftist Heap
Property 226 
 6.6.2. Leftist Heap
Operations 227 
 6.7. Skew
Heaps 233 
 6.8. Binomial
Queues 236 
 6.8.1. Binomial Queue
Structure 236 
 6.8.2. Binomial Queue
Operations 237 
 6.8.3. Implementation of Binomial
Queues 240 
 Summary 246 
 Exercises 246 
 References 251 
Chapter 7 Sorting 253 
 7.1. Preliminaries 253 
 7.2. Insertion
Sort 254 
 7.2.1. The
Algorithm 254 
 7.2.2. Analysis of Insertion
Sort 254 
 7.3. A Lower Bound for Simple Sorting
Algorithms 255 
 7.4. Shellsort 256 
 7.4.1. Worst-Case Analysis of
Shellsort 257 
 7.5. Heapsort 260 
 7.5.1. Analysis of
Heapsort 263 
 7.6. Mergesort 264 
 7.6.1. Analysis of
Mergesort 266 
 7.7. Quicksort 269 
 7.7.1. Picking the
Pivot 271 
 7.7.2. Partitioning
Strategy 271 
 7.7.3. Small
Arrays 274 
 7.7.4. Actual Quicksort
Routines 274 
 7.7.5. Analysis of
Quicksort 275 
 7.7.6. A Linear-Expected-Time Algorithm for
Selection 279 
 7.8. Indirect
Sorting 281 
 7.8.1. tt vector<Comparable *> Does Not
Work 283 
 7.8.2. Smart Pointer
Class 283 
 7.8.3. Overloading
 tt operator< 284 
 7.8.4. Dereferencing a Pointer with
 tt * 284 
 7.8.5. Overloading the Type Conversion
Operator 284 
 7.8.6. Implicit Type Conversions Are
Everywhere 285 
 7.8.7. Dual-Direction Implicit Conversions Can
 Cause
Ambiguities 285 
 7.8.8. Pointer Subtraction Is
Legal 286 
 7.9. A General Lower Bound for
Sorting 286 
 7.9.1. Decision
Trees 286 
 7.10. Bucket
Sort 288 
 7.11. External
Sorting 289 
 7.11.1. Why We Need New
Algorithms 289 
 7.11.2. Model for External
Sorting 289 
 7.11.3. The Simple
Algorithm 290 
 7.11.4. Multiway
Merge 291 
 7.11.5. Polyphase
Merge 292 
 7.11.6. Replacement
Selection 293 
 Summary 294 
 Exercises 295 
 References 300 
Chapter 8 The Disjoint Set sc ADT 303 
 8.1. Equivalence
Relations 303 
 8.2. The Dynamic Equivalence
Problem 304 
 8.3. Basic Data
Structure 306 
 8.4. Smart Union
Algorithms 309 
 8.5. Path
Compression 312 
 8.6. Worst Case for Union-by-Rank and Path
Compression 313 
 8.6.1. Analysis of the Union/Find
Algorithm 314 
 8.7. An
Application 320 
 Summary 322 
 Exercises 322 
 References 324 
Chapter 9 Graph
Algorithms 327 
 9.1. Definitions 327 
 9.1.1. Representation of
Graphs 328 
 9.2. Topological
Sort 330 
 9.3. Shortest-Path
Algorithms 333 
 9.3.1. Unweighted Shortest
Paths 335 
 9.3.2. Dijkstra's
Algorithm 339 
 9.3.3. Graphs with Negative Edge
Costs 347 
 9.3.4. Acyclic
Graphs 348 
 9.3.5. All-Pairs Shortest
Path 351 
 9.4. Network Flow
Problems 351 
 9.4.1. A Simple Maximum-Flow
Algorithm 352 
 9.5. Minimum Spanning
Tree 356 
 9.5.1. Prim's
Algorithm 356 
 9.5.2. Kruskal's
Algorithm 360 
 9.6. Applications of Depth-First
Search 362 
 9.6.1. Undirected
Graphs 362 
 9.6.2. Biconnectivity 363 
 9.6.3. Euler
Circuits 368 
 9.6.4. Directed
Graphs 371 
 9.6.5. Finding Strong
Components 373 
 9.7. Introduction to
NP-Completeness 374 
 9.7.1. Easy vs.
Hard 375 
 9.7.2. The Class
NP 376 
 9.7.3. NP-Complete
Problems 377 
 Summary 379 
 Exercises 379 
 References 386 
Chapter 10 Algorithm Design
Techniques 391 
 10.1. Greedy
Algorithms 391 
 10.1.1. A Simple Scheduling
Problem 392 
 10.1.2. Huffman
Codes 395 
 10.1.3. Approximate Bin
Packing 401 
 10.2. Divide and
Conquer 409 
 10.2.1. Running Time of Divide and Conquer
Algorithms 410 
 10.2.2. Closest-Points
Problem 412 
 10.2.3. The Selection
Problem 416 
 10.2.4. Theoretical Improvements for Arithmetic
Problems 419 
 10.3. Dynamic
Programming 423 
 10.3.1. Using a Table Instead of
Recursion 423 
 10.3.2. Ordering Matrix
Multiplications 425 
 10.3.3. Optimal Binary Search
Tree 429 
 10.3.4. All-Pairs Shortest
Path 432 
 10.4. Randomized
Algorithms 434 
 10.4.1. Random Number
Generators 436 
 10.4.2. Skip
Lists 440 
 10.4.3. Primality
Testing 442 
 10.5. Backtracking
Algorithms 444 
 10.5.1. The Turnpike Reconstruction
Problem 445 
 10.5.2. Games 449 
 Summary 455 
 Exercises 455 
 References 464 
Chapter 11 Amortized
Analysis 469 
 11.1. An Unrelated
Puzzle 470 
 11.2. Binomial
Queues 470 
 11.3. Skew
Heaps 475 
 11.4. Fibonacci
Heaps 477 
 11.4.1. Cutting Nodes in Leftist
Heaps 478 
 11.4.2. Lazy Merging for Binomial
Queues 481 
 11.4.3. The Fibonacci Heap
Operations 484 
 11.4.4. Proof of the Time
Bound 485 
 11.5. Splay
Trees 487 
 Summary 491 
 Exercises 491 
 References 493 
Chapter 12 Advanced Data Structures and
Implementation 495 
 12.1. Top-Down Splay
Trees 495 
 12.2. Red-Black
Trees 503 
 12.2.1. Bottom-Up
Insertion 503 
 12.2.2. Top-Down Red-Black
Trees 505 
 12.2.3. Top-Down
Deletion 506 
 12.3. Deterministic Skip
Lists 512 
 12.4. AA-Trees 518 
 12.5. Treaps 524 
 12.6. $k$-d
Trees 527 
 12.7. Pairing
Heaps 530 
 Summary 536 
 Exercises 536 
 References 540 
Appendix A The Standard Template
Library 543 
 A.1. Introduction 543 
 A.2. Basic sc STL 
Concepts 544 
 A.2.1. Header Files and the tt using 
Directive 544 
 A.2.2. Containers 544 
 A.2.3. tt iterator 545 
 A.2.4. Pairs 546 
 A.2.5. Function
Objects 546 
 A.3. Unordered Sequences: tt vector and
 tt list 547 
 A.3.1. tt vector versus
 tt list 547 
 A.3.2. Stacks and
Queues 549 
 A.4. Sets 550 
 A.5. Maps 551 
 A.6. Example: Generating a
Concordance 552 
 A.6.1. sc STL 
Version 552 
 A.6.2. Version without Using the
 sc STL 554 
 A.7. Example: Shortest-Path
Calculation 557 
 A.7.1. sc STL 
Implementation 557 
 A.7.2. Version without Using the sc STL 560 
 A.8. Other sc STL 
Features 566 
Appendix B tt vector and tt string 
Classes 567 
 B.1. First-Class versus Second-Class
Objects 567 
 B.2. tt vector 
Class 567 
 B.3. tt string 
Class 570 
Index 577 

Library of Congress Subject Headings for this publication:

C++ (Computer program language).
Data structures (Computer science).
Computer algorithms.