CDN$ 126.60
Usually ships within 2 to 4 weeks.
Ships from and sold by Amazon.ca.
Gift-wrap available.
Quantity:1
Have one to sell?
Flip to back Flip to front
Listen Playing... Paused   You're listening to a sample of the Audible audio edition.
Learn more
See this image

Data Structures and Algorithm Analysis in C++ Hardcover – Nov 9 1998


See all 3 formats and editions Hide other formats and editions
Amazon Price New from Used from
Hardcover
"Please retry"
CDN$ 126.60
CDN$ 49.97 CDN$ 10.29

There is a newer edition of this item:


2014 Books Gift Guide
Thug Kitchen is featured in our 2014 Books Gift Guide. More gift ideas



Product Details

  • Hardcover: 564 pages
  • Publisher: Addison Wesley; 2 edition (Nov. 9 1998)
  • Language: English
  • ISBN-10: 0201361221
  • ISBN-13: 978-0201361223
  • Product Dimensions: 19 x 3.2 x 23.5 cm
  • Shipping Weight: 1.2 Kg
  • Average Customer Review: 3.4 out of 5 stars  See all reviews (19 customer reviews)
  • Amazon Bestsellers Rank: #715,445 in Books (See Top 100 in Books)
  • See Complete Table of Contents

Product Description

From the Inside Flap

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, 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

Customer Reviews

3.4 out of 5 stars

Most helpful customer reviews

By dag robole on July 30 2002
Format: Hardcover
As a computer science student having this book for (dinner) my course in structures and algorithms, my comment will not be of the fool proof theoretical academical type.
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
(like Deitel&Deitel).
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)
Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again.
Format: Hardcover
I used this book for teaching an introductory data structures and algorithms course at Long Beach St. University. In teaching or studying such a course one has to walk a fine line between giving a good theoretical presentation of the material, but at the same time discuss practical implementation issues. Weiss walks this line with good balance and agility, but his presentation of the material does raise some pedagogical issues; the most obvious being whether or not it is prudent to use C++ code in favor of psuedocode. Not an easy question to answer. One compromise would be to first present the algorithms in pseudocode and then follow it up with C++ in an appendix. This is the choice taken by Drozdek, in his book with the same name. To Weiss's credit, however, I do not think this would work as well. Since he does very well at explaining many practical aspects of the implementation, it seems appropriate to have the code nearby. On the other hand, there were occassions when I felt that the code seemed too advanced and overly refined for an audience consisting of mostly students who are just learning how to program in C++. It only detracts from the issues at hand, namely the data structures and algorithms.
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 ›
Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again.
By Hapazard on March 7 2001
Format: Hardcover
This book was used in CS 303 at the University of Alabama at Birmingham.
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.
My complaints:
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.
Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again.
Format: Hardcover
This book is excellent, I also own the C and Java versions and I love them all. For a long time I knew the basics of programmin, I knew Basic, VB, C, C++ and Java, but I really couldn't get anything advanced done, I simply got stuck and didn't know what to do and how.
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.
Was this review helpful to you? Yes No Sending feedback...
Thank you for your feedback. If this review is inappropriate, please let us know.
Sorry, we failed to record your vote. Please try again.

Most recent customer reviews



Feedback