Data Structures and Algorithm Analysis in C++ (2nd Edition) Hardcover – Nov 9 1998
There is a newer edition of this item:
Customers Who Bought This Item Also Bought
No Kindle device required. Download one of the Free Kindle apps to start reading Kindle books on your smartphone, tablet, and computer.
Getting the download link through email is temporarily not available. Please check back later.
To get the free app, enter your mobile phone number.
From the Inside Flap
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-based programming, 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.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 ftp.awl.com/cseng/authors/weiss.The exact location of this material may change.Acknowledgments
Many, many people have helped me in the preparation of books in this series. Some are listed in other versions of the book; thanks to all.
As usual, the writing process was made easier by the professionals at Addison Wesley Longman. I'd like to thank my editor, Susan Hartman; associate editor, Katherine Harutunian; and production editor, Pat Unubun. I'd also like to thank Kris Engberg and her staff at Publication Services for their usual fine work putting the final pieces together.
I would like to thank the reviewers, who provided valuable comments, many of which have been incorporated into the text. For this edition, they are Phillip T. Conrad (Temple University), Robin Hill (University of Wyoming), Bob Robinson (University of Georgia), Gurdip Singh (Kansas State University), Bernard M. Waxman (Southern Illinois University at Edwardsville), and William W. White (Southern Illinois University at Edwardsville).
Finally, I'd like to thank the numerous readers who have sent e-mail messages and pointed out errors or inconsistencies in earlier versions.
From the Back Cover
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 such as 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. Dr. Weiss's clear writing style, logical organization of topics, and extensive use of figures and examples to demonstrate the successive stages of an algorithm make this an accessible, valuable text.New to this Edition
- An appendix on the Standard Template Library (STL)
- C++ code, tested on multiple platforms, that conforms to the ANSI ISO final draft standard
0201361221B04062001 See all Product Description
Top Customer Reviews
I find this book very useful.
It has a lot of code examples, and in my oppinion it is perfect
for those who has some experience writing C++ code.
The implementations rely heavily on templates, which
(will effectively scare away the remaining students)
is actualy irrelevant when it comes to most of the algorithms.
I say this even if our course only covered 60-70 % of the book.
Luckily for me, I already loved templates when I started the course, but I dont think this was the case for most of my fellow students.
The book is vell organized, and it has a lot of "easy to understand" drawings all the way through.
It starts with a tutorial on advanced C++ topics for those who just finished their ABC book in C++ programming
The code examples are very professional, tight and bug free.
If you are happy writing C code, this book is not for you.
There is some use of STL througout the book, but it does not require you to be an expert on the topic.
I think it has a deep and thorough examination of all the topics, and it covers more structures and algorithms I could dream of for at least the next 2 years.
I recommend this book to all C++ code writing engineer students
(who are not afraid of irrelevant templates)
With so much detail paid to implementation issues, one aspect of the subject (possibly the most important aspect) that suffers most is the mathematical analysis. Frankly, there just isn't enough of it, to at least support many of the more advanced problems posed at the end of each chapter. Although an abundance of such problems is supplied, it would have helped to see a sample of them worked out as examples throughout the main text.
On a more positive note however, I did enjoy Weiss's down-to-earth style of writing.Read more ›
It is overall a good book and covers many topics in a reasonable depth. Its very readable and definitely worth the buy. The *best* part are the supplied references at the end of each chapter.
1. Focuses on a Specific language. While there are editions for a number of languages, Weiss does not give pseudo code implementations, so you have to rely on your programming knowledge. While this is beneficial since it grounds the details in a real language, I'd rather not get in the details at this point. And things like necessary operations for data structures are provided only in code form, so you have to read and understand the code. That is more a practical concern that shouldnt be focused on. I prefer a higher level, more mathematically intense analysis.
2. No answer to questions asked at the end of the section. This would be nice, especially for independent study, but not overly needed in this book. Its written well enough that it is not as much of a requirement.
3. The mathematical treatment of the algorithm analysis is a bit lacking. What little there is is not well explained. For those without the needed background, its useless, for those with a moderate background a sufficient amount of detail is not provided.
This book changed it all. But make sure you are ready for this. Some have said that this is for academics only or that it is too difficult. You MUST know the basics first! Someone complained that the code is uncommented, Geez... The code fragments are quite short and very basic C++. If you don't know how to handle structs, templates, pointers and variable operations, then don't complain that this book is too difficult. You just haven't got the basics yet.
When you know the basics but need to know how to store data into the memory for the optimal use (instead of relying on arrays for everything), you must read a book on Data Structures and this book is among the best. Yes, it makes you work, yes you have to read carefully through the examples, but that is the nature of these things. You are no longer a beginner in first grade.
It is good to know some math, but if you don't need to learn the analysis (mostly for academic use) then you can skip the analysis stuff. Just learn to implement the structures and algorithms, the text will tell you which are the best ones.
Most recent customer reviews
A realy good book, for an old version. If you are a CS student this book is for you, it would be better if it contained solutions of the exercices in the same book, but its not a... Read morePublished on May 26 2012 by Ismayl
This book is impossible to learn from unless you know c++ like the person who wrote the language. I am using this book for my data structures class I'm in right now and it is... Read morePublished on May 21 2003 by Chris Wilson
This is my second time taking this class. The only reason, and I do mean the only reason why I have to retake this class is because many of the examples in the book are confusing. Read morePublished on Nov. 10 2002
As a C.S. major, I had to buy this book for my class. The author uses concise vocabulary and explanations, and gets straight 2 the point. The best part of this book are the ref. Read morePublished on Aug. 3 2002
I am currently taking advanced data and file structures and this book is somewhat helpful. I have not needed to refer to the book that much while taking the course. Read morePublished on April 28 2000
This is the textbook for my undergraduate data structures class. In my opinion this book is more suited to graduate level study, or for very experienced C programmers. Read morePublished on April 18 2000
Mark Allen Weiss did a superb job at explaining the very abstract material. I think every person interested in computer Science should read.Published on March 6 2000 by Batis Malekpour
The author writes, "...the [this] book usually provides about one-half to three-quarters of an implementation, and the student is encouraged to supply the rest. Read morePublished on Oct. 24 1999
Look for similar items by category
- Books > Computers & Technology > Computer Science > Systems Analysis & Design
- Books > Computers & Technology > Databases > Database Design
- Books > Computers & Technology > Microsoft > Development > C & C++ Windows Programming
- Books > Computers & Technology > Programming > Algorithms > Data Structures
- Books > Computers & Technology > Programming > C
- Books > Computers & Technology > Programming > Languages & Tools
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Software Development
- Books > Computers & Technology > Programming > Software Design, Testing & Engineering > Structured Design
- Books > Computers & Technology > Software > Databases
- Books > Professional & Technical > Professional Science > Mathematics
- Books > Textbooks > Computer Science & Information Systems > Algorithms
- Books > Textbooks > Computer Science & Information Systems > Computer Science
- Books > Textbooks > Computer Science & Information Systems > Database Storage & Design
- Books > Textbooks > Computer Science & Information Systems > Programming Languages