Algorithms, Data Structures, and Problem Solving With C++ - Hardcover

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.

It might have been preferable to write the book in a language-independent fashion, concentrating only on general principles such as the theory of the data structures and referring to C++ code only in passing, but that is impossible. C++ code is complex, and readers will need to see complete examples to understand some of the finer points. As mentioned earlier, a brief review of the simpler parts of C++ is provided in Appendix A. Part I of the book describes some of C++'s more advanced features relevant to data structures.

Three parts of the language stand out as requiring special pedagogical consideration: templates, inheritance, and exceptions. The approach to this material is as follows:

Templates: Templates are used extensively. Some readers may have reservations with this approach because it complicates the code, but I have included them because they are fundamental concepts in any sophisticated C++ program.

Inheritance: Inheritance is used relatively sparingly because it adds complications, and data structures are not a strong application area for it. The main instance in which it is used is to derive implementations of data structures from abstract specifications.

Exceptions: At the time of this writing, development of exceptions is several years behind that of templates. They are not universally implemented, and the exact semantics have yet to be standardized. Eventually they will be standardized, they will work, and they will be widely used. In recognition of this, my preference would have been to include them, but except for the handling of memory exhaustion, this is not possible right now. Consequently, exceptions are not otherwise used in the code. However, throughout the text we use the function EXCEPTION, described in Appendix D, to signal points at which an exception could be used. Appendix D also describes how to incorporate exceptions into the code should they be available on your compiler.

Text Organization This text introduces C++ and object-oriented programming (particularly abstraction) in Part I. We discuss pointers, arrays, and some other C++ topics and then go on to discuss the syntax and use of classes, templates, and inheritance.

Part II discusses Big-Oh and algorithmic paradigms, including recursion and randomization. Sorting is covered in a full chapter, and basic data structures are described in another chapter. The interfaces and running times of the data structures are presented without giving the implementations. The instructor then may take several approaches to present the remaining material. Two of these are:

Use the corresponding implementations in Part IV as each data structure is described. The instructor can ask students to extend the classes in various ways, as suggested in the exercises.

Show how the interface is used and cover implementation at a later point in the course. The case studies in Part III can be used to support this approach. Since complete implementations will be available on the internet, the instructor can provide a library of classes for use in programming projects. Details on using this approach are given below.

Part V describes advanced data structures such as splay trees, pairing heaps, and the disjoint set data structure that can be covered if time permits.

Chapter-by-Chapter Text Organization Part I consists of four chapters describing some advanced features of C++ that are used throughout the text. Chapter 1 describes pointers, arrays, and structures and also contains a short study that describes how a profiling tool is used to measure the running time of a program. Chapter 2 begins the discussion of object-oriented programming by describing the class mechanism in C++. Chapter 3 continues this discussion by examining templates, and Chapter 4 illustrates the use of inheritance. Several components, including strings and vectors, are written in these chapters.

Part II is about the basic algorithms and building blocks. In Chapter 5 a complete discussion of time complexity and Big-Oh notation is provided. Binary search is discussed and analyzed here. Chapter 6 is a crucial chapter that discusses the interface to the data structures and argues intuitively what the running time of the supported operations should be for each data structure. However, implementation of these data structures is not provided until Part IV. Chapter 7 describes recursion by first introducing the notion of proof by induction. This chapter also discusses divide-and-conquer, dynamic programming, and backtracking. One section describes several recursive numerical algorithms that are used to implement the RSA cryptosystem. Chapter 8 describes, codes, and analyzes several basic sorting algorithms, including the insertion sort, Shellsort, mergesort, and quicksort, as well as indirect sorting. It also proves the classic lower bound for sorting and discusses the related problems of selection. Finally, Chapter 9 is a short chapter that discusses random numbers, including their generation and use in randomized algorithms.

Part III provides several case studies, and each chapter is organized along a general theme. Chapter 10 illustrates several important techniques by examining games. Chapter 11 discusses the use of stacks in computer languages by examining an algorithm to check for balanced symbols and the classic operator precedence parsing algorithm. Complete implementations with code are provided for both algorithms. Chapter 12 discusses the basic utilities of file compression and cross-reference generation, and a complete implementation of the cross-reference generator is provided. Chapter 13 broadly examines simulation by looking at one problem that can be viewed as a simulation and then the more classic event-driven simulation. Finally, Chapter 14 illustrates how data structures are used to implement several shortest path algorithms efficiently for graphs.

