Preface: A Computer Science Tapestry

( the book home page)

The Tapestry Viewed from Afar

This book is designed for a first course (CS 1) in computer science that uses C++ as the language by which programming is studied. My goal in writing the book has not been to adopt a ``hot'' new language (If that was the goal, I would have to discard three years of work and switch from C++ to Java.) and use it in ways otherwise similar to so many introductory programming texts. I have tried to exploit the best features of C++ in the context of studying programming, program design and construction, and computer science. My intent is that mastering the material presented here will provide:

  1. a strong grounding in the design, construction, and analysis of programs

  2. a means for honing ``problem solving'' skills associated with the study of computer programming

  3. an introduction to computer science that gives the student more of an idea of what the discipline is about than does a ``traditional'' introductory programming book

In particular, this is a book designed to teach programming using C++, not a book designed to teach C++. Nevertheless, I expect students who use this book will be reasonably adept C++ programmers. Object-oriented programming is not a programmer's panacea although it can make some jobs much easier. To mix metaphors, no matter how you slice it learning to program is a hard task --- it takes time to master just as bread takes time to rise.

The material here is grounded in the concept that the study of computer science should be part of the study of programming. It is also based on the idea that program design is a very difficult task for novices to master, but that program enhancement or modification (a much more manageable skill) permits beginning programmers to develop programming skills in the context of meaningful programs. Most importantly, this book takes the view that the study of computer science should involve hands-on activity and should be fun. The study of programming must cover those areas that are acknowledged as fundamental to computer science, but should do so in such a way that the foundation that is constructed during this study can be used to study current trends that change and should do so in a way that enables students to want to learn more. Support for this position can be found in several places, I offer two quotes that express my sentiments quite well.

Having surveyed the relationships of computer science with other disciplines, it remains to answer the basic questions: What is the central core of the subject? What is it that distinguishes it from the separate subjects with which it is related? What is the linking thread which gathers these disparate branches into a single discipline? My answer to these questions is simple --- it is the art of programming a computer. It is the art of designing efficient and elegant methods of getting a computer to solve problems, theoretical or practical, small or large, simple or complex. It is the art of translating this design into an effective and accurate computer program. This is the art that must be mastered by a practising computer scientist; the skill that is sought by numerous advertisements in the general and technical press; the ability that must be fostered and developed by computer science courses in universities.
C.A.R. Hoare
Essays in Computing Science

A supporting view is expressed in the following quote:

Programming is unquestionably the central topic of computing.

In addition to being important, programming is an enormously exciting intellectual activity. In its purest form, it is the systematic mastery of complexity. For some problems, the complexity is akin to that associated with designing a fine mechanical watch, i.e., discovering the best way to assemble a relatively small number of pieces into a harmonious and efficient mechanism. For other problems, the complexity is more akin to that associated with putting a man on the moon, i.e, managing a massive amount of detail.

In addition to being important and intellectually challenging, programming is a great deal of fun. Programmers get to build things and see them work.. What could be more satisfying?

John V. Guttag
Why Programming Is Too Hard and What to Do About It
in Research Directions in Computer Science: An MIT Perspective


Programming and Computer Science

This is more than a book about programming. Although its principal focus is on programming using C++, this is also a book about computer science. However, this is neither a book that adopts what some have called a ``breadth-first'' approach to computer science nor is it a book primarily designed to teach object-oriented programming in the first course (although glimpses of both approaches will be evident).

I believe that a one-semester course that attempts to cover programming to the same extent as is done in a traditional Pascal, C, or C++ CS1 course and, at the same time, attempts to cover at even a superficial level the core areas of computer science is most likely doomed to failure. There is simply too much material to be covered.

At the same time, there has been an unfortunate though well-motivated tendency in many colleges and universities to move from Pascal-based courses to C-based courses. There are many good reasons for this change, but there is a fundamental pedagogical flaw in using C in a first course that more than counterbalances all the good reasons that so many have propounded: C is not designed to insulate the novice programmer from the machine --- as such it is a disaster when used in a first course.(It is possible to use C in a first course in a reasonable way, but the only example of doing this that I have seen is in a book by Eric Roberts, The Art and Science of C. Using C++ is much simpler than using C.)

Of course these statements not only border on hyperbole, they embrace it with open arms. Nevertheless, watching students struggle with the many idiosyncrasies of C while trying to develop and master general principles of programming has not been a pretty sight --- we did just this for several years before switching to C++ in our first course. At one level, the approach used in this book is the approach we adopted initially in our courses --- C++ is simply a much better C. At a superficial level its I/O support and its support of more than one mode of parameter passing --- by value and by reference --- free students from worrying about pointers in the first week of the course. At a deeper level C++ and its support of objects and libraries allows students to make use of supplied code in a standard and useful way.

