Computer Science: An Interdisciplinary Approach is an introductory textbook suitable for use by any college student, of similar scope to well-known introductory textbooks for economics, physics, biology, chemistry, and many other fields. As with such books, it

• Covers the intellectual underpinnings of the field.
• Can serve as the basis for teaching a course for first-year college students or a college prep course in high schools and community colleges.
• Can serve as a self-study resource to introduce individuals to computer science.
• Prepares readers for further study in the field.
• Emphasizes applications in other disciplines.

Importantly, while this book does provide a thorough introduction to programming, it advances the notion that “computer science” is much more than “learning to program.” The book covers algorithms and data structures, theory of computing, and computer architecture, with emphasis on core ideas of Turing, von Neumann, Shannon, and others that ignited the digital age.

Chapter 1. Elements of Programming

1.1 Your First Program
1.2 Built-in Types of Data
1.3 Conditionals and Loops
1.4 Arrays
1.5 Input and Output
1.6 Case Study: Random Web Surfer

Chapter 2. Functions and Modules

2.1 Defining Functions
2.2 Libraries and Clients
2.3 Recursion
2.4 Case Study: Percolation

Chapter 3. Object-Oriented Programming

3.1 Using Data Types
3.2 Creating Data Types
3.3 Designing Data Types
3.4 Case Study: N-Body Simulation

Chapter 4. Algorithms and Data Structures 

4.1 Performance
4.2 Sorting and Searching
4.3 Stacks and Queues
4.4 Symbol Tables
4.5 Case Study: Small-World Phenomenon

Chapter 5. Theory of Computing 

5.1 Formal Languages
5.2 Turing Machines
5.3 Universality
5.4 Computability
5.5 Intractability

Chapter 6. A Computing Machine 

6.1 Representing Information
6.2 TOY Machine
6.3 Machine-Language Programming
6.4 TOY Virtual Machine

Chapter 7. Building a Computing Device

7.1 Boolean Logic
7.2 Basic Circuit Model
7.3 Combinational Circuits
7.4 Sequential Circuits
7.5 Digital Devices

The basis for education in the last millennium was “reading, writing, and arithmetic”; now it is reading, writing, and computing. Learning to program is an essential part of the education of every student in the sciences and engineering. Beyond direct applications, it is the first step in understanding the nature of computer science’s undeniable impact on the modern world. This book aims to teach programming to those who need or want to learn it, in a scientific context.
     Our primary goal is to empower students by supplying the experience and basic tools necessary to use computation effectively. Our approach is to teach students that composing a program is a natural, satisfying, and creative experience. We progressively introduce essential concepts, embrace classic applications from applied mathematics and the sciences to illustrate the concepts, and provide opportunities for students to write programs to solve engaging problems. We seek also to demystify computation for students and to build awareness about the substantial intellectual underpinnings of the field of computer science.
     We use the Java programming language for all of the programs in this book. The first part of the book teaches basic skills for computational problem solving that are applicable in many modern computing environments, and it is a self-contained treatment intended for people with no previous experience in programming. It is about fundamental concepts in programming, not Java per se. The second part of the book demonstrates that there is much more to computer science than programming, but we do often use Java programs to help communicate the main ideas.
     This book is an interdisciplinary approach to the traditional CS1 curriculum, in that we highlight the role of computing in other disciplines, from materials science to genomics to astrophysics to network systems. This approach reinforces for students the essential idea that mathematics, science, engineering, and computing are intertwined in the modern world. While it is a CS1 textbook designed for any first-year college student, the book also can be used for self-study.

