Eric S. Roberts is an associate professor of computer science at Stanford University and the department's associate
chair for educational affairs. After receiving his Ph.D. in applied mathematics from Harvard University in 1980,
Roberts founded and chaired the computer science department at Wellesley College. He then worked for five years
as a researcher for Digital Equipment Corporation's System Research Center in Palo Alto, California. He is also
the author of Thinking Recursively along with numerous technical publications. A highly rated teacher, Roberts
received the Bing Award for excellence in undergraduate teaching in 1993.
Preface
Welcome! By picking up this book, you have taken a step into the world of computer science - a field of study
that has grown from almost nothing half a century ago to become one of the most vibrant and active disciplines
of our time.
Over that time, the computer has opened up extraordinary possibilities in almost every area of human endeavor.
Business leaders today are able to manage global enterprises on an unprecedented scale because computers enable
them to transfer information anywhere in a fraction of a second. Scientists can now solve problems that were beyond
their reach until the computer made the necessary calculations possible. Filmmakers use computers to generate dramatic
visual effects that are impossible to achieve without them. Doctors can determine much more accurately what is
going on inside a patient because computers have enabled a massive transformation in the practice of medicine.
Computers are a profoundly empowering technology. The advances we have seen up to now are small compared to
what we will see in the next century. Computers will play a major role in shaping that century, just as they have
the last 50 years. Those of you who are students today will soon inherit the responsibility of guiding that progress.
As you do so, knowing how to use computers can only help.
Like most skills that are worth knowing, learning how computers work and how to control their enormous power
takes time. You will not understand it all at once. But you must start somewhere. Twenty-five centuries ago, the
Chinese philosopher Lao-tzu observed that the longest journey begins with a single step. This book can be your
beginning.
For many of you, however, the first step can be the hardest to take. Many students find computers overwhelming
and imagine that computer science is beyond their reach. Learning the basics of programming, however, does not
require advanced mathematics or a detailed understanding of electronics. What matters in programming is whether
you can progress from the statement of a problem to its solution. To do so, you must be able to think logically.
You must have the necessary discipline to express your logic in a form that the computer can understand. Perhaps
most importantly, you must be able to see the task through to its completion without getting discouraged by difficulties
and setbacks. If you stick with the process, you will discover that reaching the solution is so exhilarating that
it more than makes up for any frustrations you encounter along the way.
This book is designed to teach you the fundamentals of programming and the basics of C, which is the dominant
programming language in the computing industry today. It treats the whys of programming as well as the hows, to
give you a feel for the programming process as a whole. It also includes several features that will help you focus
on the essential points and avoid errors that slow you down. The next few pages summarize these features and explain
how to use this book effectively as you begin your journey into the exciting world of computer science.
In 1991-92, Stanford decided to restructure its introductory computer science curriculum to use ANSI C instead
of Pascal. We chose to adopt ANSI C in our introductory courses for the following reasons:
Students demanded a more practical language. Future employers want students to have more direct experience with
the tools industry uses, which today are principally C and C++. With few employment opportunities listed for Pascal
programmers in the newspaper employment section, our students began to question the relevance of their education.
Our Pascal-based curriculum taught students to program in a language that they would never again use. We discovered
that many of those students, when they abandoned Pascal for more modern languages, often forgot everything they
had learned about programming style and the discipline of software engineering. Having now taught these skills
in the context of a language that the students continue to use, we have found that they end up writing much better
programs.
Many of our advanced computer science courses, particularly in the systems area, require students to program
in C. Working with C from the beginning gives students much more experience by the time they reach the advanced
courses.
Learning C early paves the way to learning C++ and the object-oriented paradigm. Because our students have a
strong background in C programming after their first year of study, we have been able to offer our course on object-oriented
system design much earlier in the curriculum.
C makes it possible to cover several important topics, such as modular development and abstract data types,
that are hard to teach in a Pascal environment.
In the last five years, C has made significant headway toward replacing Fortran as the lingua franca of programming
for the engineering sciences.
Given our experience over the last three years, I am convinced that the choice was a good one and that our program
is stronger because of the change. At the same time, it is important to recognize that teaching C in the first
programming course is not always easy. C was designed for programmers, not introductory students. Many of its features
make sense only when understood in terms of a larger conceptual framework that new students do not recognize. In
many respects, C is a complex language. To teach it at the introductory level, we must find a way to control its
complexity.
One of the central goals of this text is to enable teachers to manage C's inherent complexity. Managing complexity,
however, is precisely what we do as programmers. When we are faced with a problem that is too complex for immediate
solution, we divide it into smaller pieces and consider each one independently. Moreover, when the complexity of
one of those pieces crosses a certain threshold, it makes sense to isolate that complexity by defining a separate
abstraction that has a simple interface. The interface protects clients from the underlying details of the abstraction,
thereby simplifying the conceptual structure.
The same approach works for teaching programming. To make the material easier for students to learn, this text
adopts a library-based approach that emphasizes the principle of abstraction. The essential character of that approach
is reflected in the following two features that set this book apart from other introductory texts:
Libraries and modular development - essential concepts in modern programming - are covered in considerable
detail early in the presentation. Part II focuses entirely on the topics of libraries, interfaces, abstractions,
and modular development. Students learn how to use these techniques effectively before they learn about arrays.
The text demonstrates the power of libraries by using them. It is one thing to tell students that libraries
make it possible to hide complexity. It is quite another to demonstrate that concept. This text introduces several
new libraries that hide details from the students until they are ready to assimilate them. The libraries give students
the power to write useful programs that they could not develop on their own. Later chapters reveal the implementation
of those libraries, thereby allowing students to appreciate the power of abstraction.
In 1992, I attempted to teach the introductory course using only the ANSI libraries. The results were not encouraging.
Each new topic required that the student understand so much about the rest of C that there was no effective way
to present the material. For example, students had to understand the mechanics of arrays, pointers, and allocation
before they could use string data in any interesting way, even though string manipulation is simpler conceptually.
My best students managed to understand what was going on by the end of the quarter. Most, however, did not. Since
we introduced the library-based approach in early 1993, students have assimilated the material more easily and
learned much more about computer science.
The library interfaces and associated implementations used in this text are reprinted in Appendix B, which also
gives instructions for obtaining the source code electronically through anonymous FTP (File Transfer Protocol).
This book presents topics in the same order as Stanford's introductory course, except for the material in Chapter
17, which we cover in the second course. Depending on your audience and the goals of your course, you may want
to vary the order of presentation. The following notes provide an overview of the chapters and indicate some of
the more important dependencies.
Chapter 1 traces the history of computing and describes the programming process. The chapter requires no programming
per se but provides the contextual background for the rest of the text.
I have designed Chapters 2 and 3 for students with little or no background in programming. These chapters are
conceptual in their approach and focus on problem solving rather than on the details of the C language. When new
students are faced with detailed rules of syntax and structure, they concentrate on learning the rules instead
of the underlying concepts, which are vastly more important at this stage. If your students already know some programming,
you could move much more quickly through this material.
Chapters 2 and 3 are informal in their approach and concentrate on developing the student's problem-solving
skills. Along the way they introduce several basic statement forms and control structures, but only as idioms to
accomplish a specific task. Chapter 4 adds formal structure to this topic by describing each statement form in
turn, detailing its syntax and semantics. The chapter also includes an extensive discussion of Boolean data.
Chapter 5 introduces functions and procedures. It begins with simple examples of functions and then continues
with increasingly sophisticated examples. The mechanics of parameter passing are discussed in a separate section
that includes many diagrams to help students follow the flow of data from one function to another. The chapter
ends with a significant programming example that illustrates the concept of stepwise refinement.
The algorithmic concepts presented in Chapter 6 are fundamental to computer science but may not be required
for all students. If your audience consists of engineers or potential computer science majors, the material will
prove extremely valuable. For less technical audiences, however, you can eliminate much of this material without
disturbing the flow of the presentation.
I have found that integrating graphics in the introductory course is a great way to increase student interest
in the material. Chapter 7 exists for that reason. At this state, students have learned the mechanics of functions
but have no burning need to write them. Letting students draw complex pictures on the screen gives them that incentive.
The graphics library is implemented for several of the major programming environments and can therefore be used
in most institutions.
Chapter 8 has two themes, which are in some sense separable. The first part of the chapter discusses design
criteria for interfaces and is essential for anyone who needs to understand how modern programming works. The second
part of the chapter applies those principles to build a random number library. The random.h interface itself is
less important than the general principles, although use of the random number library is required for a few of
the exercises later in the text.
Chapter 9 introduces strings as an abstract type and represents to a certain extent, the cornerstone of the
library-based approach. By using a dynamic string library, students can easily write programs that perform sophisticated
string manipulation, even though they do not yet understand the underlying representation, which is covered in
Chapter 14. Introducing strings at this point in the presentation enables students to write much more exciting
programs than they could otherwise.
On a first reading, it is easy to miss the purpose of Chapter 10, which appears to be an extension of the discussion
of strings begun in Chapter 9. The fundamental value of Chapter 10 does not lie in the Pig Latin program, which
is more fun than it is practical. The entire reason for the example is that it provides them motivation to build
the scanner interface used to separate words on the input line. The scanner module proves its usefulness over and
over again, not only in the first course but in subsequent courses as well. It is the most practical tool students
create in the course and therefore serves as a compelling example of the value of modularity.
Chapters 11 through 16 introduce the fundamental compound structures - arrays, pointers, files, and records
- in an order that has worked well in practice. Because the base language is C, it is important to present pointers
as soon as possible after introducing arrays so that you can emphasize the connections between them. Moreover,
having established these concepts, it is then possible in Chapter 14 to consider string data more closely, thereby
revealing the underlying representation that was concealed by the abstract definition. Chapter 16 integrates the
fundamental data structures with the construction of a data-driven teaching machine, which is the most sophisticated
example of programming presented in the text.
Chapter 17 includes three important topics that often appear in the first programming course: recursion, abstract
data types, and analysis of algorithms. At Stanford, which is on the quarter system, we teach all these topics
in the second course. I strongly recommend that you do so early enough to allow students time to assimilate the
material. One possibility is to discuss recursive functions immediately after Chapter 5 and recursive algorithms
after Chapter 6. Another approach is to cover recursion and analysis of algorithms together at the end of Chapter
12.
The Instructor's Manual contains supplemental materials including a course syllabus, suggestions for lecture
design, sample assignments and examinations, and solutions to all programming exercises. In addition to the printed
manual, instructors who adopt this text can retrieve electronic copies of solution sets and related materials.
For details on obtaining solutions, please contact your local Addison-Wesley representative. All other supplemental
material is available on-line. For explicit instructions see Appendix B.
The text has come a long way from it initial stages as class notes, in large measure because of suggestions
from people who have worked with the text in one capacity or another. I am particularly grateful to the Stanford
lecturers - Jon Becker, Katie Capps, Stephen Clausing, Todd Feldman, Allison Hansen, Margaret Johnson, Jim Kent,
Andrew Kosoresow, Mehran Sahami, and Julie Zelenski - who have taught this material in 14 different sections of
the introductory course over the past three years. I am also indebted to all the section leaders and teaching assistants
as well as the coordinators of the student-teaching program - Felix Baker, John Lilly, Sandy Nguyen, Bryan Rollins,
and Scott Wiltamuth - who provided much needed logistical support.
Many of the best ideas for the text came from a seminar on teaching introductory computer science that I conducted
beginning in 1992-93. It provided a forum for thrashing out the hard issues and made a significant difference in
the text. I want to thank everyone who participated: Perry Arnold, Jon Becker, Tom Bogart, Karl Brown, Bryan Busse,
Katie Capps, Peter Chang, Scott Cohen, Stacey Doerr, Jeff Forbes, Stephen Freund, Jon Goldberg, Tague Griffith,
Matt Harad, Lindsay Lack, Christine Lee, Tricia Lee, John Lilly, Albert Lin, Mara Mather, Hugh McGuire, Jeffrey
Oldham, David O'Keefe, Bryan Rollins, Samir Saxena, Nikhyl Singhal, Eric Tucker, Garner Weng, Howard Wong-Toi,
and John Yong.
I also want to thank all the students who have used and critiqued the draft version of the text: Adjo Amekudzi,
Eric Anderson, Andrew Arnold, Kevin Berk, Kevin Carbajal, Ajit Chaudhari, Alida Cheung, Hye-won Choi, Elisabeth
Christensen, Ralph Davis, Joel Firehammer, Peter Frelinghuysen, Trevor Gattis, Teddy Harris, Heather Heal, Enoch
Huang, Ann Lee, Ted Lee, Daphne Lichtensztajn, Lisa Maddock, Allan Marcus, Brad McGoran, Forrest Melton, Adrienne
Osborn, Masatoshi Saito, Anne Stern, Ricardo Urena, and Nichole Wilson.
In 1993-94, several faculty members at other universities tested this material in draft from and made several
valuable suggestions. I especially want to thank Margo Seltzer at Harvard University, Rob Langsner at the University
of Nevada (Reno), Richard Chang at the University of Maryland (Baltimore County), Jane Turk at La Salle University,
and Kim Kihlstrom at Westmont College for helping to refine the text from its early stages.
I am also indebted to my reviewers:
Stephen Allan
Utah State University
James Schmolze
Tufts University
Don Goelman
Villanova University
Michael Skolnick
Rensselaer Polytechnic
Stan Kolasa
Rutgers University
Jeffrey A. Slomka
Southwest Texas State University
Harry R. Lewis
Harvard University
Kevin Smith
Emory University
Bill Muellner
Elmhurst College
Phil Tromovitch
SUNY - Stony Brook
Rayno Niemi
Rochester Institute of Technology
John A. Trono
St. Michaels' College
Robert G. Plantz
Sonoma State University
Robert Walker
Rensselaer Polytechnic
David Rosenthal
Seton Hall
Richard Weinand
Wayne State University
In addition, I have received useful advice along the way from several friends and colleagues, including Josh
Barnes, Pavel Curtis, Kathleen Kells, James Finn, and Steve Lewin-Berlin.
The final version of this text owes much to my editors at Addison-Wesley, who have been helpful throughout the
process,. In particular, I thank Lynne Doran Cote, Sue Gleason, Peter Gordon, Laura Michaels, Jim Rigney, Karen
Stone, and Amy Willcutt for all their work. And I am extremely fortunate to have Lauren Rusk as both my developmental
editor and my partner; without her, nothing would ever come out as well as it should.
Summary
The Art and Science of C is specifically designed to teach introductory programming using ANSI C. Roberts uses
standard software engineering strategies---procedural abstraction, modular decomposition, and information hiding---from
start to finish. What is unique about this book is Roberts' use of libraries. This method has two advantages. First,
Roberts uses the libraries to emphasize the techniques of procedural abstraction, modular development, and information
hiding, which are essential tools for the professional programmer. By emphasizing these concepts from the very
beginning to the text, students develop the skills necessary to manage complexity when it arises.
Second, the text makes the material easier for students to learn. Early in the book, Roberts introduces several
new libraries that hide details from the students until they are ready to use them. The libraries give the students
the power to write useful programs that they could not yet develop on their own. Later chapters reveal the implementation
of those libraries, thereby allowing students to appreciate the power of abstraction. With this text, Roberts provides
you with everything you'll need to manage C's inherent complexity.
* Promotes solid programming skills by including discussion of the hows as well as the whys of programming.
* Includes helpful learning tools:
* Review questions covering key elements end each chapter.
* Exercises, over 175 in the text.
* Sample programs illustrate both the mechanics of programming and the use of good programming style.
* Buggy programs help student identity and correct bugs of their own.
Table of Contents
Chapter 1: Introduction
A Brief History of Computing
What is Computer Science?
A Brief Tour of Computer Hardware
Algorithms
Programming Languages and Compilation
Programming Errors and Debugging
Software Maintenance
The Importance of Software Engineering
Some Thoughts on the C Programming Language
Summary
Review Questions
Part 1 --- The Basics Of C Programming
Chapter 2. Learning by Example
The "Hello World" Program
A Program to Add Two Numbers
Perspectives on the Programming Process
Data Types
Expressions
Summary
Review Questions
Programming Exercises
Chapter 3. Problem Solving
Programming Idioms and Paradigms
Solving Problems on a Larger Scale
Control Statements
An Exercise in Debugging
Formatted Output
Crafting a Program
Summary
Review Questions
Programming Exercises
Chapter 4. Statement Forms
Simple Statements
Control Statements
Boolean Data
The if Statement
The switch Statement
The while Statement
The for Statement
Summary
Review Questions
Programming Exercises
Chapter 5. Functions
Using Library Functions
Function Declarations
Writing Your Own Functions
Mechanics of the Function-Calling Process
Procedures
Stepwise Refinement
Summary
Review Questions
Programming Exercises
Chapter 6. Algorithms
Testing for Primality
Computing the Greatest Common Divisor
Numerical Algorithms
Series Expansion
Specifying the Size of Numeric Types
Summary
Review Questions
Programming Exercises
Part II --- Libraries And Modular Development
Chapter 7. Libraries and Interfaces: A Simple Graphics Library
The Concept of an Interface
An Introduction to the Graphics Library
Building Your Own Tools
Solving a Larger Problem
Summary
Review Questions
Programming Exercises
Chapter 8. Designing Interfaces: A Random Number Library
Interface Design
Generating Random Numbers by Computer
Saving Tools in Libraries
Evaluating the Design of random.h Interface
Using the Random-Number Package
Summary
Review Questions
Programming Exercises
Chapter 9. Strings and Characters
The Principle of Enumeration
Characters
Strings as Abstract Data
The strlib.h Interface
Summary
Review Questions
Programming Exercises
Chapter 10. Modular Development
Pig Latin---A Case Study in Modular Development
Maintaining Internal State within a Module
Implementing a Scanner Abstraction
Summary
Review Questions
Programming Exercises
Part III --- Compound Data Types
Chapter 11. Arrays
Introduction to Arrays
Internal Representation of Data
Passing Arrays as Parameters
Using Arrays for Tabulation
Static Initialization of Arrays
Multidimensional Arrays
Summary
Review Questions
Programming Exercises
Using Addresses as Data Values
Pointer Manipulation in C
Passing Parameters by Reference
Pointers and Arrays
Dynamic Allocation
Summary
Review Questions
Programming Exercises
Chapter 14. Strings Revisited
Conceptual Representations of the Type string
The ANSI String Library
Implementing the strlib.h Library
Summary
Review Questions
Programming Exercises
Chapter 15. Files
Text Files
Using Files in C
Character I/O
Line-oriented I/O
Formatted I/O
Summary
Review Questions
Programming Exercises
Chapter 16. Records
The Concept of the Data Record
Using Records in C
Combining Records and Arrays
Pointers to Records
Building a Database of Records
Designing a Record-Based Application
Summary
Review Questions
Programming Exercises
Chapter 17. Looking Ahead
Recursion
Abstract Data Types
Analysis of Algorithms
Summary
Review Questions
Programming Exercises
Appendix A. Summary of C Syntax and Structure
Appendix B. Library Sources
