Data Structures and Algorithms in C++

By Michael T. Goodrich, Roberto Tamassia and David M. Mount

This book provides a comprehensive introduction to data structures and algorithms, including their design, analysis, and implementation. In terms of the computer science and computer engineering curricula, we have written this book to be primarily focused on the Freshman-Sophomore level Data Structures (CS2) course.

This is a "sister"' book to Goodrich-Tamassia, Data Structures and Algorithms in Java (DSAJ), but uses C++ as the basis language instead of Java. This present book maintains the same general structure as DSAJ, so that CS/CE programs that teach data structures in both C++ and Java can share the same core syllabus, with one course using DSAJ and the other using this book.

While this book retains the same pedagogical approach and general structure as DSAJ, the code fragments have been completely redesigned. Because the C++ language supports almost all of Java's basic constructs, it would be tempting to simply translate the code fragments from Java to the corresponding C++ counterparts. We have been careful, however, to make full use of C++'s capabilities and design code in a manner that is consistent with modern C++ usage. In particular, whenever appropriate, we use elements of C++ that are not part of Java, including templated functions and classes, the C++ Standard Template Library (STL), C++ memory allocation and deallocation (and we discuss the associated tricky issues of writing destructors, copy constructors, and assignment operators), virtual functions and virtual class destructors, stream input and output, and C++'s safe run-time casting. However, we have avoided some of C++'s more arcane or easily misused elements, such as pointer arithmetic.

Highlights of this book include:

• Review of basic features of the C++ programming language
• Introduction to object-oriented design with C++ and design patterns
• Consistent object-oriented viewpoint throughout the book
• Comprehensive coverage of all the data structures taught in a typical CS2 course, including vectors, lists, heaps, hash tables, and search trees
• Detailed explanation and visualization of sorting algorithms
• Coverage of graph algorithms and pattern-matching algorithms for more advanced CS2 courses
• Visual justifications (that is, picture proofs), which make mathematical arguments more understandable for students, appealing to visual learners
• Motivation of algorithmic concepts with Internet-related applications, such as Web browsers and search engines
• Accompanying Web site http://datastructures.net with a special password-protected area for instructors.

Click to Read More

Algorithmic Information Theory

By G J Chaitin

The aim of this book is to present the strongest possible version of G¨odel's incompleteness theorem, using an information-theoretic approach based on the size of computer programs.

One half of the book is concerned with studying , the halting probability of a universal computer if its program is chosen by tossing a coin. The other half of the book is concerned with encoding as an algebraic equation in integers, a so-called exponential diophantine equation.

G¨odel's original proof of his incompleteness theorem is essentially the assertion that one cannot always prove that a program will fail to halt. This is equivalent to asking whether it ever produces any output. He then converts this into an arithmetical assertion. Over the years this has been improved; it follows from the work on Hilbert's 10th problem that G¨odel's theorem is equivalent to the assertion that one cannot always prove that a diophantine equation has no solutions if this is the case.

In our approach to incompleteness, we shall ask whether or not a program produces an in nite amount of output rather than asking whether it produces any; this is equivalent to asking whether or not a diophantine equation has in nitely many solutions instead of asking whether or not it is solvable.

If one asks whether or not a diophantine equation has a solution for N dierent values of a parameter, the N dierent answers to this question are not independent; in fact, they are only log2 N bits of information. But if one asks whether or not there are in nitely many solutions for N dierent values of a parameter, then there are indeed cases in which the N dierent answers to these questions are independent mathematical facts, so that knowing one answer is no help in knowing any of the others. The equation encoding has this property.

When mathematicians can't understand something they usually assume that it is their fault, but it may just be that there is no pattern or law to be discovered!

How to read this book: This entire monograph is essentially a proof of one theorem, Theorem D in Chapter 8. The exposition is completely self-contained, but the collection Chaitin (1987c) is a useful source of background material. While the reader is assumed to be familiar with the basic concepts of recursive function or computability theory and probability theory, at a level easily acquired from Davis (1965) and Feller (1970), we make no use of individual results from these elds that we do not reformulate and prove here. Familiarity with LISP programming is helpful but not necessary, because we give a selfcontained exposition of the unusual version of pure LISP that we use, including a listing of an interpreter. For discussions of the history and signi cance of metamathematics, see Davis (1978), Webb (1980), Tymoczko (1986), and Rucker (1987).

Although the ideas in this book are not easy, we have tried to present the material in the most concrete and direct fashion possible. We give many examples, and computer programs for key algorithms. In particular, the theory of program-size in LISP presented in Chapter 5 and Appendix B, which has not appeared elsewhere, is intended as an illustration of the more abstract ideas in the following chapters.

Click to Download

Algorithms and Complexity

by Herbert S. Wilf

For the past several years mathematics majors in the computing track at the University of Pennsylvania have taken a course in continuous algorithms (numerical analysis) in the junior year, and in discrete algorithms in the senior year. This book has grown out of the senior course as I have been teaching it recently. It has also been tried out on a large class of computer science and mathematics majors, including seniors and graduate students, with good results.

Selection by the instructor of topics of interest will be very important, because normally I’ve found that I can’t cover anywhere near all of this material in a semester. A reasonable choice for a first try might be to begin with Chapter 2 (recursive algorithms) which contains lots of motivation. Then, as new ideas are needed in Chapter 2, one might delve into the appropriate sections of Chapter 1 to get the concepts and techniques well in hand. After Chapter 2, Chapter 4, on number theory, discusses material that is extremely attractive, and surprisingly pure and applicable at the same time. Chapter 5 would be next, since the foundations would then all be in place. Finally, material from Chapter 3, which is rather independent of the rest of the book, but is strongly connected to combinatorial algorithms in general, might be studied as time permits.

Throughout the book there are opportunities to ask students to write programs and get them running. These are not mentioned explicitly, with a few exceptions, but will be obvious when encountered. Students should all have the experience of writing, debugging, and using a program that is nontrivially recursive, for example. The concept of recursion is subtle and powerful, and is helped a lot by hands-on practice. Any of the algorithms of Chapter 2 would be suitable for this purpose. The recursive graph algorithms are particularly recommended since they are usually quite foreign to students’ previous experience and therefore have great learning value.

In addition to the exercises that appear in this book, then, student assignments might consist of writing occasional programs, as well as delivering reports in class on assigned readings. The latter might be found among the references cited in the bibliographies in each chapter.

I am indebted first of all to the students on whom I worked out these ideas, and second to a number of colleagues for their helpful advice and friendly criticism. Among the latter I will mention Richard Brualdi, Daniel Kleitman, Albert Nijenhuis, Robert Tarjan and Alan Tucker. For the no-doubt-numerous shortcomings that remain, I accept full responsibility.

This book was typeset in TEX. To the extent that it’s a delight to look at, thank TEX. For the deficiencies in its appearance, thank my limitations as a typesetter. It was, however, a pleasure for me to have had the chance to typeset my own book. My thanks to the Computer Science department of the University of Pennsylvania, and particularly to Aravind Joshi, for generously allowing me the use of TEX facilities.

Click to Download