Coverage. The first part of the book is organized around four stages of learning to program: basic elements, functions, object-oriented programming, and algorithms. We provide the basic information that readers need to build confidence in composing programs at each level before moving to the next level. An essential feature of our approach is the use of example programs that solve intriguing problems, supported with exercises ranging from self-study drills to challenging problems that call for creative solutions.
     Elements of programming include variables, assignment statements, built-in types of data, flow of control, arrays, and input/output, including graphics and sound.
     Functions and modules are the students’ first exposure to modular programming. We build upon students’ familiarity with mathematical functions to introduce Java functions, and then consider the implications of programming with functions, including libraries of functions and recursion. We stress the fundamental idea of dividing a program into components that can be independently debugged, maintained, and reused.
     Object-oriented programming is our introduction to data abstraction. We emphasize the concept of a data type and its implementation using Java’s class mechanism. We teach students how to use, create, and design data types. Modularity, encapsulation, and other modern programming paradigms are the central concepts of this stage.
     The second part of the book introduces advanced topics in computer science: algorithms and data structures, theory of computing, and machine architecture.
     Algorithms and data structures combine these modern programming paradigms with classic methods of organizing and processing data that remain effective for modern applications. We provide an introduction to classical algorithms for sorting and searching as well as fundamental data structures and their application, emphasizing the use of the scientific method to understand performance characteristics of implementations.
     Theory of computing helps us address basic questions about computation, using simple abstract models of computers. Not only are the insights gained invaluable, but many of the ideas are also directly useful and relevant in practical computing applications.
     Machine architecture provides a path to understanding what computation actually looks like in the real world—a link between the abstract machines of the theory of computing and the real computers that we use. Moreover, the study of machine architecture provides a link to the past, as the microprocessors found in today’s computers and mobile devices are not so different from the first computers that were developed in the middle of the 20th century.
     Applications in science and engineering are a key feature of the text. We motivate each programming concept that we address by examining its impact on specific applications. We draw examples from applied mathematics, the physical and biological sciences, and computer science itself, and include simulation of physical systems, numerical methods, data visualization, sound synthesis, image processing, financial simulation, and information technology. Specific examples include a treatment in the first chapter of Markov chains for web page ranks and case studies that address the percolation problem, n-body simulation, and the small-world phenomenon. These applications are an integral part of the text. They engage students in the material, illustrate the importance of the programming concepts, and provide persuasive evidence of the critical role played by computation in modern science and engineering.
     Historical context is emphasized in the later chapters. The fascinating story of the development and application of fundamental ideas about computation by Alan Turing, John von Neumann, and many others is an important subtext.
     Our primary goal is to teach the specific mechanisms and skills that are needed to develop effective solutions to any programming problem. We work with complete Java programs and encourage readers to use them. We focus on programming by individuals, not programming in the large.

Use in the Curriculum. This book is intended for a first-year college course aimed at teaching computer science to novices in the context of scientific applications. When such a course is taught from this book, college students will learn to program in a familiar context. Students completing a course based on this book will be well prepared to apply their skills in later courses in their chosen major and to recognize when further education in computer science might be beneficial. Prospective computer science majors, in particular, can benefit from learning to program in the context of scientific applications. A computer scientist needs the same basic background in the scientific method and the same exposure to the role of computation in science as does a biologist, an engineer, or a physicist.
     Indeed, our interdisciplinary approach enables colleges and universities to teach prospective computer science majors and prospective majors in other fields in the same course. We cover the material prescribed by CS1, but our focus on applications brings life to the concepts and motivates students to learn them. Our interdisciplinary approach exposes students to problems in many different disciplines, helping them to choose a major more wisely.
     Whatever the specific mechanism, the use of this book is best positioned early in the curriculum. First, this positioning allows us to leverage familiar material in high school mathematics and science. Second, students who learn to program early in their college curriculum will then be able to use computers more effectively when moving on to courses in their specialty. Like reading and writing, programming is certain to be an essential skill for any scientist or engineer. Students who have grasped the concepts in this book will continually develop that skill throughout their lifetimes, reaping the benefits of exploiting computation to solve or to better understand the problems and projects that arise in their chosen field.

