Data Structures, Algorithms, and Applications in Java (2nd Edition)
by Sartaj Sahni
ISBN 0-929306-33-3
2004
870 pages, Paperback
$89.95 (US Dollars)
Author Bios: Sahni

 Summary    Contents 

Table of Contents:

• PART I PRELIMINARIES
• Chapter 1 Java Review
  • Introduction
  • Structure of a Java Program
  • The Java Compiler and Virtual Machine
  • Documentation Comments
  • Data Types
  • Methods
  • Exceptions
  • Your Very Own Data Type
  • Access Modiers
  • Inheritance and Method Overriding
  • Currency Revisited
  • Defining an Exception Class
  • Generic Methods
  • Garbage Collection
  • Recursion
  • Testing and Debugging
  • References and Selected Readings
• Chapter 2 Performance Analysis of Programs
  • 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
  • The Class java.util.ArrayList
  • 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 Linear Lists - Simulated Pointers
  • The Need for Simulated Pointers
  • Simulating Pointers
  • MemoryManagement
  • Comparison with Garbage Collection
  • Simulated Chains
  • MemoryManaged Chains
  • ApplicationUnion-Find Problem
• Chapter 8 Arrays and Matrices
  • Arrays
  • Matrices
  • Special Matrices
  • Sparse Matrices
• Chapter 9 Stacks
  • Definition and Applications
  • The Abstract Data Type
  • Array Representation
  • Linked Representation
  • Applications
  • References and Selected Readings
• Chapter 10 Queues
  • Definition and Applications
  • The Abstract Data Type
  • Array Representation
  • Linked Representation
  • Applications
  • References and Selected Readings
• Chapter 11 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 12 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 13 Priority Queues
  • Definition and Applications
  • The Abstract Data Type
  • Linear Lists
  • Heaps
  • Leftist Trees
  • Applications
  • References and Selected Readings
• Chapter 14 Tournament Trees
  • Winner Trees and Applications
  • The ADT WinnerTree
  • Winner Tree Implementation
  • Loser Trees
  • Applications
  • References and Selected Readings
• Chapter 15 Binary Search Trees
  • Definitions
  • Abstract Data Types
  • Binary Search Tree Operations and Implementation
  • Binary Search Trees with Duplicates
  • Indexed Binary Search Trees
  • Applications
• Chapter 16 Balanced Search Trees
  • AVL Trees
  • Red-Black Trees
  • Splay Trees
  • B-Trees
  • References and Selected Readings
• Chapter 17 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 18 The Greedy Method
  • Optimization Problems
  • The Greedy Method
  • Applications
  • References and Selected Readings
• Chapter 19 Divide and Conquer
  • The Method
  • Applications
  • Solving Recurrence Equations
  • Lower Bounds on Complexity
• Chapter 20 Dynamic Programming
  • The Method
  • Applications
  • References and Selected Readings
• Chapter 21 Backtracking (On the Web)
  • The Method
  • Applications
• Chapter 22 Branch and Bound (On the Web)
  • The Method
  • Applications