Data structures and algorithm analysis in C++
By: Mark Allen Weiss.
Edition: 3rd ed.
Publisher: Pearson Addison-Wesley
Published: 2005
Place of publication: Boston
Language: eng
Number of pages: 608
Subjects: C++ (Computer program language); Data structures (Computer science); Computer algorithms
Notes: Includes bibliographical references and index.
Table of contents: title: Preface
pagenum: xv; label: Chapter 1
title: Introduction
pagenum: 1; title: What's the Book About?
pagenum: 1; title: Mathematics Review
pagenum: 2; title: Exponents
pagenum: 3; title: Logarithms
pagenum: 3; title: Series; title: Modular Arithmetic
pagenum: 5; title: The P Word
pagenum: 6; title: A Brief Introduction to Recursion
pagenum: 7; title: C++ Classes
pagenum: 11; title: Basic Class Syntax
pagenum: 12; title: Extra Constructor Syntax and Accessors
pagenum: 12; title: Separation of Interface and Implementation
pagenum: 15; title: vector and string
pagenum: 17; title: C++ Details
pagenum: 19; title: Pointers
pagenum: 19; title: Parameter Passing
pagenum: 21; title: Return Passing
pagenum: 22; title: Reference Variables
pagenum: 23; title: The Big Three: Destructor, Copy Constructor, operator=
pagenum: 23; title: C-style Arrays and Strings
pagenum: 26; title: Templates
pagenum: 29; title: Function Templates
pagenum: 29; title: Class Templates
pagenum: 30; title: Object, Comparable, and an Example
pagenum: 32; title: Function Objects
pagenum: 34; title: Separate Compilation of Class Templates
pagenum: 35; title: Using Matrices
pagenum: 37; title: The Data Members, Constructor, and Basic Accessors
pagenum: 37; title: operator[]
pagenum: 37; title: Destructor, Copy Assignment, Copy Constructor
pagenum: 39; title: Summary
pagenum: 39; title: Exercises
pagenum: 39; title: References
pagenum: 41; label: Chapter 2
title: Algorithm Analysis
pagenum: 43; title: Mathematical Background
pagenum: 43; title: Model
pagenum: 46; title: What to Analyze
pagenum: 46; title: Running Time Calculations
pagenum: 49; title: A Simple Example
pagenum: 49; title: General Rules
pagenum: 50; title: Solutions for the Maximum Subsequence Sum Problem
pagenum: 52; title: Logarithms in the Running Time
pagenum: 58; title: Checking Your Analysis
pagenum: 62; title: A Grain of Salt
pagenum: 63; title: Summary
pagenum: 63; title: Exercises
pagenum: 64; title: References
pagenum: 69; label: Chapter 3
title: Lists, Stacks, and Queues
pagenum: 71; title: Abstract Data Types (ADTs)
pagenum: 71; title: The List ADT
pagenum: 72; title: Simple Array Implementation of Lists
pagenum: 72; title: Simple Linked Lists
pagenum: 73; title: vector and list in the STL
pagenum: 74; title: Iterators
pagenum: 75; title: Example: Using erase on a List
pagenum: 77; title: const_iterators
pagenum: 77; title: Implementation of vector
pagenum: 79; title: Implementation of list
pagenum: 83; title: The Stack ADT
pagenum: 94; title: Stack Model
pagenum: 94; title: Implementation of Stacks
pagenum: 95; title: Applications
pagenum: 96; title: The Queue ADT
pagenum: 104; title: Queue Model
pagenum: 104; title: Array Implementation of Queues
pagenum: 104; title: Applications of Queues
pagenum: 106; title: Summary
pagenum: 107; title: Exercises
pagenum: 108; label: Chapter 4
title: Trees
pagenum: 113; title: Preliminaries
pagenum: 113; title: Implementation of Trees
pagenum: 114; title: Tree Traversals with an Application
pagenum: 115; title: Binary Trees
pagenum: 119; title: Implementation
pagenum: 120; title: An Example: Expression Trees
pagenum: 121; title: The Search Tree ADT - Binary Search Trees
pagenum: 124; title: contains
pagenum: 125; title: findMin and findMax
pagenum: 125; title: insert
pagenum: 129; title: remove
pagenum: 130; title: Destructor and Copy Assignment Operator
pagenum: 132; title: Average-Case Analysis
pagenum: 133; title: AVL Trees
pagenum: 136; title: Single Rotation
pagenum: 139; title: Double Rotation
pagenum: 142; title: Splay Trees
pagenum: 149; title: A Simple Idea (That Does Not Work)
pagenum: 150; title: Splaying
pagenum: 152; title: Tree Traversals (Revisited)
pagenum: 158; title: B-Trees
pagenum: 159; title: Sets and Maps in the Standard Library
pagenum: 165; title: Sets
pagenum: 165; title: Maps
pagenum: 166; title: Implementation of set and map
pagenum: 167; title: An Example That Uses Several Maps
pagenum: 168; title: Summary
pagenum: 174; title: Exercises
pagenum: 174; title: References
pagenum: 181; label: Chapter 5
title: Hashing
pagenum: 185; title: General Idea
pagenum: 185; title: Hash Function
pagenum: 186; title: Separate Chaining
pagenum: 188; title: Hash Tables Without Linked Lists
pagenum: 192; title: Linear Probing
pagenum: 193; title: Quadratic Probing
pagenum: 195; title: Double Hashing
pagenum: 199; title: Rehashing
pagenum: 200; title: Hash Tables in the Standard Library
pagenum: 204; title: Extendible Hashing
pagenum: 204; title: Summary
pagenum: 207; title: Exercises
pagenum: 208; title: References
pagenum: 211; label: Chapter 6
title: Priority Queues (Heaps)
pagenum: 213; title: Model
pagenum: 213; title: Simple Implementations
pagenum: 214; title: Binary Heap
pagenum: 215; title: Structure Property
pagenum: 215; title: Heap-Order Property
pagenum: 216; title: Basic Heap Operations
pagenum: 217; title: Other Heap Operations
pagenum: 220; title: Applications of Priority Queues
pagenum: 225; title: The Selection Problem
pagenum: 226; title: Event Simulation
pagenum: 227; title: d-Heaps
pagenum: 228; title: Leftist Heaps
pagenum: 229; title: Leftist Heap Property
pagenum: 229; title: Leftist Heap Operations
pagenum: 230; title: Skew Heaps
pagenum: 235; title: Binomial Queues
pagenum: 239; title: Binomial Queue Structure
pagenum: 240; title: Binomial Queue Operations
pagenum: 241; title: Implementation of Binomial Queues
pagenum: 244; title: Priority Queues in the Standard Library
pagenum: 251; title: Summary
pagenum: 251; title: Exercises
pagenum: 251; title: References
pagenum: 257; label: Chapter 7
title: Sorting
pagenum: 261; title: Preliminaries
pagenum: 261; title: Insertion Sort
pagenum: 262; title: The Algorithm
pagenum: 262; title: STL Implementation of Insertion Sort
pagenum: 263; title: Analysis of Insertion Sort
pagenum: 264; title: A Lower Bound for Simple Sorting Algorithms
pagenum: 265; title: Shellsort
pagenum: 266; title: Worst-Case Analysis of Shellsort
pagenum: 268; title: Heapsort
pagenum: 270; title: Analysis of Heapsort
pagenum: 272; title: Mergesort
pagenum: 274; title: Analysis of Mergesort
pagenum: 276; title: Quicksort
pagenum: 279; title: Picking the Pivot
pagenum: 280; title: Partitioning Strategy
pagenum: 282; title: Small Arrays
pagenum: 284; title: Actual Quicksort Routines
pagenum: 284; title: Analysis of Quicksort
pagenum: 287; title: A Linear-Expected-Time Algorithm for Selection
pagenum: 290; title: Indirect Sorting
pagenum: 292; title: vector<Comparable*> Does Not Work
pagenum: 295; title: Smart Pointer Class
pagenum: 295; title: Overloading operator<
pagenum: 295; title: Dereferencing a Pointer with *
pagenum: 295; title: Overloading the Type Conversion Operator
pagenum: 295; title: Implicit Type Conversions Are Everywhere
pagenum: 296; title: Dual-Direction Implicit Conversions Can Cause Ambiguities
pagenum: 296; title: Pointer Subtraction Is Legal
pagenum: 297; title: A General Lower Bound for Sorting
pagenum: 297; title: Decision Trees
pagenum: 297; title: Bucket Sort
pagenum: 299; title: External Sorting
pagenum: 300; title: Why We Need New Algorithms
pagenum: 300; title: Model for External Sorting
pagenum: 300; title: The Simple Algorithm
pagenum: 301; title: Multiway Merge
pagenum: 302; title: Polyphase Merge
pagenum: 303; title: Replacement Selection
pagenum: 304; title: Summary
pagenum: 305; title: Exercises
pagenum: 306; title: References
pagenum: 311; label: Chapter 8
title: The Disjoint Set Class
pagenum: 315; title: Equivalence Relations
pagenum: 315; title: The Dynamic Equivalence Problem
pagenum: 316; title: Basic Data Structure
pagenum: 317; title: Smart Union Algorithms
pagenum: 321; title: Path Compression
pagenum: 324; title: Worst Case for Union-by-Rank and Path Compression
pagenum: 325; title: Analysis of the Union/Find Algorithm
pagenum: 326; title: An Application
pagenum: 331; title: Summary
pagenum: 334; title: Exercises
pagenum: 335; title: References
pagenum: 336; label: Chapter 9
title: Graph Algorithms
pagenum: 339; title: Definitions
pagenum: 339; title: Representation of Graphs
pagenum: 340; title: Topological Sort
pagenum: 342; title: Shortest-Path Algorithms
pagenum: 345; title: Unweighted Shortest Paths
pagenum: 347; title: Dijkstra's Algorithm
pagenum: 351; title: Graphs with Negative Edge Costs
pagenum: 360; title: Acyclic Graphs
pagenum: 360; title: All-Pairs Shortest Path
pagenum: 364; title: Shortest Path Example
pagenum: 365; title: Network Flow Problems
pagenum: 367; title: A Simple Maximum-Flow Algorithm
pagenum: 367; title: Minimum Spanning Tree
pagenum: 371; title: Prim's Algorithm
pagenum: 373; title: Kruskal's Algorithm
pagenum: 376; title: Applications of Depth-First Search
pagenum: 378; title: Undirected Graphs
pagenum: 379; title: Biconnectivity
pagenum: 381; title: Euler Circuits
pagenum: 385; title: Directed Graphs
pagenum: 388; title: Finding Strong Components
pagenum: 390; title: Introduction to NP-Completeness
pagenum: 392; title: Easy vs. Hard
pagenum: 392; title: The Class NP
pagenum: 393; title: NP-Complete Problems
pagenum: 394; title: Summary
pagenum: 396; title: Exercises
pagenum: 396; title: References
pagenum: 404; label: Chapter 10
title: Algorithm Design Techniques
pagenum: 409; title: Greedy Algorithms
pagenum: 409; title: A Simple Scheduling Problem
pagenum: 410; title: Huffman Codes
pagenum: 413; title: Approximate Bin Packing
pagenum: 419; title: Divide and Conquer
pagenum: 427; title: Running Time of Divide and Conquer Algorithms
pagenum: 428; title: Closest-Points Problem
pagenum: 430; title: The Selection Problem
pagenum: 435; title: Theoretical Improvements for Arithmetic Problems
pagenum: 438; title: Dynamic Programming
pagenum: 442; title: Using a Table Instead of Recursion
pagenum: 442; title: Ordering Matrix Multiplications
pagenum: 444; title: Optimal Binary Search Tree
pagenum: 447; title: All-Pairs Shortest Path
pagenum: 451; title: Randomized Algorithms
pagenum: 454; title: Random Number Generators
pagenum: 455; title: Skip Lists
pagenum: 459; title: Primality Testing
pagenum: 461; title: Backtracking Algorithms
pagenum: 464; title: The Turnpike Reconstruction Problem
pagenum: 465; title: Games
pagenum: 469; title: Summary
pagenum: 475; title: Exercises
pagenum: 475; title: References
pagenum: 485; label: Chapter 11
title: Amortized Analysis
pagenum: 491; title: An Unrelated Puzzle
pagenum: 492; title: Binomial Queues
pagenum: 492; title: Skew Heaps
pagenum: 497; title: Fibonacci Heaps
pagenum: 499; title: Cutting Nodes in Leftist Heaps
pagenum: 500; title: Lazy Merging for Binomial Queues
pagenum: 502; title: The Fibonacci Heap Operations
pagenum: 506; title: Proof of the Time Bound
pagenum: 506; title: Splay Trees
pagenum: 509; title: Summary
pagenum: 513; title: Exercises
pagenum: 513; title: References
pagenum: 515; label: Chapter 12
title: Advanced Data Structures and Implementation
pagenum: 517; title: Top-Down Splay Trees
pagenum: 517; title: Red-Black Trees
pagenum: 525; title: Bottom-Up Insertion
pagenum: 526; title: Top-Down Red-Black Trees
pagenum: 527; title: Top-Down Deletion
pagenum: 531; title: Deterministic Skip Lists
pagenum: 535; title: AA-Trees
pagenum: 540; title: Treaps
pagenum: 547; title: k-d Trees
pagenum: 549; title: Pairing Heaps
pagenum: 553; title: Summary
pagenum: 558; title: Exercises
pagenum: 558; title: References
pagenum: 563; label: Appendix A
title: Separate Compilation of Class Templates
pagenum: 567; title: Everything in the Header
pagenum: 568; title: Explicit Instantiation
pagenum: 568; title: The export Directive
pagenum: 570; title: Index
pagenum: 571