Data Structures and Algorithm Analysis in C++ / Edition 3

Data Structures and Algorithm Analysis in C++ / Edition 3

by Mark A. Weiss
     
 

View All Available Formats & Editions

ISBN-10: 032144146X

ISBN-13: 9780321441461

Pub. Date: 02/28/2006

Publisher: Prentice Hall

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second. Class templates are used to describe generic data structures and first-class versions of vector and string classes are used. Included is an appendix on a

Overview

In this text, readers are able to look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from several years to less than a second. Class templates are used to describe generic data structures and first-class versions of vector and string classes are used. Included is an appendix on a Standard Template Library (STL). This text is for readers who want to learn good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. Readers should have some knowledge of intermediate programming, including topics as object-based programming and recursion, and some background in discrete math.

Product Details

ISBN-13:
9780321441461
Publisher:
Prentice Hall
Publication date:
02/28/2006
Edition description:
3RD
Pages:
586
Product dimensions:
7.60(w) x 9.30(h) x 1.00(d)

Table of Contents

What's the Book About? * Mathematics Review * A Brief Introduction to Recursion * C++ Classes* C++ Details * Templates * Using Matrices

ALGORITHM ANALYSIS

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

Customer Reviews

Average Review:

Write a Review

and post it to your social network

     

Most Helpful Customer Reviews

See all customer reviews >