The data structure implementations that correspond to the interfaces in Chapter 6 are presented in Part IV. Some mathematics is used in this part, especially in Chapters 18 to 20, and can be skipped at the discretion of the instructor. Chapter 15 provides implementations for both stacks and queues. First these data structures are implemented using a dynamic array; then they are implemented using linked lists. In Chapter 16 general linked lists are described. Extensions such as doubly linked lists, circular linked lists, and cursor implementations are left as exercises. Chapter 17 describes trees and illustrates the basic traversal schemes. Chapter 18 is a detailed chapter that provides several implementations of binary search trees. Initially, the basic binary search tree is shown, and then a binary search tree that supports order statistics is derived. AVL trees are discussed but not implemented; however, the more practical red black trees and AA-trees are implemented. Finally, the B-tree is examined. Chapter 19 discusses hash tables, and the quadratic probing scheme is implementated after examination of a simpler alternative. In Chapter 20 we describe the binary heap and examine heapsort and external sorting.

Part V contains material that is suitable for use in a more advanced course or for general reference. The algorithms are accessible even at the first-year level; however, for completeness we have included sophisticated mathematical analyses that are almost certainly beyond the reach of a first-year student. Chapter 21 describes the splay tree, which is a binary search tree that seems to perform extremely well in practice and is also competitive with the binary heap in some applications that require priority queues. Chapter 22 describes priority queues that support merging operations and provides an implementation of the pairing heap. Finally, Chapter 23 examines the classic disjoint set data structure.

Course Organization Ignoring factors such as the balance between theory and practice, the crucial issue in teaching the course is deciding how the materials in Parts II to IV are to be used. The material in Part I should be covered in depth, and the student should write one or two programs that illustrate the design, implementation, and testing of classes and template classes, and depending on how much C++ is desired to be taught, inheritance. Next, Chapter 5 discusses Big-Oh, and an exercise in which the student writes a short program and compares the running time with an analysis can be given to test comprehension.

In the separation approach, the key concept of Chapter 6 is simply the fact that different data structures support different access schemes with different efficiency. Students can be asked first to write an inefficient data structure. Any case study (except the tic-tac-toe example that uses recursion) can be used to test their programs, and the students can compare their inefficient data structures with an efficient library routine (provided by anonymous ftp, as discussed below). In this scheme all the case studies (except tic-tac-toe) can be examined to see how each of the particular data structures is used. In this way we see the interface for each data structure, and we see how it is used, but we do not see how it is efficiently implemented. This is truly a separation, and viewing things this way will greatly enhance the ability of students to think abstractly. Students can be asked to extend the case study but, once again, do not have to know any of the details of the data structures.

The implementation of the data structures can be discussed afterward, and recursion can be introduced whenever the instructor feels it is appropriate (but prior to binary search trees). The details of sorting can be discussed at any point after recursion. At this point the course can continue by using the same case studies and experimenting with modifications to the implementations of the data structures. For instance, the student can experiment with various forms of balanced binary search trees.

Instructors opting for a more traditional approach can simply discuss a case study in Part III after discussing a data structure implementation in Part IV. The book chapters are meant to be as independent of each other as possible.

Exercises Exercises come in various flavors. The basic In Short exercise asks a simple question or requires hand-drawn ...

Features

Retains an emphasis on data structures and algorithm design while using C++ as the language of implementation.

Reinforces abstraction by discussing interface and implementations of data structures in different parts of the book.

Incorporates case studies such as expression evaluation, cross-reference generation, and shortest path calculations.

Provides a complete discussion of time complexity and Big-Oh notation early in the text.

Gives the instructor flexibility in choosing an appropriate balance between practice, theory, and level of C++ detail. Contains optional advanced material in Part V.

Covers classes, templates, and inheritance as fundamental concepts in sophisticated C++ programs.

Contains fully functional code that has been tested on g++2.6.2, Sun 3.0.1, and Borland 4.5 compilers. Code is integrated into the book and also available by ftp.

Includes end-of-chapter glossaries, summaries of common errors, and a variety of exercises.