Data Structures and Algorithm Analysis in C++ Book

Mathematical Background * Model * What to Analyze * Running Time Calculations

LISTS, STACKS, AND QUEUES

Abstract Data Types (ADTs) * The List ADT * The Stack ADT * The Queue

ADT TREES

Preliminaries * Binary Trees * The Search Tree ADT: Binary Search Trees * AVL Trees * Splay

Trees * Tree Traversals (Revisited) * B-Trees

HASHING

General Idea * Hash Function * Separate Claiming * Open Addressing * Rehashing * Extendible Hashing

PRIORITY QUEUES (HEAPS)

Model * Simple Implementations * Binary Heap * Applications of Priority Queues * d-heaps *Leftist Heaps * Skew Heaps * Binomial Queues

SORTING

Preliminaries * Insertion Sort * A Lower Bound for Simple Sorting Algorithms * Shellsort * Heapsort * Mergesort * Quicksort * Sorting Large Structures * A General Lower Bound for Sorting * Bucket Sort * Extemal Sorting

THE DISJOINT SET ADT

Equivalence Relations * The Dynamic Equivalence Problem * Basic Data Structure * Smart Union Algorithms * Path Compression * Worst Case for Union-by Rank And Path Compression *An Application

GRAPH ALGORITHMS

Definitions * Topologic Al Sort * Shortest-Path Algorithms * Network Flow Problems * Minimum Spanning Tree * Applications of Depth-First Search * Introduction to NP-Completeness

ALGORITHM DESIGN TECHNIQUES

Greedy Algorithms * Divide And Conquer * Dynamic Programming * Randomized Algorithms * Backtracking Algorithms

AMORTIZED ANALYSIS

An Unrelated Puzzle * Binomial Queues * Skew Heaps * Fibonacci Heaps * Splay Trees

ADVANCED DATA STRUCTURES AND IMPLEMENTATION

Top-Down Splay Trees * Red Black Trees * Deterministic Skip Lists * A A-Trees * Treaps k-d Trees * Pairing Heaps

APPENDIX A: THE STANDARD TEMPLATE LIBRARY

Introduction * Basic STL Concepts * Unordered Sequences: vector And list * Sets * Maps * Example: Generating a Concordance * Example: Shortest Path Calculation

APPENDIX B: VECTOR AND STRING CLASSES

Vector Class string Class

END