Introductory courses are evolving to take advantage of new and current trends in software-engineering and programming language design. One of these trends is object-oriented design and object-oriented programming or OOP. Some schools will adopt the approach that learning object-oriented principles should be the focus of a first programming course. Although this approach certainly has some merit, students in the first course traditionally have a very difficult time with the design of programs. I believe that attempting to cover program design in addition to object design will not be as conducive to a successful programming experience as will using object-oriented concepts in the context of learning to program by reading programs before writing them. This may seem a subtle distinction, but if the focus of the course is on learning about the design and use of both objects and programs, there may be a tendency to delve too quickly and too deeply into the details of C++.

The approach taken in this book is that C++ and OOP permit students with little or no programming background to make great strides towards developing foundational knowledge and expertise in programming. In subsequent courses students will hone the skills that are first learned in the study of the material in this book and will expand the coverage of computer science begun here. Computer science is not just programming, and students in a first course in computer science must be shown something of what the discipline is about. At the same time, programming provides a means of relating the subdisciplines that comprise computer science. Many of the examples and programs in this book rely on the use of classes, code, and libraries that are documented and supplied. It is possible that these examples could be studied using C rather than C++, but this would be very cumbersome and difficult to do in anything but an ad-hoc manner specific to this book at best.

A major tenet of the approach used here is that students should read, modify, and extend programs before designing and writing from scratch. This is enabled to a large extent by using the object-oriented features of C++ whenever appropriate. However, neither I nor the book are compelled to delve into design methodologies and features of OOP; C++ is a tool to be used rather than studied. One of the most important ideas underlying the use of classes and objects in C++ and one of the most important concepts in computer science is the idea of abstraction.

Its [computer science] study involves development of the ability to abstract the essential features of a problem and its solution, to reason effectively in the abstract plane, without confusion by a mass of highly relevant detail. The abstraction must then be related to the detailed characteristics of computers as the design of the solution progresses; and it must culminate in a program in which all the detail has been made explicit; and at this stage, the utmost care must be exercised to ensure a very high degree of accuracy. At all stages the programmer must be articulate about his activity. The need for abstract thought together with meticulous accuracy, the need for imaginative speculation in the search for a solution, together with a sound knowledge of the practical limitations of the tools available for its implementation, the combination of formal rigour with a clear style for its explanation to others --- these are the combinations of attributes which should be inculcated and developed in a student by any university academic discipline; and which must be developed in high degree in students of computer science.
C.A.R. Hoare
Essays in Computing Science

Students and teachers of computer science are not obliged to understand the IEEE standards for floating point numbers in order to write code that uses such numbers. Although at one time a deep understanding of machine architecture was necessary in order to write programs, this is no longer the case. Just as Hoare exhorts the programmer to be articulate about his or her activity, this book is designed to bring the novice programmer and student of computer science to a point where such behavior is possible. The use of C++ provides a mechanism for doing this so that details can be revealed if and when it is appropriate to do so and hidden otherwise.


Programming in C++

Although this book uses C++ as a tool to be used rather than studied, students coming out of a first course must be well-prepared for subsequent courses in computer science and other disciplines. As such, the essential features of C++ must be used, studied, and mastered. The syntactic and semantic features of C++ sufficient for an introductory course will be thoroughly covered. It has been our experience in using this material that it is easier to move from C++ to C than vice-versa. With this in mind, no coverage is given to C topics such as the kind of I/O done using printf and scanf.

Many thought and programming exercises are integrated in the text, particularly in the pause and reflect sections. These exercises are designed to make students think about what they're doing, and to cover some of the messier language details in thought-provoking and interesting ways. Online materials accessible via the world-wide web will provide supporting programming lab assignments.


A Closer View of the CS Tapestry

This book is different than most other introductory programming contexts in that:

How to use the book

We do not cover every section of the book in our courses and instructors who class-tested the book indicated that they skip some sections as well. Different institutions will cover some topics in more detail than others. In particular, Chapter 10 is not a prerequisite for the chapters that follow it except that it introduces recursion which is used in Section 11.4 discussing quick sort. Recursion is also used in the coverage of linked lists and trees in Chapter 12 although linked lists can be studied without recursion. The excursion sections are not pre-requisites for any of the material appearing later in the book, so these sections are optional as well. Chapter 8 and Chapter 9 can be covered in the opposite order for teachers who want to have covered streams and characters before arrays and vectors. In our course we don't cover the material explaining the built-in array type except in a cursory manner. The Vector and Matrix classes are much easier for students to use since they hide all relationship with pointers.

Thanks

Many people have contributed to this book and the material in it. I hope that lots more will. I must single out several people who have offered criticisms and suggestions that have been extremely useful during the development of the material here: Rich Pattis (University of Washington, now at Carnegie Mellon) and Dave Reed (Dickinson College). At Duke, Susan Rodger taught using a draft, waited patiently while chapters were revised, and offered a nearly uncountable number of exercises, improvements, and programs. Her efforts have been very important in the development of this material. Greg Badros(then at Duke) reviewed the entire manuscript and offered absolutely wonderful suggestions --- he astonished me with his perspicacity. In the fall of 1995 David Levine used the book at Gettysburg College and made many constructive suggestions based on this use. Through the auspices of McGraw-Hill, Marjorie Anderson offered wonderful suggestions for improving the quality of the material here. Although I haven't vanquished the passive-voice, any progress is due to her diligence and all stylistic blunders are my own. The entire project was overseen and shepherded by Eric Munson and Holly Stark. Their tireless efforts are much appreciated.

