ECEP VIRTUAL CAMPUS

UCB-CS61A: The Structure and Interpretation of Computer Programs, Fall 2013

The Structure and Interpretation of Computer Programs - Introduction to programming and computer science. This course exposes students to techniques of abstraction at several levels: (a) within a programming language, using higher-order functions, manifest types, data-directed programming, and message-passing; (b) between programming languages, using functional and rule-based languages as examples. It also relates these techniques to the practical problems of implementation of languages and algorithms on a von Neumann machine. There are several significant programming projects, programmed in a dialect of the LISP language.

Course Description

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, such as constructing and analyzing large 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 how to use one particular programming language. We consider a series of techniques for controlling program complexity, such as functional programming, data abstraction, and object-oriented programming. Mastery of a particular programming language is a very useful side effect of studying these general techniques. However, our hope 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.

There is also a self-paced version of this course, 61AS, which fulfills the same requirements.

Programming Language

61A uses the Python 3 programming language. Python is a popular language in both industry and academia. It is also particularly well-suited to the task of exploring the topics taught in this course. It is an open-source language developed by a large volunteer community that prides itself on the diversity of its contributors.

In previous semesters, this course was taught using the Scheme language, a dialect of Lisp, which is the oldest programming language that is still recruiting new users today. Lisp and Python are similar in many ways. In fact, Lisp popularized many of the features that make Python a great language. Our choice to change languages is primarily motivated by the strength of Python's programming community, which you will soon join as you learn the language. Python also has excellent library support for a vast range of application areas. Knowing Python will help you pursue your future programming interests, wherever they may lead you.

Prerequisites

Math 1A is a corequisite for 61A. (That is, it may be taken concurrently.)

There is no formal programming-related prerequisites for admission to 61A. However, most 61A students have had significant prior programming experience. There is no need for you to be familiar with any particular programming language. If you have taken the CS Advanced Placement AB course in C++ or Java, you are certainly ready for 61A.

If you don't feel ready for 61A, we recommend that you take CS 10 : The Beauty and Joy of Computing, which is an introduction to computer science for non-majors (and majors needing more programming experience). The course will teach students how to program using BYOB (based on Scratch), one of the friendliest programming languages ever invented. It's purely graphical, which means programming involves simply dragging blocks around, and building bigger blocks out of smaller blocks. But the course is far more than just learning to program! You'll learn some of the "Big Ideas" of computing, such as abstraction, design, recursion, concurrency, simulations, and the limits of computation. You'll also see some beautiful applications of computing that have changed the world, as well as talk about the history of computing and where it will go in the future.

Non-technical students (for instance, ones who prefer Math 16A to Math 1A) should probably avoid CS 61A entirely, and should take CS 10 to satisfy their need for or interest in a programming course.

If you are not strongly interested in computer programming at all, but instead want to learn how to use computers as a tool, you should consider IDS 110, a course that presents a variety of personal computer software along with a brief introduction to programming.

If you have substantial prior programming background, you may feel that you can skip 61A. In most cases we don't recommend that. Although 61A is the first course in the CS sequence, it's quite different from most introductory courses. You won't be bored in 61A. Perhaps your prior experience will allow you to skip 61B or 61C, which are more comparable to courses taught elsewhere.

Course Materials

There is no required textbook for this course. Our primary text will be a series of lecture notes based on the classic book, Structure and Interpretation of Computer Programs, which has been the textbook for 61A for many years. Lecture notes will be posted to the course website.

Course Syllabus

Lecture 1 Welcome
Lecture 2 Names
Lecture 3 Control
Lecture 4 Higher-Order Functions
Lecture 5 Environments
Lecture 6 Newton's Method
Lecture 7 Recursion
Lecture 8 Tree Recursion
Lecture 9 Function Examples
Lecture 10 Data Abstraction
Lecture 11 Sequences
Lecture 12 Lists and Dictionaries
Lecture 13 Strings and Sequence Processing
Lecture 14 Mutable Data
Lecture 15 Objects
Lecture 16 Inheritance
Lecture 17 Recursive Objects
Lecture 18 Orders of growth
Lecture 19 Sets
Lecture 20 Multiple Representations
Lecture 21 Generic Functions
Lecture 22 Data Examples
Lecture 23 Functional Programming
Lecture 24 Exceptions
Lecture 25 Calculator
Lecture 26 Interpreters
Lecture 27 Tail Calls
Lecture 28 User Interfaces
Lecture 29 Iterators
Lecture 30 Streams
Lecture 31 Declarative Programming
Lecture 32 Unification
Lecture 33 Distributed Computing
Lecture 34 MapReduce 
Lecture 35 Natural Language Processing
Starts August 18, 2015

Course at a Glance

10 weeks of study 2-4 hours/week English English & Vietnamese subtitles