Foundations of Computer Science

This book developed from notes for a two-quarter course at Stanford – called CS109: Introduction to Computer Science – that serves a number of goals. The first goal is to give beginning computer science majors a solid foundation for further study. However, computing is becoming increasingly important in a much wider range of scientific and engineering disciplines. Therefore, a second goal is to give those students who will not take advanced courses in computer science the conceptual tools that the field provides. Finally, a more pervasive goal is to expose all students not only to programming concepts but also to the intellectually rich foundations of the field.

The first version of this book was based on programming in Pascal and appeared in 1992. Their choice of Pascal as the language for example programs was motivated by that language’s use in the Computer Science Advanced Placement Test as well as in a plurality of college introductions to programming. They were pleased to see that since 1992 there has been a significant trend toward C as the introductory programming language, and they accordingly developed a new version of the book using C for programming examples. Their emphasis on abstraction and encapsulation should provide a good foundation for subsequent courses covering object-oriented technology using C++.

Foundations of Computer Science covers subjects that are often found split between a discrete mathematics course and a sophomore-level sequence in computer science in data structures. It has been their intention to select the mathematical foundations with an eye toward what the computer user really needs, rather than what a mathematician might choose. They have tried to integrate effectively the mathematical foundations with the computing. They thus hope to provide a better feel for the soul of computer science than might be found in a programming course, a discrete mathematics course, or a course in a computer science subspecialty. They believe that, as time goes on, all scientists and engineers will take a foundational course similar to the one offered at Stanford upon which this book is based. Such a course in computer science should become as standard as similar courses in calculus and physics.