About the Book
This volume examines the main features of C++ and provides a modern treatment of data structures and their implementations as objects that demonstrates many of the most innovative features of C++. The book includes many modern data structures such as leftish heaps, skew heaps, Fibonacci heaps and splay trees. It integrates algorithm analysis with the data structures material focusing on performance and running time. It also offers high-level analysis material such as amortized analysis.
Table of Contents:
Introduction - what's the book about?, mathematics review, a brief introduction to recursion, C++ at a glance; algorithm analysis - mathematical background, model, what to analyze, running time calculations; lists, stacks, and queues - abstract data types, 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, B-trees; hashing - general idea, hash function, open hashing, closed hashing, 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, shellsort, heapsort, Mergesort, quicksort, sorting large records, a general lower bound for sorting, bucket sort, external 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, topological 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.
About the Author :
Mark Allen Weiss is a Professor in the School of Computer Science at Florida International University. He received his Ph.D. in Computer Science from Princeton University where he studied under Robert Sedgewick. Dr.Weiss has received FIU's Excellence in Research Award, as well as the Teaching Incentive Program Award, which was established by the Florida Legislature to recognize teaching excellence. Mark Allen Weiss is on the Advanced Placement Computer Science Development Committee. He is the successful author of Algorithms, Data Structures, and Problem Solving with C++ and the series Data Structures and Algorithm Analysis in Pascal, Ada, C, and C++, with Addison-Wesley.
0805354433AB04062001
