CS 61A: Structure and Interpretation of Computer Programs

The CS 61 series is an introduction to computer science, with particular emphasis on software and on machines from a programmer's point of view. This first course concentrates mostly on the idea of abstraction, allowing the programmer to think in terms appropriate to the problem rather than in low-level operations dictated by the computer hardware. The next course, CS 61B, will deal with the more advanced engineering aspects of software--on constructing and analyzing large programs and on techniques for handling computationally expensive programs. Finally, CS 61C concentrates on machines and how they carry out the programs you write.

In CS 61A, we are interested in teaching you about programming, not about any particular programming language. We consider a series of techniques for controlling program complexity, such as functional programming, data abstraction, object-oriented programming, and query systems. To get past generalities you must have programming practice in some particular language, and in this course we use Scheme, a dialect of Lisp. This language is particularly well-suited to the organizing ideas we want to teach. Our hope, however, is that once you have learned the essence of programming, you will find that picking up a new programming language is but a few days' work.

The prerequisite for this course is programming experience, in any language, including writing recursive procedures. (The CS Advanced Placement AB course will do, for example.) If you don't have that experience, consider starting with CS 3. If what you want is a course on how to use computer software, such as word processors and spreadsheets, you should take IDS 110 (InterDisciplinary Studies) instead.

The textbook for this course is Structure and Interpretation of Computer Programs (Second Edition) by Abelson, Sussman, and Sussman. It's the best computer science book ever written.

week  topic                             reading

1     functional programming            1.1
2     higher-order procedures           1.3
3     recursion and iteration           1.2.1-4
      ---Midterm 1---
4     data abstraction                  2.1, 2.2.1
5     hierarchical data                 2.2.2-3, 2.3.1,3
6     representing abstract data        2.4, 2.5.1-2
      ---Midterm 2---
7     object-oriented programming       handout
8     assignment, state, environments   3.1, 3.2
9     mutable data, queues, tables      3.3.1-3
10    concurrency                       3.4
11    streams                           3.5.1-3,5
      ---Midterm 3---
12    metacircular evaluator            4.1.1-6
13    analyzing, lazy evaluators        4.1.7, 4.2
14    nondeterministic evaluator        4.3
15    logic programming                 4.4.1-3