In addition, the following people have reviewed the material and offered many useful suggestions (if I've left someone out, I apologize).

Gail Chapman
Educational Testing Service
Mike Clancy
U.C. Berkeley
David Kay
U.C. Irvine
Clayton Lewis
University of Colorado
Bob Noonan
College of William and Mary
Richard Prosl
College of William and Mary
Stephen Schach
Vanderbilt University
Andrew Holey
St. John's University
David Teague
Western Carolina University
Robert Plantz
Sonoma State University
Arthur Farley
University of Oregon
David Mutchler
Rose-Hulman
Deganit Armon
U.C. Riverside
Stuart Reges
University of Arizona
Jerry Mead
Bucknell University

Students in the Fall 1994 CPS 06 and 08 courses at Duke suffered through a draft of the material here. Several of them offered useful suggestions that appear in this draft. In particular Travis Pouarz and Derek Mims combed the material for errors and offered useful improvements. Students in the Spring, 1995 CPS 08 course had to make do with a version of the book with no index. Nevertheless, several students made useful suggestions. In particular, Jay Kamm found many errors, even looking at code that wasn't in the book and offering suggestions.

Students in the Fall 1995 CPS 06 course had a book with an index, but the pages fell out. These students persevered, and new books arrived. In the interim several students combed the book for typos. I cannot possibly thank them all enough, but one stands out for her diligence: Christine Hong found countless errors and made many suggestions for improvement. Mackenzie Steele offered several quotations in addition to finding errors.


Development

The ideas and exercises in this book have been tested in the first course for majors at Duke during the 1993-1994 and 1994-1995 academic years. A draft form of the book has been used in all courses since the fall of 1994.

Several schools used a beta-edition of the book, and the feedback from these schools has been incorporated into the final version. These schools include the University of Iowa, Rose-Hulman Institute of Technology, Gettysburg College, St. John's College (Minnesota), Mills College, and U. California, Berkeley.

Versions of all the programs used in the book are available for Mac, DOS, and Unix machines. The software is currently available via anonymous ftp in pub/ola/book/code. It is also accessible using your favorite browser (or you wouldn't be reading this)

Although beta-editions of the book have been through extensive classroom testing, there are undoubtedly errors that persist. Occasional slips of the tongue (or keyboard) have almost certainly crept into the manuscript.

Nevertheless, all code has been compiled and executed and is reproduced in this work directly from the source, it is not retyped. The material here is intended to provide complete coverage for many different kinds of introductory computer science courses based on C++.

I am anxious to correct all the errors and fuzzy, incoherent, or otherwise incomprehensible passages for the first (and hopefully not last) edition of the book. I am not anxious to hear about misplaced commas and semi-colons. I haven't mastered comma placement and will leave this to experts. I would be ecstatic to hear about methods that might improve certain sections, or comments about sections that caused problems even without suggestions for improvement.

Please send all comments by electronic mail , I will try to acknowledge all mail received. Materials for the book are also accessible via the world-wide web. A listserv is available for discussing any aspects of the book or course. To subscribe, send email with the message subscribe tapestry as the message body to majordomo@acpub.duke.edu, to unsubscribe send the message unsubscribe tapestry to the same address. To send mail to the listserv use the address tapestry@acpub.duke.edu.


Details

This beta-version of the book was prepared using LaTeX on Sun Sparcstation computers and a Micron Pentium-based machine running Linux Pictures were ``drawn'' using xfig and exported as Postscript files. Photos were found on the world-wide web using Netscape and converted to Postscript using XV.

To paraphrase Newton, the work in this book is not mine alone; I have stood on the shoulders of giants. Of course Newton paraphrased Robert Burton who said ``a dwarf standing on the shoulders of a giant may see farther than a giant himself.'' The styles used in several books serve as models for different portions of this text. In particular Eric Roberts' The Art and Science of C provided style guidelines for formatting; the book A Logical Approach to Discrete Math (by David Gries and Fred B. Schneider) motivated the biographies; books by Bjarne Stroustrup: The C++ Programming Language (2nd edition) and The Design and Evolution of C++ and Scott Meyers: Effective C++ were indispensable in delving into C++. Rick Mercer's C++ book, Computing Fundamentals with C++ provided a good example of how to do things well and simply. Stuart Reges' book Building Pascal Programs (now out of print) had a strong influence.

I've borrowed ideas from almost all the textbooks I've read in eighteen years of teaching, so I acknowledge them en masse.

Thanks to Duke University and the Computer Science Department for providing an atmosphere in which teaching is rewarded and this book is possible.

Finally, thanks to Laura for always understanding.