Free download : Algorithms, Data Structures, and Problem Solving With C++

Product Details

• Hardcover: 820 pages
• Publisher: Addison-Wesley (June 1996)
• Language: English
• ISBN-10: 0805316663
• ISBN-13: 978-0805316667

From the Inside Flap
This book was designed for a second course in computer science, which has typically been known as CS-2 Data Structures. The content of CS-2 has been evolving over some time, but there is general agreement that topics such as structures, pointers, and data structures should be taught, along with an introduction to algorithm analysis and a general scaling up of the complexity of programming projects.

Although the general topics of CS-2 are to some extent uniformly accepted, the language of expression has clearly not been and indeed invokes quite spirited debate among computer science educators. We use C++ in this text. C++ has a host of both benefits and disadvantages but is clearly gaining support as a prefered language in industry and academic circles.

My goal in writing this text is to provide a practical introduction to data structures and algorithms, from the viewpoint of abstract thinking and problem solving, as well as to the use of C++. I try to cover all important details concerning the data structures, the analyses, and their C++ implementations, and have stayed away from data structures that are theoretically interesting but not widely used. I have designed the textbook to allow flexibility in topic coverage for the instructor. It is impossible to cover all the C++ details, all the different data structures, and all the mathematics described in the text in a single course. The instructor will need to decide on an appropriate balance between practice, theory, and level of C++ detail.

Approach The most unique aspect of the text is the clear separation of the interface and implementation. In C++ the class mechanism allows the programmer to write the interface and implementation separately, to place them in separate files and compile separately, and to hide implementation details. In this textbook we take this a step further: The interface and implementation are discussed in separate parts of the book. Parts I, II, and III lay the groundwork, discussing basic concepts and tools and providing some practical examples, but implementation of the basic data structures are not shown until Part IV. This is the first CS-2 textbook to take this approach.

The separation of interface and implementation provides several benefits. Generally, it promotes abstract thinking: Class interfaces are written and used before the implementation is known, and it forces the reader to think about the functionality and potential efficiency of the various data structures. For example, programs that use a hash table are written hundreds of pages before the hash table is implemented. The proposed standard template library (STL) for C++ (which is likely to be mimicked in Ada and other languages) provides classes for stacks, queues, and almost all the fundamental data structures. We believe it will hasten the shift in emphasis of data structures courses from implemention to use.

Prerequisites The prerequisite is a working knowledge of small C or a C-like subset of C++, including basic data types, operators, control structures, functions, and input and output. Appendix A contains a review of this material. Students that have had a first course using C++ should be able to start at Chapter 1. Students that have had a first course using C should scan Appendix A to see the differences between C and C++. Students whose first course was neither C nor C++ will need to read Appendix A carefully. In any event, this textbook is not about C++; it is about data structures and algorithm design, which is the proper focus of a CS-2 course. Readers who are not fluent C++ programmers should have a C++ reference book available; some recommendations are listed in Chapter 1.

Discrete math is not a prerequisite. Mathematical proofs are relatively rare (except towards the end of the text), and when done they are usually preceded by a brief math review. However, establishing some of our claims requires proof; Chapters 7 and 18 through 23 require some degree of mathematical sophistication. The instructor may elect to skip mathematical aspects of the proofs by presenting only the results. All proofs in the text are clearly marked and are separate from the body of the text.

C++ Using C++ presents both advantages and disadvantages. The C++ class allows the separation of interface and implementation, as well as the hiding of internal details of the implementation. It cleanly supports the notion of abstraction. However, other languages support this also, notably Turbo Pascal and Ada. The advantage of C++ is that it is widely used in industry. Students perceive that the material they are learning is practical and will help them find employment, which provides motivation to persevere through the course. The disadvantage of C++ is that it is far from a perfect language pedagogically, especially in a second course, and thus additional care needs to be expended to avoid bad programming practices. A second disadvantage is that C++ is still not a stable language, so the various compilers behave differently.

Go to the page and save file as (.pdf)