false
Data Structures and Algorithm Analysis in C++ by Mark Allen Weiss
BUY IT NEW
- $122.00 List price$110.36 Online price$99.32 Member price(Save 18%)Limited Time Offer! Everyone receives the Member Price on books.
See Details
- Add To List uiAction=GetAllLists&page=List&pageType=list&ean=9780321441461&productCode=BK&maxCount=100&threshold=3
DELIVERY & GIFT DETAILS:
Usually ships within 24 hours
Delivery Time and Shipping Rates
Eligible for gift wrap & gift message.
Textbook (Hardcover - 3RD)
- 586pp
- Sales Rank: 123,943
Textbook Information
- ISBN-13: 9780321441461
- Edition Description: 3RD
- Edition Number: 3
- Pub. Date: February 2006
- Publisher: Addison Wesley
Buy it Used: 5 copies from $81.74 See All Available
Customers who bought this also bought
Product Details
- Pub. Date: February 2006
- Publisher: Addison Wesley
- Format: Textbook Hardcover, 586pp
- Sales Rank: 123,943
- ISBN-13: 9780321441461
- ISBN: 032144146X
- Edition Number: 3
- Edition Description: 3RD
Synopsis
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. This edition also includes A new chapter on advanced data structures and material on the Standard Template Library that conforms to the new standard. In Addition, All code has been updated and tested on multiple p1atforms and conforms to the ANSI ISO Final Draft standard. 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 user-friendly writing style, logical organization of topics, and extensive use of figures and examples that show the successive stages of an algorithm.
Annotation
Mark Weiss uses C++ to provide a smooth introduction to object-oriented design for programmers competent in one other language. Using C++, the book delivers a series of carefully developed examples which illustrate the important concepts of object orientation alongside its main theme of data structures.
Booknews
Written for the advanced data structures course, this textbook highlights theoretical topics such as abstract data types and the efficiency of algorithms and data structures, as well as performance and running time. The second edition adds an appendix on the Standard Template Library (STL), and C++ code that conforms to the ANSI ISO final draft standard. Annotation c. by Book News, Inc., Portland, Or.
More Reviews and RecommendationsFrom the Publisher
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. This edition also includes A new chapter on advanced data structures and material on the Standard Template Library that conforms to the new standard. In Addition, All code has been updated and tested on multiple p1atforms and conforms to the ANSI ISO Final Draft standard. 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 user-friendly writing style, logical organization of topics, and extensive use of figures and examples that show the successive stages of an algorithm.
Booknews
Written for the advanced data structures course, this textbook highlights theoretical topics such as abstract data types and the efficiency of algorithms and data structures, as well as performance and running time. The second edition adds an appendix on the Standard Template Library (STL), and C++ code that conforms to the ANSI ISO final draft standard. Annotation c. by Book News, Inc., Portland, Or.
Product Details
- Pub. Date: February 2006
- Publisher: Addison Wesley
- Format: Textbook Hardcover, 586pp
- Sales Rank: 123,943
- ISBN-13: 9780321441461
- ISBN: 032144146X
- Edition Number: 3
- Edition Description: 3RD
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
Forewords & Introductions
PREFACE:Purpose/Goals
The second edition of Data Structures and Algorithms Analysis in C++ describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it Is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored.
Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency.
This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers, recursion, andobject-basedprogramming, and some background in discrete math.
Approach
Although the material in this text is largely language independent, programming requires the use of a specific language. As the title implies, we have chosen C++ for this book.
C++ has emerged as the leading systems programming language. In addition to fixing many of the syntactic flaws of C, C++ provides direct constructs (the class and template) to implement generic data structures as abstract data types.
The most difficult part of writing the book was deciding on the amount of C++ to include. Use too many features of C++, and one gets an incomprehensible text; use too few and you have little more than a C text that supports classes.
The approach we take is to present the material in an object-based approach. As such, unlike the first edition, there is no use of inheritance in the text. We use class templates to describe generic data structures. We generally avoid esoteric C++ features, and use the vector and string classes that are now part of the C++ standard. Using these first-class versions, instead of the second-class counterparts that were used in the first edition, simplifies much of the code. Because not all compilers are current, we provide a vector and string class in Appendix B; this is the class that is actually used in the online code. Chapter 1 provides a review of the C++ features that are used throughout the text.
Complete versions of the data structures, in both C++ and Java, are available on the Internet. We use similar coding conventions to make the parallels between the two languages more evident. The code has been tested on UNIX systems using g++ (2.7.2 and 2.8.1) and SunPro 4.0 and on Windows95 systems using Visual C++ 5.0 and 6.0, Borland C++ 5.0, and Codewarrior Pro Release 2.
Overview
Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5. Chapter I also includes material that serves as a review of basic C++. Included is a discussion of templates and important constructs in C++ class design.
Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail.
Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using ADTs, fast implementation of these data structures, and an exposition of some of their uses. There are almost no complete programs, but the exercises contain plenty of ideas for programming assignments.
Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. AVL trees and splay trees are introduced. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.
Chapter 5 is a relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter.
Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12.
Chapter 7 covers sorting. It is very specific with respect to coding details and analysis. All the important general-purpose sorting algorithms are covered and compared. Four algorithms are analyzed in detail: insertion sort, Shellsort, heapsort, and quicksort. External sorting is covered at the end of the chapter.Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed.
Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur In practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided.
Chapter 10 covers algorithm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details.
Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed.
Chapter 12 covers search tree algorithms, the k-d tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the top-down red-black tree in Chapter 12 can be discussed under AVL trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of vector and string.
Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text.
Exercises
Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks.
A solutions manual containing solutions to almost all the exercises is available online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability.
References
References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises.
Code Availability
The example program code in this book is available via anonymous ftp at The second edition of Data Structures and Algorithms Analysis in C++ describes data structures, methods of organizing large amounts of data, and algorithm analysis, the estimation of the running time of algorithms. As computers become faster and faster, the need for programs that can handle large amounts of input becomes more acute. Paradoxically, this requires more careful attention to efficiency, since inefficiencies in programs become most obvious when input sizes are large. By analyzing an algorithm before it Is actually coded, students can decide if a particular solution will be feasible. For example, in this text students look at specific problems and see how careful implementations can reduce the time constraint for large amounts of data from 16 years to less than a second. Therefore, no algorithm or data structure is presented without an explanation of its running time. In some cases, minute details that affect the running time of the implementation are explored. Once a solution method is determined, a program must still be written. As computers have become more powerful, the problems they must solve have become larger and more complex, requiring development of more intricate programs. The goal of this text is to teach students good programming and algorithm analysis skills simultaneously so that they can develop such programs with the maximum amount of efficiency. This book is suitable for either an advanced data structures (CS7) course or a first-year graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers, recursion, and object-basedprogramming, and some background in discrete math. Although the material in this text is largely language independent, programming requires the use of a specific language. As the title implies, we have chosen C++ for this book. C++ has emerged as the leading systems programming language. In addition to fixing many of the syntactic flaws of C, C++ provides direct constructs (the class and template) to implement generic data structures as abstract data types. The most difficult part of writing the book was deciding on the amount of C++ to include. Use too many features of C++, and one gets an incomprehensible text; use too few and you have little more than a C text that supports classes. The approach we take is to present the material in an object-based approach. As such, unlike the first edition, there is no use of inheritance in the text. We use class templates to describe generic data structures. We generally avoid esoteric C++ features, and use the Complete versions of the data structures, in both C++ and Java, are available on the Internet. We use similar coding conventions to make the parallels between the two languages more evident. The code has been tested on UNIX systems using g++ (2.7.2 and 2.8.1) and SunPro 4.0 and on Windows95 systems using Visual C++ 5.0 and 6.0, Borland C++ 5.0, and Codewarrior Pro Release 2. Chapter 1 contains review material on discrete math and recursion. I believe the only way to be comfortable with recursion is to see good uses over and over. Therefore, recursion is prevalent in this text, with examples in every chapter except Chapter 5. Chapter I also includes material that serves as a review of basic C++. Included is a discussion of templates and important constructs in C++ class design. Chapter 2 deals with algorithm analysis. This chapter explains asymptotic analysis and its major weaknesses. Many examples are provided, including an in-depth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divide-and-conquer programs are introduced, but some of the analysis (solving recurrence relations) is implicitly delayed until Chapter 7, where it is performed in detail. Chapter 3 covers lists, stacks, and queues. The emphasis here is on coding these data structures using Chapter 4 covers trees, with an emphasis on search trees, including external search trees (B-trees). The UNIX file system and expression trees are used as examples. Chapter 5 is a relatively short chapter concerning hash tables. Some analysis is performed, and extendible hashing is covered at the end of the chapter. Chapter 6 is about priority queues. Binary heaps are covered, and there is additional material on some of the theoretically interesting implementations of priority queues. The Fibonacci heap is discussed in Chapter 11, and the pairing heap is discussed in Chapter 12. Chapter 8 discusses the disjoint set algorithm with proof of the running time. This is a short and specific chapter that can be skipped if Kruskal's algorithm is not discussed. Chapter 9 covers graph algorithms. Algorithms on graphs are interesting, not only because they frequently occur In practice but also because their running time is so heavily dependent on the proper use of data structures. Virtually all of the standard algorithms are presented along with appropriate data structures, pseudocode, and analysis of running time. To place these problems in a proper context, a short discussion on complexity theory (including NP-completeness and undecidability) is provided. Chapter 10 covers algorithm design by examining common problem-solving techniques. This chapter is heavily fortified with examples. Pseudocode is used in these later chapters so that the student's appreciation of an example algorithm is not obscured by implementation details. Chapter 11 deals with amortized analysis. Three data structures from Chapters 4 and 6 and the Fibonacci heap, introduced in this chapter, are analyzed. Chapter 12 covers search tree algorithms, the k-d tree, and the pairing heap. This chapter departs from the rest of the text by providing complete and careful implementations for the search trees and pairing heap. The material is structured so that the instructor can integrate sections into discussions from other chapters. For example, the top-down red-black tree in Chapter 12 can be discussed under Chapters 1-9 provide enough material for most one-semester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 7-11. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NP-completeness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NP-completeness can be used to augment this text. Exercises, provided at the end of each chapter, match the order in which material is presented. The last exercises may address the chapter as a whole rather than a specific section. Difficult exercises are marked with an asterisk, and more challenging exercises have two asterisks. A solutions manual containing solutions to almost all the exercises is available online to instructors from the Addison Wesley Longman Publishing Company. Instructors should contact their Addison-Wesley local sales representative for information on the manual's availability. References are placed at the end of each chapter. Generally the references either are historical, representing the original source of the material, or they represent extensions and improvements to the results given in the text. Some references represent solutions to exercises. The example program code in this book is available via anonymous ftp at ftp.awl.com/cseng/authors/weiss. It is also accessible through the World Wide Web; the URL is ...
Read an Excerpt
PREFACE: Purpose/Goals
Approach
vector and string classes that are now part of the C++ standard. Using these first-class versions, instead of the second-class counterparts that were used in the first edition, simplifies much of the code. Because not all compilers are current, we provide a vector and string class in Appendix B; this is the class that is actually used in the online code. Chapter 1 provides a review of the C++ features that are used throughout the text.Overview
ADTs, fast implementation of these data structures, and an exposition of some of their uses. There are almost no complete programs, but the exercises contain plenty of ideas for programming assignments.AVL trees and splay trees are introduced. More careful treatment of search tree implementation details is found in Chapter 12. Additional coverage of trees, such as file compression and game trees, is deferred until Chapter 10. Data structures for an external medium are considered as the final topic in several chapters.AVL trees (in Chapter 4). Appendix A discusses the Standard Template Library and illustrates how the concepts described in this text are applied to a high-performance data structures and algorithms library. Appendix B describes an implementation of vector and string.Exercises
References
Code Availability
ftp.awl.com/cseng/authors/weiss. It is also accessible through the World Wide Web; the URL is ...
loading...
Related EssentiaListsuiAction=GetRelatedListsByEanFromProductPage&page=List&pageType=list&ean=9780321441461&productCode=BK&maxCount=5&threshold=10
loading...
Fans of this BookuiAction=GetProfileBlurbsWithEANinFavorites&page=UserProfile&pageType=profile&eanInput=9780321441461
loading...