Data Structures and Algorithm Analysis in C++by Mark Allen Weiss
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
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.
- Publication date:
Read an Excerpt
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
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
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.
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
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
Meet the Author
Mark Allen Weiss is Professor and Associate Director for the School of Computing and Information Sciences at Florida International University. He is also currently serving as both Director of Undergraduate Studies and Director of Graduate Studies. He received his Bachelor’s Degree in Electrical Engineering from the Cooper Union in 1983, and his Ph.D. in Computer Science from Princeton University in 1987, working under Bob Sedgewick. He has been at FIU since 1987 and was promoted to Professor in 1996. His interests include data structures, algorithms, and education. He is most well-known for his highly-acclaimed Data Structures textbooks, which have been used for a generation by roughly a million students.
Professor Weiss is the author of numerous publications in top-rated journals and was recipient of the University’s Excellence in Research Award in 1994. In 1996 at FIU he was the first in the world to teach Data Structures using the Java programming language, which is now the de facto standard. From 1997-2004 he served as a member of the Advanced Placement Computer Science Development Committee, chairing the committee from 2000-2004. The committee designed the curriculum and wrote the AP exams that were taken by 20,000 high school students annually.
In addition to his Research Award in 1994, Professor Weiss is also the recipient of the University’s Excellence in Teaching Award in 1999 and the School of Computing and Information Science Excellence in Teaching Award (2005) and Excellence in Service Award (2007).
Most Helpful Customer Reviews
See all customer reviews