Prerequisites. This book is suitable for typical first-year college students. That is, we do not expect preparation beyond what is typically required for other entry-level science and mathematics courses.
     Mathematical maturity is important. While we do not dwell on mathematical material, we do refer to the mathematics curriculum that students have taken in high school, including algebra, geometry, and trigonometry. Most students in our target audience automatically meet these requirements. Indeed, we take advantage of their familiarity with the basic curriculum to introduce basic programming concepts.
     Scientific curiosity is also an essential ingredient. Science and engineering students bring with them a sense of fascination with the ability of scientific inquiry to help explain what goes on in nature. We leverage this predilection with examples of simple programs that speak volumes about the natural world. We do not assume any specific knowledge beyond that provided in typical high school courses in mathematics, physics, biology, or chemistry.
     Programming experience is not necessary, but also is not harmful. Teaching programming is one of our primary goals, so we assume no prior programming experience. But composing a program to solve a new problem is a challenging intellectual task, so students who have written numerous programs in high school can benefit from taking an introductory programming course based on this book. The book can support teaching students with varying backgrounds because the applications appeal to novices and experts alike.
     Experience using a computer is not necessary, but also is not a problem. College students use computers regularly—for example, to communicate with friends and relatives, listen to music, process photos, and as part of many other activities. The realization that they can harness the power of their own computer in interesting and important ways is an exciting and lasting lesson.
     In summary, virtually all college students are prepared to take a course based on this book as a part of their first-semester curriculum.

Goals. What can instructors of upper-level courses in science and engineering expect of students who have completed a course based on this book?
     We cover the CS1 curriculum, but anyone who has taught an introductory programming course knows that expectations of instructors in later courses are typically high: each instructor expects all students to be familiar with the computing environment and approach that he or she wants to use. A physics professor might expect some students to design a program over the weekend to run a simulation; an engineering professor might expect other students to use a particular package to numerically solve differential equations; or a computer science professor might expect knowledge of the details of a particular programming environment. Is it realistic for a single entry-level course to meet such diverse expectations? Should there be a different introductory course for each set of students?
     Colleges and universities have been wrestling with such questions since computers came into widespread use in the latter part of the 20th century. Our answer to them is found in this common introductory treatment of programming, which is analogous to commonly accepted introductory courses in mathematics, physics, biology, and chemistry. Computer Science strives to provide the basic preparation needed by all students in science and engineering, while sending the clear message that there is much more to understand about computer science than programming. Instructors teaching students who have studied from this book can expect that they will have the knowledge and experience necessary to enable those students to adapt to new computational environments and to effectively exploit computers in diverse applications.
     What can students who have completed a course based on this book expect to accomplish in later courses?
     Our message is that programming is not difficult to learn and that harnessing the power of the computer is rewarding. Students who master the material in this book are prepared to address computational challenges wherever they might appear later in their careers. They learn that modern programming environments, such as the one provided by Java, help open the door to any computational problem they might encounter later, and they gain the confidence to learn, evaluate, and use other computational tools. Students interested in computer science will be well prepared to pursue that interest; students in science and engineering will be ready to integrate computation into their studies.

Online lectures. A complete set of lecture slides and curated studio-produced videos that can be used in conjunction with this text are available online. As with traditional live lectures, the purpose of these videos is to inform and inspire, motivating students to study and learn from the text. Our experience is that student engagement with the material is significantly better than with live lectures because of the ability to play the lectures at a chosen speed and to replay and review the lectures at any time.

