Data structures and algorithm analysis in C++
By: Mark Allen Weiss.
Publisher: Benjamin/Cummings Pub. Co.
Published: 1994
Place of publication: Redwood City, Calif
Language: eng
Number of pages: 498
Subjects: C++ (Computer program language); Data structures (Computer science); Computer algorithms.
Notes: Includes bibliographical references and index.
Table of contents: label: 1
title: Introduction
pagenum: 1; label: 1.1
title: What's the Book About?
pagenum: 1; label: 1.2
title: Mathematics Review
pagenum: 3; label: 1.2.1
title: Exponents
pagenum: 3; label: 1.2.2
title: Logarithms
pagenum: 3; label: 1.2.3
title: Series
pagenum: 4; label: 1.2.4
title: Modular Arithmetic
pagenum: 5; label: 1.2.5
title: The P Word
pagenum: 6; label: 1.3
title: A Brief Introduction to Recursion
pagenum: 8; label: 1.4
title: C++ at a Glance
pagenum: 12; label: 1.4.1
title: A String Class
pagenum: 14; label: 1.4.2
title: A Complex Number Class
pagenum: 21; title: Summary
pagenum: 25; title: Exercises
pagenum: 25; title: References
pagenum: 26; label: 2
title: Algorithm Analysis
pagenum: 29; label: 2.1
title: Mathematical Background
pagenum: 29; label: 2.2
title: Model
pagenum: 32; label: 2.3
title: What to Analyze
pagenum: 32; label: 2.4
title: Running Time Calculations
pagenum: 34; label: 2.4.1
title: A Simple Example
pagenum: 35; label: 2.4.2
title: General Rules
pagenum: 36; label: 2.4.3
title: Solutions for the Maximum Subsequence Sum Problem
pagenum: 38; label: 2.4.4
title: Logarithms in the Running Time
pagenum: 43; label: 2.4.5
title: Checking Your Analysis
pagenum: 48; label: 2.4.6
title: A Grain of Salt
pagenum: 48; title: Summary
pagenum: 48; title: Exercises
pagenum: 50; title: References
pagenum: 54; label: 3
title: Lists, Stacks, and Queues
pagenum: 57; label: 3.1
title: Abstract Data Types (ADTs)
pagenum: 57; label: 3.2
title: The List ADT
pagenum: 58; label: 3.2.1
title: Simple Array Implementation of Lists
pagenum: 59; label: 3.2.2
title: Linked Lists
pagenum: 59; label: 3.2.3
title: Programming Details
pagenum: 60; label: 3.2.4
title: Common Errors
pagenum: 69; label: 3.2.5
title: Doubly and Circularly Linked Lists
pagenum: 71; label: 3.2.6
title: Sorted Linked Lists, Inheritance, and Virtual Functions
pagenum: 71; label: 3.2.7
title: Examples
pagenum: 73; label: 3.2.8
title: Cursor Implementation of Linked Lists
pagenum: 80; label: 3.3
title: The Stack ADT
pagenum: 88; label: 3.3.1
title: Stack Model
pagenum: 88; label: 3.3.2
title: Implementation of Stacks
pagenum: 89; label: 3.3.3
title: Applications
pagenum: 96; label: 3.4
title: The Queue ADT
pagenum: 104; label: 3.4.1
title: Queue Model
pagenum: 104; label: 3.4.2
title: Array Implementation of Queues
pagenum: 105; label: 3.4.3
title: Applications of Queues
pagenum: 107; title: Summary
pagenum: 110; title: Exercises
pagenum: 111; label: 4
title: Trees
pagenum: 115; label: 4.1
title: Preliminaries
pagenum: 115; label: 4.1.1
title: Implementation of Trees
pagenum: 116; label: 4.1.2
title: Tree Traversals with an Application
pagenum: 117; label: 4.2
title: Binary Trees
pagenum: 121; label: 4.2.1
title: Implementation
pagenum: 122; label: 4.2.2
title: Expression Trees
pagenum: 123; label: 4.3
title: The Search Tree ADT: Binary Search Trees
pagenum: 126; label: 4.3.1
title: Make_Empty
pagenum: 129; label: 4.3.2
title: Find
pagenum: 130; label: 4.3.3
title: Find_Min and Find_Max
pagenum: 130; label: 4.3.4
title: Insert
pagenum: 131; label: 4.3.5
title: Remove
pagenum: 133; label: 4.3.6
title: Average-Case Analysis
pagenum: 135; label: 4.4
title: AVL Trees
pagenum: 137; label: 4.4.1
title: Single Rotation
pagenum: 139; label: 4.4.2
title: Double Rotation
pagenum: 141; label: 4.5
title: Splay Trees
pagenum: 150; label: 4.5.1
title: A Simple Idea (That Does Not Work)
pagenum: 150; label: 4.5.2
title: Splaying
pagenum: 153; label: 4.6
title: Tree Traversals (Revisited)
pagenum: 164; label: 4.7
title: B-Trees
pagenum: 165; title: Summary
pagenum: 170; title: Exercises
pagenum: 171; title: References
pagenum: 177; label: 5
title: Hashing
pagenum: 181; label: 5.1
title: General Idea
pagenum: 181; label: 5.2
title: Hash Function
pagenum: 182; label: 5.3
title: Open Hashing (Separate Chaining)
pagenum: 184; label: 5.4
title: Closed Hashing (Open Addressing)
pagenum: 189; label: 5.4.1
title: Linear Probing
pagenum: 189; label: 5.4.2
title: Quadratic Probing
pagenum: 191; label: 5.4.3
title: Double Hashing
pagenum: 193; label: 5.5
title: Rehashing
pagenum: 198; label: 5.6
title: Extendible Hashing
pagenum: 200; title: Summary
pagenum: 204; title: Exercises
pagenum: 206; title: References
pagenum: 208; label: 6
title: Priority Queues (Heaps)
pagenum: 211; label: 6.1
title: Model
pagenum: 211; label: 6.2
title: Simple Implementations
pagenum: 212; label: 6.3
title: Binary Heap
pagenum: 213; label: 6.3.1
title: Structure Property
pagenum: 213; label: 6.3.2
title: Heap Order Property
pagenum: 215; label: 6.3.3
title: Basic Heap Operations
pagenum: 216; label: 6.3.4
title: Other Heap Operations
pagenum: 220; label: 6.4
title: Applications of Priority Queues
pagenum: 223; label: 6.4.1
title: The Selection Problem
pagenum: 224; label: 6.4.2
title: Event Simulation
pagenum: 225; label: 6.5
title: d-Heaps
pagenum: 226; label: 6.6
title: Leftist Heaps
pagenum: 227; label: 6.6.1
title: Leftist Heap Property
pagenum: 227; label: 6.6.2
title: Leftist Heap Operations
pagenum: 228; label: 6.7
title: Skew Heaps
pagenum: 235; label: 6.8
title: Binomial Queues
pagenum: 237; label: 6.8.1
title: Binomial Queue Structure
pagenum: 237; label: 6.8.2
title: Binomial Queue Operations
pagenum: 237; label: 6.8.3
title: Implementation of Binomial Queues
pagenum: 242; title: Summary
pagenum: 246; title: Exercises
pagenum: 247; title: References
pagenum: 251; label: 7
title: Sorting
pagenum: 253; label: 7.1
title: Preliminaries
pagenum: 253; label: 7.2
title: Insertion Sort
pagenum: 254; label: 7.2.1
title: The Algorithm
pagenum: 254; label: 7.2.2
title: Analysis of Insertion Sort
pagenum: 254; label: 7.3
title: A Lower Bound for Simple Sorting Algorithms
pagenum: 255; label: 7.4
title: Shellsort
pagenum: 256; label: 7.4.1
title: Worst-Case Analysis of Shellsort
pagenum: 258; label: 7.5
title: Heapsort
pagenum: 260; label: 7.6
title: Mergesort
pagenum: 262; label: 7.6.1
title: Analysis of Mergesort
pagenum: 265; label: 7.7
title: Quicksort
pagenum: 267; label: 7.7.1
title: Picking the Pivot
pagenum: 268; label: 7.7.2
title: Partitioning Strategy
pagenum: 270; label: 7.7.3
title: Small Files
pagenum: 272; label: 7.7.4
title: Actual Quicksort Routines
pagenum: 272; label: 7.7.5
title: Analysis of Quicksort
pagenum: 275; label: 7.7.6
title: A Linear-Expected-Time Algorithm for Selection
pagenum: 278; label: 7.8
title: Sorting Large Objects
pagenum: 280; label: 7.9
title: A General Lower Bound for Sorting
pagenum: 280; label: 7.9.1
title: Decision Trees
pagenum: 280; label: 7.10
title: Bucket Sort
pagenum: 283; label: 7.11
title: External Sorting
pagenum: 283; label: 7.11.1
title: Why We Need New Algorithms
pagenum: 284; label: 7.11.2
title: Model for External Sorting
pagenum: 284; label: 7.11.3
title: The Simple Algorithm
pagenum: 284; label: 7.11.4
title: Multiway Merge
pagenum: 286; label: 7.11.5
title: Polyphase Merge
pagenum: 287; label: 7.11.6
title: Replacement Selection
pagenum: 288; title: Summary
pagenum: 289; title: Exercises
pagenum: 290; title: References
pagenum: 293; label: 8
title: The Disjoint Set ADT
pagenum: 297; label: 8.1
title: Equivalence Relations
pagenum: 297; label: 8.2
title: The Dynamic Equivalence Problem
pagenum: 298; label: 8.3
title: Basic Data Structure
pagenum: 299; label: 8.4
title: Smart Union Algorithms
pagenum: 303; label: 8.5
title: Path Compression
pagenum: 306; label: 8.6
title: Worst Case for Union-by-Rank and Path Compression
pagenum: 307; label: 8.6.1
title: Analysis of the Union/Find Algorithm
pagenum: 308; label: 8.7
title: An Application
pagenum: 314; title: Summary
pagenum: 314; title: Exercises
pagenum: 315; title: References
pagenum: 316; label: 9
title: Graph Algorithms
pagenum: 319; label: 9.1
title: Definitions
pagenum: 319; label: 9.1.1
title: Representation of Graphs
pagenum: 320; label: 9.2
title: Topological Sort
pagenum: 322; label: 9.3
title: Shortest-Path Algorithms
pagenum: 326; label: 9.3.1
title: Unweighted Shortest Paths
pagenum: 327; label: 9.3.2
title: Dijkstra's Algorithm
pagenum: 333; label: 9.3.3
title: Graphs with Negative Edge Costs
pagenum: 340; label: 9.3.4
title: Acyclic Graphs
pagenum: 341; label: 9.3.5
title: All-Pairs Shortest Path
pagenum: 344; label: 9.4
title: Network Flow Problems
pagenum: 345; label: 9.4.1
title: A Simple Maximum-Flow Algorithm
pagenum: 345; label: 9.5
title: Minimum Spanning Tree
pagenum: 350; label: 9.5.1
title: Prim's Algorithm
pagenum: 350; label: 9.5.2
title: Kruskal's Algorithm
pagenum: 354; label: 9.6
title: Applications of Depth-First Search
pagenum: 356; label: 9.6.1
title: Undirected Graphs
pagenum: 357; label: 9.6.2
title: Biconnectivity
pagenum: 359; label: 9.6.3
title: Euler Circuits
pagenum: 363; label: 9.6.4
title: Directed Graphs
pagenum: 366; label: 9.6.5
title: Finding Strong Components
pagenum: 368; label: 9.7
title: Introduction to NP-Completeness
pagenum: 369; label: 9.7.1
title: Easy vs. Hard
pagenum: 370; label: 9.7.2
title: The Class NP
pagenum: 371; label: 9.7.3
title: NP-Complete Problems
pagenum: 372; title: Summary
pagenum: 374; title: Exercises
pagenum: 374; title: References
pagenum: 380; label: 10
title: Algorithm Design Techniques
pagenum: 383; label: 10.1
title: Greedy Algorithms
pagenum: 383; label: 10.1.1
title: A Simple Scheduling Problem
pagenum: 384; label: 10.1.2
title: Huffman Codes
pagenum: 387; label: 10.1.3
title: Approximate Bin Packing
pagenum: 393; label: 10.2
title: Divide and Conquer
pagenum: 401; label: 10.2.1
title: Running Time of Divide and Conquer Algorithms
pagenum: 402; label: 10.2.2
title: Closest-Points Problem
pagenum: 404; label: 10.2.3
title: The Selection Problem
pagenum: 409; label: 10.2.4
title: Theoretical Improvements for Arithmetic Problems
pagenum: 412; label: 10.3
title: Dynamic Programming
pagenum: 416; label: 10.3.1
title: Using a Table Instead of Recursion
pagenum: 416; label: 10.3.2
title: Ordering Matrix Multiplications
pagenum: 419; label: 10.3.3
title: Optimal Binary Search Tree
pagenum: 422; label: 10.3.4
title: All-Pairs Shortest Path
pagenum: 425; label: 10.4
title: Randomized Algorithms
pagenum: 428; label: 10.4.1
title: Random Number Generators
pagenum: 429; label: 10.4.2
title: Skip Lists
pagenum: 433; label: 10.4.3
title: Primality Testing
pagenum: 436; label: 10.5
title: Backtracking Algorithms
pagenum: 438; label: 10.5.1
title: The Turnpike Reconstruction Problem
pagenum: 439; label: 10.5.2
title: Games
pagenum: 444; title: Summary
pagenum: 450; title: Exercises
pagenum: 451; title: References
pagenum: 458; label: 11
title: Amortized Analysis
pagenum: 463; label: 11.1
title: An Unrelated Puzzle
pagenum: 464; label: 11.2
title: Binomial Queues
pagenum: 464; label: 11.3
title: Skew Heaps
pagenum: 469; label: 11.4
title: Fibonacci Heaps
pagenum: 471; label: 11.4.1
title: Cutting Nodes in Leftist Heaps
pagenum: 472; label: 11.4.2
title: Lazy Merging for Binomial Queues
pagenum: 474; label: 11.4.3
title: The Fibonacci Heap Operations
pagenum: 478; label: 11.4.4
title: Proof of the Time Bound
pagenum: 479; label: 11.5
title: Splay Trees
pagenum: 481; title: Summary
pagenum: 485; title: Exercises
pagenum: 486; title: References
pagenum: 487; title: Index
pagenum: 489