Amazon Price  New from  Used from 
Hardcover
"Please retry"

CDN$ 126.60

CDN$ 42.94  CDN$ 4.99 
Paperback
"Please retry"

CDN$ 59.99  CDN$ 12.71 
Product Details
Would you like to update product info or give feedback on images?

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 firstyear graduate course in algorithm analysis. Students should have some knowledge of intermediate programming, including such topics as pointers, recursion, and objectbased programming, and some background in discrete math.
ApproachAlthough 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 objectbased 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 firstclass versions, instead of the secondclass 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.
OverviewChapter 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 indepth explanation of logarithmic running time. Simple recursive programs are analyzed by intuitively converting them into iterative programs. More complicated divideandconquer 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 (Btrees). 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 generalpurpose 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 NPcompleteness and undecidability) is provided.
Chapter 10 covers algorithm design by examining common problemsolving 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 kd 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 topdown redblack 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 highperformance data structures and algorithms library. Appendix B describes an implementation of vector and string.
Chapters 19 provide enough material for most onesemester data structures courses. If time permits, then Chapter 10 can be covered. A graduate course on algorithm analysis could cover Chapters 711. The advanced data structures analyzed in Chapter 11 can easily be referred to in the earlier chapters. The discussion of NPcompleteness in Chapter 9 is far too brief to be used in such a course. Garey and Johnson's book on NPcompleteness can be used to augment this text.
ExercisesExercises, 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 AvailabilityThe 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.
AcknowledgmentsMany, 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 email messages and pointed out errors or inconsistencies in earlier versions.
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