Booksite. An extensive amount of other information that supplements this text may be found on our Computer Science website. For economy, we refer to this site as the booksite throughout. It contains material for instructors, students, and casual readers of the book. We briefly describe this material here, though, as all web users know, it is best surveyed by browsing. With a few exceptions to support testing, the material is all publicly available.
     One of the most important implications of the booksite is that it empowers instructors and students to use their own computers to teach and learn the material. Anyone with a computer and a browser can begin learning to program by following a few instructions on the booksite. The process is no more difficult than downloading a media player or a movie. As with any website, our booksite is continually evolving. It is an essential resource for everyone who owns this book. In particular, the supplemental materials are critical to our goal of making computer science an integral component of the education of all scientists and engineers.
     For instructors, the booksite contains information about teaching. This information is primarily organized around a teaching style that we have developed over the past decade, where we offer two lectures per week to a large audience, supplemented by two class sessions per week where students meet in small groups with instructors or teaching assistants. The booksite has presentation slides for the lectures, which set the tone.
     For teaching assistants, the booksite contains detailed problem sets and programming projects, which are based on exercises from the book but contain much more detail. Each programming assignment is intended to teach a relevant concept in the context of an interesting application while presenting an inviting and engaging challenge to each student. The progression of assignments embodies our approach to teaching programming. The booksite fully specifies all the assignments and provides detailed, structured information to help students complete them in the allotted time, including descriptions of suggested approaches and outlines for what should be taught in class sessions.
     For students, the booksite contains quick access to much of the material in the book, including source code, plus extra material to encourage self-learning. Solutions are provided for many of the book’s exercises, including complete program code and test data. A wealth of information is associated with the programming assignments, including suggested approaches, checklists, FAQs, and test data.
     For casual readers, the booksite is a resource for accessing all manner of extra information associated with the book’s content. All of the booksite content provides web links and other routes to pursue more information about the topic under consideration. There is far more information accessible than any individual could fully digest, but our goal is to provide enough to whet any reader’s appetite for more information about the book’s content.

Acknowledgments. This project has been under development since 1992, and far too many people have contributed to its success for us to acknowledge them all here. Special thanks are due to Anne Rogers, for helping to start the ball rolling; to Dave Hanson, Andrew Appel, and Chris van Wyk, for their patience in explaining data abstraction; to Lisa Worthington and Donna Gabai, for being the first to truly relish the challenge of teaching this material to first-year students; and to Doug Clark for his patience as we learned about building Turing machines and circuits. We also gratefully acknowledge the efforts of /dev/126; the faculty, graduate students, and teaching staff who have dedicated themselves to teaching this material over the past 25 years here at Princeton University; and the thousands of undergraduates who have dedicated themselves to learning it.

Robert Sedgewick
Kevin Wayne
May 2016

An extensive amount of content associated with this book is available online, most of it freely available. The introduction to the COURSES page and the essay on online learning on this website tell the full story of the types of content, relationships, and how it may best be used by students and teachers of all sorts. The COURSES page for this book gives specific details. Here are some brief descriptions and quick links to this material.

Booksite. Our Computer Science website contains tens of thousands of files, fully coordinated with our textbook and also useful as a standalone resource. It consists of the following elements:

Excerpts. A condensed version of the text narrative, for reference while online.
Java code. Hundreds of easily downloadable Java programs and our I/O libraries for processing text, graphics, and sound.
Data. Real-world data sets for testing code (ours and yours).
Exercises. Selected exercises from the book and “web exercises” developed since its publication, along with solutions to selected exercises.
Programming assignments. Creative programming assignments that we have used at Princeton.

This is a living resource that is constantly being improved and updated.

Online lectures. A complete set of curated studio-produced lecture videos that can be used in conjunction with this text are available online via the cubits platform. This platform applies modern machine-learning models to build searchable transcripts, indexing, and other features that enhance the experience of learning from the videos.

Lecture slides. The lectures are based on hundreds of detailed, carefully prepared slides that are useful for reviewing the lecture content. These are available at the websites just listed, and on the COURSES page for this book, which provides a convenient interface for browsing through them.

MOOCs. The Coursera courses Computer Science: Programming with a Purpose and Computer Science: Algorithms, Theory, and Machines are massive open online courses based on the lecture videos that include exercises, auto-assessed programming assignments, and other features encouraging coordinated study of the material in the book.

Princeton course. You can find details on how we conduct our course at Princeton on our course website. Our students watch lectures online and are organized into small groups where they regularly complete laboratory assignments, meet with instructors, and participate in discussion groups and virtual office hours. They complete weekly programming assignments which are assessed with a modern online infrastructure. Other assessments include two programming exams and two online exams on lecture material (you can find many examples of old exam questions with answers here, an excellent source for self-assessment). We use codePost for grading and providing targeted feedback for programming assignments; Zoom for class, precept meetings, and office hours; Gradescope for online exams; cubits to curate and serve lectures; and Ed for student Q&A and peer discussion. We ensure loose synchronization via regular e-mail for authoritative communication from faculty to students.