Skip to content

Data Structures and Algorithm Analysis in C++

ISBN-10: 0201361221

ISBN-13: 9780201361223

Edition: 2nd 1999

Authors: Mark Allen Weiss

List price: $131.20
Blue ribbon 30 day, 100% satisfaction guarantee!
what's this?
Rush Rewards U
Members Receive:
Carrot Coin icon
XP icon
You have reached 400 XP and carrot coins. That is the daily max!

Description:

In this second edition of his successful book, experienced teacher and author Mark Allen Weiss continues to refine and enhance his innovative approach to algorithms and data structures. Written for the advanced data structures course, this text highlights theoretical topics like abstract data types and the efficiency of algorithms, as well as performance and running time. Before covering algorithms and data structures, the author provides a brief introduction to C++ for programmers unfamiliar with the language. All of the source code will be available over the Internet. Dr. Weiss also distinguishes the book with his clear, friendly writing style, logical organization of topics, and extensive use of figures and examples that show the successive stages of an algorithm.
Customers also bought

Book details

List price: $131.20
Edition: 2nd
Copyright year: 1999
Publisher: Addison-Wesley Longman, Incorporated
Publication date: 11/9/1998
Binding: Hardcover
Pages: 564
Size: 7.75" wide x 9.50" long x 1.00" tall
Weight: 2.398
Language: English

Introduction
What's the Book About?
Mathematics Review
Exponents
Logarithms
Series
Modular Arithmetic
The P Word
A Brief Introduction to Recursion
C++ Classes
Basic class Syntax
Extra Constructor Syntax and Accessors
Separation of Interface and Implementation
Vector and string
C++ Details
Pointers
Parameter Passing
Return Passing
Reference Variables
The Big Three: Destructor, Copy Constructor, operator=
The World of C
Templates
Function Templates
Class Templates
Object, Comparable, and an Example
Using Matrices
The Data Members, Constructor, and Basic Accessors
Operator
Destructor, Copy Assignment, Copy Constructor
Summary
Exercises
References
Algorithm Analysis
Mathematical Background
Model
What to Analyze
Running Time Calculations
A Simple Example
General Rules
Solutions for the Maximum Subsequence Sum Problem
Logarithms in the Running Time
Checking Your Analysis
A Grain of Salt
Summary
Exercises
References
Lists, Stacks, and Queues
Abstract Data Types (ADTs)
The List ADT
Simple Array Implementation of Lists
Linked Lists
Programming Details
Memory Reclamation and the Big Three
Doubly Linked Lists
Circular Linked Lists
Examples
Cursor Implementation of Linked Lists
The Stack ADT
Stack Model
Implementation of Stacks
Applications
The Queue ADT
Queue Model
Array Implementation of Queues
Applications of Queues
Summary
Exercises
Trees
Preliminaries
Implementation of Trees
Tree Traversals with an Application
Binary Trees
Implementation
An Example: Expression Trees
The Search Tree ADT-Binary Search Trees
Find
FindMin and findMax
Insert
Remove
Destructor and Copy Assignment Operator
Average-Case Analysis
AVL Trees
Single Rotation
Double Rotation
Splay Trees
A Simple Idea (That Does Not Work)
Splaying
Tree Traversals (Revisited)
B-Trees
Summary
Exercises
References
Hashing
General Idea
Hash Function
Separate Chaining
Open Addressing
Linear Probing
Quadratic Probing
Double Hashing
Rehashing
Extendible Hashing
Summary
Exercises
References
Priority Queues (Heaps)
Model
Simple Implementations
Binary Heap
Structure Property
Heap-Order Property
Basic Heap Operations
Other Heap Operations
Applications of Priority Queues
The Selection Problem
Event Simulation
D-Heaps
Leftist Heaps
Leftist Heap Property
Leftist Heap Operations
Skew Heaps
Binomial Queues
Binomial Queue Structure
Binomial Queue Operations
Implementation of Binomial Queues
Summary
Exercises
References
Sorting
Preliminaries
Insertion Sort
The Algorithm
Analysis of Insertion Sort
A Lower Bound for Simple Sorting Algorithms
Shellsort
Worst-Case Analysis of Shellsort
Heapsort
Analysis of Heapsort
Mergesort
Analysis of Mergesort
Quicksort
Picking the Pivot
Partitioning Strategy
Small Arrays
Actual Quicksort Routines
Analysis of Quicksort
A Linear-Expected-Time Algorithm for Selection
Indirect Sorting
Vector<Comparable *>
Does Not Work
Smart Pointer Class
Overloading operator
Dereferencing a Pointer with *
Overloading the Type Conversion Operator
Implicit Type Conversions Are Everywhere
Dual-Direction Implicit Conversions Can Cause Ambiguities
Pointer Subtraction Is Legal
A General Lower Bound for Sorting
Decision Trees
Bucket Sort
External Sorting
Why We Need New Algorithms
Model for External Sorting
The Simple Algorithm
Multiway Merge
Polyphase Merge
Replacement Selection
Summary
Exercises
References
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
Analysis of the Union/Find Algorithm
An Application
Summary
Exercises
References
Graph Algorithms
Definitions
Representation of Graphs
Topological Sort
Shortest-Path Algorithms
Unweighted Shortest Paths
Dijkstra's Algorithm
Graphs with Negative Edge Costs
Acyclic Graphs
All-Pairs Shortest Path
Network Flow Problems
A Simple Maximum-Flow Algorithm
Minimum Spanning Tree
Prim's Algorithm
Kruskal's Algorithm
Applications of Depth-First Search
Undirected Graphs
Biconnectivity
Euler Circuits
Directed Graphs
Finding Strong Components
Introduction to NP-Completeness
Easy vs. Hard
The Class NP
NP-Complete Problems
Summary
Exercises
References
Algorithm Design Techniques
Greedy Algorithms
A Simple Scheduling Problem
Huffman Codes
Approximate Bin Packing
Divide and Conquer
Running Time of Divide and Conquer Algorithms
Closest-Points Problem
The Selection Problem
Theoretical Improvements for Arithmetic Problems
Dynamic Programming
Using a Table Instead of Recursion
Ordering Matrix Multiplications
Optimal Binary Search Tree
All-Pairs Shortest Path
Randomized Algorithms
Random Number Generators
Skip Lists
Primality Testing
Backtracking Algorithms
The Turnpike Reconstruction Problem
Games
Summary
Exercises
References
Amortized Analysis
An Unrelated Puzzle
Binomial Queues
Skew Heaps
Fibonacci Heaps
Cutting Nodes in Leftist Heaps
Lazy Merging for Binomial Queues
The Fibonacci Heap Operations
Proof of the Time Bound
Splay Trees
Summary
Exercises
References
Advanced Data Structures and Implementation
Top-Down Splay Trees
Red-Black Trees
Bottom-Up Insertion
Top-Down Red-Black Trees
Top-Down Deletion
Deterministic Skip Lists
AA-Trees
Treaps
K-d Trees
Pairing Heaps
Summary
Exercises
References
The Standard Template Library
Introduction
Basic STL Concepts
Header Files and the using Directive
Containers
iterator
Pairs
Function Objects
Unordered Sequences: vector and list
vector versus list
Stacks and Queues
Sets
Maps
Example: Generating a Concordance
STL Version
Version without Using the STL
Example: Shortest-Path Calculation
STL Implementation
Version without Using the STL
Other STL Features
vector and string Classes
First-Class versus Second-Class Objects
vector Class
string Class
Index