CS For All

This book aims to provide an introduction to computer science as an intellectually rich and vibrant field rather than focusing exclusively on computer programming. While programming is an important and pervasive element of the approach, this book emphasizes concepts and problem-solving over syntax and programming language features.

This book is a companion to the course “CS for All” developed at Harvey Mudd College and subsequently adopted at a variety of colleges and universities. At Mudd, this course is taken by almost every first-year student—irrespective of the student’s ultimate major—as part of the college’s core curriculum. The offering is also taken by many students at the Claremont Colleges, including students majoring in the humanities, social sciences, and the arts. Thus, it serves as a first computing course for students regardless of their major.

This book is intended to be used with the substantial resources that we have developed for the course, which are available on the Web at www.cs.hmc.edu/csforall. These resources include complete lecture slides, a rich collection of weekly assignments, some accompanying software, documentation, and papers that have been published about the course.

The authors have deliberately kept this book relatively short and have endeavored to make it fun and readable. The content of this book is an accurate reflection of the content of the course rather than an intimidating encyclopedic tome that can’t possibly be covered in a single semester. The book has been written in the belief that a student can read all of it comfortably as the course proceeds.

TABLE OF CONTENTS

Chapter 1: Introduction

1.1    What Is Computer Science?
1.1.1 Data
1.1.2 Algorithms
1.1.3 Programming
1.1.4 Abstraction
1.1.5 Problem-Solving and Creativity
1.2    Picobot
1.2.1 The Roomba Problem
1.2.2 The Environment
1.2.3 State0
1.2.4  Think Locally, Act Globally
1.2.5 Whatever
1.2.6 Algorithms and Rules
1.2.7 The Picobot Challenge
1.2.8 A-Maze Your Friends!
1.2.9 Uncomputable Environments
Key Terms
Exercises

Chapter 2: Functional Programming

2.1    Humans, Chimpanzees, and Spell Checkers
2.2     Getting Started in Python
2.2.1 Naming Things
2.2.2 What’s in a Name?
2.3    More Data: from Numbers to Strings
2.3.1 A Short Note on Length
2.3.2 Indexing
2.3.3 Slicing
2.3.4 String Arithmetic
2.4     Lists
2.4.1 Some Good News!
2.5     Functioning in Python
2.5.1 A Short Comment on Docstrings
2.5.2 An Equally Short Comment on Comments
2.5.3 Functions Can Have More Than One Line
2.5.4 Functions Can Have Multiple Arguments
2.5.5 Why Write Functions?
2.6    Making Decisions
2.6.1 A Second Example Function
2.6.2 Indentation
2.6.3 Multiple Conditions
2.7     Recursion
2.7.1 A First Recursive Example: Factorial!
2.7.2 Returning to the Edit Distance Function
2.8     Recursion, Revealed
2.8.1 Functions that Call Functions
2.9     Let’s Recurse!
2.9.1 Recursive Design
2.9.2 Base Case(s)
2.9.3 Designing with Recursion
2.9.4 Recursive Patterns
2.9.5 Visualization Tools
2.10    Use It or Lose It
2.11    Edit Distance!
2.11.1 Base Cases for distance
2.11.2 Recursive Cases for distance
2.12    Conclusion
Key Terms
Exercises

Chapter 3: Functional Programming, Part Deux

3.1    Cryptography and Prime Numbers
3.2     First-Class Functions
3.3     Generating Primes
3.4     Filtering
3.5     Lambda
3.6     Putting Google on the Map!
3.6.1 Map
3.6.2 Reduce
3.6.3 Composition and mapReduce
3.7     Functions as Results
3.7.1 Python Does Calculus!
3.7.2 Higher Derivatives
3.8     RSA Cryptography Revisited
3.9    Conclusion
Key Terms
Exercises

Chapter 4: Computer Organization

4.1    Introduction to Computer Organization
4.2    Representing Information
4.2.1 Integers
4.2.2 Arithmetic
4.2.3 Negative Thinking
4.2.4 Fractions: Piecing It Together
4.2.5 Letters and Strings
4.2.6 Structured Information
4.3    Logic Circuitry
4.3.1 Boolean Algebra
4.3.2 Making Other Boolean Functions
4.3.3 Logic Using Electrical Circuits
4.3.4 Computing With Logic
4.3.5 Memory
4.4    Building a Complete Computer
4.4.1 The von Neumann Architecture
4.5    Hmmm
4.5.1 A Simple Hmmm Program
4.5.2 Trying It Out
4.5.3 Looping
4.5.4 Functions
4.5.5 Recursion Using Stacks
4.5.6 Saving Precious Possessions
4.5.7 The Complete Hmmm Instruction Set
4.5.8 A Few Last Words
4.6     Conclusion
Key Terms
Exercises

Chapter 5: Imperative Programming

5.1    A Computer That Knows You (Better Than You Know Yourself?)
5.1.1 Our Goal: A Music Recommender System
5.2     Getting Input from the User
5.2.1 Type Conversion
5.3     Repeated Tasks—Loops
5.3.1 Recursion vs. Iteration at the Low Level
5.3.2 Definite Iteration: for Loops
5.3.3 How Is the Loop Control Variable Used?
5.3.4 Accumulating Answers
5.3.5 Handling Unexpected Input
5.3.6 Indefinite Iteration: while Loops
5.3.7 for Loops vs. while Loops
5.3.8 Creating Infinite Loops on Purpose
5.3.9 Iteration Is Efficient
5.4     References and Mutable vs. Immutable Data
5.4.1 Assignment by Reference
5.4.2 Mutable Data Types Can Be Changed Using Other Names!
5.5     Mutable Data + Iteration: Sorting Out Artists
5.5.1 Why Sort? Running Time Matters
5.5.2 A Simple Sorting Algorithm: selectionSort
5.5.3 Why selectionSort Works
5.5.4 A swap of a Different Sort
5.5.5 2D Arrays and Nested Loops
5.5.6 Dictionaries
5.6    Reading and Writing Files
5.7    Putting It All Together: Program Design
5.8     Conclusion
Key Terms
Exercises

Chapter 6: Fun and Games with OOPs: Object-Oriented Programs

6.1    Introduction
6.2    Thinking Objectively
6.3     The Rational Solution
6.4     Overloading
6.5     Printing an Object
6.6    A Few More Words on the Subject of Objects
6.7     Getting Graphical with OOPs
6.8     Robot versus Zombies, Finally!
6.9     Conclusion
Key Terms
Exercises

Chapter 7: How Hard is the Problem

7.1    The Never-ending Program
7.2     Three Kinds of Problems: Easy, Hard, and Impossible
7.2.1 Easy Problems
7.2.2 Hard Problems
7.2.3 Impossible Problems
7.3     The Halting Problem—An Uncomputable Problem
7.4     Conclusion
Key Terms
Exercises