Data Structures, Algorithms, and Applications in C++ (2nd Edition)
by Sartaj Sahni
ISBN 0-929306-32-5
2004
830 pages, Paperback
$89.95 (US Dollars)
Author Bios: Sahni

 Summary    Contents 

Table of Contents:

• PART I PRELIMINARIES
• Chapter 1 C++ Review
  • Introduction
  • Functions and Parameters
  • Exceptions
  • Dynamic Memory Allocation
  • Your Very Own Data Type
  • The Exception Class illegalParameterValue
  • Recursion
  • The Standard Templates Library
  • Testing and Debugging
  • References and Selected Readings
• Chapter 2 Performance Analysis
  • What Is Performance?
  • Space Complexity
  • Time Complexity
• Chapter 3 Asymptotic Notation
  • Introduction
  • Asymptotic Notation
  • AsymptoticMathematics (Optional)
  • Complexity Analysis Examples
  • Practical Complexities
  • References and Selected Readings
• Chapter 4 Performance Measurement of Programs
  • Introduction
  • Choosing Instance Size
  • Developing the Test Data
  • Setting Up the Experiment
  • Your Cache and You
  • References and Selected Readings
• PART II DATA STRUCTURES
• Chapter 5 Linear Lists - Array Representation
  • Data Objects and Structures
  • The Linear List Data Structure
  • Array Representation
  • Vector Representation
  • Multiple Lists in a Single Array
  • Performance Measurement
  • References and Selected Readings
• Chapter 6 Linear Lists - Linked Representation
  • Singly Linked Lists and Chains
  • Circular Lists and Header Nodes
  • Doubly Linked Lists
  • Glossary of Linked List Terms
  • Applications
• Chapter 7 Arrays and Matrices
  • Arrays
  • Matrices
  • Special Matrices
  • Sparse Matrices
• Chapter 8 Stacks
  • Definition and Applications
  • The Abstract Data Type
  • Array Representation
  • Linked Representation
  • Applications
  • References and Selected Readings
• Chapter 9 Queues
  • Definition and Applications
  • The Abstract Data Type
  • Array Representation
  • Linked Representation
  • Applications
  • References and Selected Readings
• Chapter 10 Skip Lists and Hashing
  • Dictionaries
  • The Abstract Data Type
  • Linear List Representation
  • Skip List Representation (Optional)
  • Hash Table Representation
  • An Application - Text Compression
  • References and Selected Readings
• Chapter 11 Binary and Other Trees
  • Trees
  • Binary Trees
  • Properties of Binary Trees
  • Representation of Binary Trees
  • Common Binary Tree Operations
  • Binary Tree Traversal
  • The ADT BinaryTree
  • The Class LinkedBinaryTree
  • Applications
  • References and Selected Readings
• Chapter 12 Priority Queues
  • Definition and Applications
  • The Abstract Data Type
  • Linear Lists
  • Heaps
  • Leftist Trees
  • Applications
  • References and Selected Readings
• Chapter 13 Tournament Trees
  • Winner Trees and Applications
  • The ADT WinnerTree
  • Winner Tree Implementation
  • Loser Trees
  • Applications
  • References and Selected Readings
• Chapter 14 Binary Search Trees
  • Definitions
  • Abstract Data Types
  • Binary Search Tree Operations and Implementation
  • Binary Search Trees with Duplicates
  • Indexed Binary Search Trees
  • Applications
• Chapter 15 Balanced Search Trees
  • AVL Trees
  • Red-Black Trees
  • Splay Trees
  • B-Trees
  • References and Selected Readings
• Chapter 16 Graphs
  • Definitions
  • Applications and More Definitions
  • Properties
  • The ADT Graph
  • Representation of Unweighted Graphs
  • Representation of Weighted Graphs
  • Class Implementations
  • Graph Search Methods
  • Applications Revisited
• PART III ALGORITHM-DESIGN METHODS
• Chapter 17 The Greedy Method
  • Optimization Problems
  • The Greedy Method
  • Applications
  • References and Selected Readings
• Chapter 18 Divide and Conquer
  • The Method
  • Applications
  • Solving Recurrence Equations
  • Lower Bounds on Complexity
• Chapter 19 Dynamic Programming
  • The Method
  • Applications
  • References and Selected Readings
• Chapter 20 Backtracking (On the Web)
  • The Method
  • Applications
• Chapter 21 Branch and Bound (On the Web)
  • The Method
  • Applications