CS22

CS 22: Structure and Interpretation of Computer Programs

Spring 2002
Swarthmore College
Professor Charles Kelemen

Course Description

Welcome to Structure and Interpretation of Computer Programs. This course is a rigorous introduction to computer science, emphasizing the development of abstraction techniques for controlling the complexity of programs. This is an important skill applicable to almost all areas of engineering design. By studying programs that make repeated and deep use of abstraction, you will learn how to generate precise specifications from vaguely formulated and perhaps partially understood descriptions. This is a skill that is essential in writing computer programs and will be useful in all intellectual endeavors. Throughout the course, we will be using a dialect of the Lisp programming language, called Scheme. Scheme's great flexibility and power, combined with its very simple syntax, will allow us to concentrate on exploring interesting computer science concepts, without getting sidetracked by irrelevant and distracting details of syntax or other language idiosyncrasies. Topics to be covered include functional programming, recursion, data abstraction, higher-order procedures, lists and symbol processing, sets, object-oriented programming and local state, stream processing, and metalinguistic abstraction. The course culminates in the development of an interpreter, written in Scheme, for a substantial subset of the Scheme language itself.

This course is a Natural Science PDC.

Course Materials

We will be using DrScheme which is public domain software. DrScheme is available in a variety of formats including Mac, Windows, Linux, and Unix. Class periods will consist of a combination of lectures and hands-on interaction at the computer. I will assume that you have read the assignments before coming to class. But many of the in-class exercises will come directly from the text, so you should always bring disks and your textbook to class. The textbook we will be using is Structure and Interpretation of Computer Programs, 2nd Edition, by Abelson, Sussman, and Sussman.

Contact Info

Office Hours:

2 - 3 p.m. Monday
11 - 12 a.m. Wednesday

Office: Sproul Observatory Room 3
Office Phone and Voice Mail: (610) 328-8515
E-mail: cfk@cs.swarthmore.edu (or ckeleme1@swarthmore.edu)
If you need to see me but can't make it to my office hours, I'll be happy to schedule an appointment. Please contact me by e-mail or leave a message on my voice mail. You can also just drop by. Occasionally, I have pressing concerns that will not allow interruption, but I am usually happy to talk to students at unscheduled times. Feel free to ask.

Grading

50% Homework Assignments (several later assignments will be weighted more heavily than others)
20% Midterm Test (date, time, and location to be announced)
25% Final Exam (To be scheduled by registrar. May be as late as May 18)
5% Class Participation

Approximate Syllabus

Clab 1 (M, Jan. 21)
Clab 2 (W, Jan. 23)
Clab 3 (F, Jan. 25)
Clab 4 (M, Jan. 28)
Clab 5 (W, Jan. 30)
Clab 6 (F, Feb. 1 )
Clab 7 (M, Feb. 4)
Clab 8 (W, Feb. 6)
Clab 9 (F, Feb. 8)
Clab 10 (M, Feb. 11)
Clab 11 (W, Feb. 13)
Clab 12 (F, Feb. 15)
Clab 13 (M, Feb. 18)
Clab 14 (W, Feb. 20)
Clab 15 (F, Feb. 22)
Clab 16 (M, Feb. 25)
Clab 17 (W, Feb. 27)
Clab 18 (F, Mar. 1)
Clab 19 (M, Mar. 4)
Clab 20-Midterm test (W, Mar. 6)
Clab 21 (F, Mar. 8)
Clab 22 (M, Mar. 18)
Clab 23 (W, Mar. 20)
Clab 24 (F, Mar. 22)
Clab 25 (M, Mar. 25)
Clab 26 (W, Mar. 27)
Clab 27 (F, Mar. 29)
Clab 28 (M, Apr. 1)
Clab 29 (W, Apr. 3)
Clab 30 (F, Apr. 5)
Clab 31 (M, Apr. 8)
Clab 32 (W, Apr. 10)
Clab 33 (F, Apr. 12)
Clab 34 (M, Apr. 15)
Clab 35 (W, Apr. 17)
Clab 36 (F, Apr. 19)
Clab 37 (M, Apr. 22)
Clab 38 (W, Apr. 24)
Clab 39 (F, Apr. 26)
No Clab 40 today (M, Apr. 29) Work on HW 41.
Clab 41 (W, May 1)
Clab 42 (F, May 3)

Homework 1 (due W, Jan. 23)
Homework 2 (due F, Jan. 25)
Homework 3 (due M, Jan. 28 )
Homework 4 (due W, Jan. 30)
Homework 5 (due F, Feb. 1)
Homework 6 (due M, Feb. 4)
Homework 7 (due W, Feb. 6)
Homework 8 (due F, Feb. 8)
Homework 9 (due M, Feb. 11)
Homework 10 (due W, Feb. 13)
Homework 11 (due F, Feb. 15)
Homework 12 (due M, Feb. 18)
Homework 13 (due W, Feb. 20)
Homework 14 (due F, Feb. 22)
Homework 15 (due M, Feb. 25)
Homework 16 (due W, Feb. 27)
Homework 17 (due F, Mar. 1)
Homework 18 (due M, Mar. 4)
Homework 19 (due W, Mar. 6)
Homework 20 (due F, Mar. 8)
Homework 21 (due M, Mar. 18)
Homework 22 (due W, Mar. 20)
Homework 23 (due F, Mar. 22)
Homework 24 (due M, Mar. 25)
Homework 25 (due W, Mar. 27)
Homework 26 (due F, Mar. 29)
Homework 27 (due M, Apr. 1)
Homework 28 (due W, Apr. 3)
Homework 29 (due F, Apr. 5)
Homework 30 (due M, Apr. 8)
Homework 31 (due W, Apr. 10)
Homework 32 (due F, Apr. 12)
Homework 33 (due M, Apr. 15)
Homework 34 (due W, Apr. 17)
Homework 35 (due F, Apr. 19)
Homework 36 (due M, Apr. 22)
Homework 37 (due W, Apr. 24)
Homework 38 (due F, Apr. 26)
Homework 39 (due M, Apr. 29)
Homework 40 (due W, May 1)
Homework 41 (due F, May3)

Homework Policy

Written homework will generally be due by the beginning of class on Mondays. Late homework will be penalized (severity will depend on lateness and what we have done in class). Even if you miss a deadline, you are strongly encouraged to complete the assignment in a timely fashion, since this really is the only effective way to learn the material. Homework more than a week late will get at most half credit. But, half credit is much better than a zero.

You will turn in your homework assignments electronically (no hardcopy printout is necessary). In order to receive credit for an assignment, you must do the following:

In a single email message to cfk@cs.swarthmore.edu, insert text versions (do not use an attachment) of your solutions to each of the problems assigned. Begin the body of your email message with your name, CS22, and the assignment number.
Make the subject line of this email: CS22--HWx
where x is the number of the homework assignment.
For each exercise that asks you to write scheme code, include your Scheme definitions (not a transcript of your interactive session!) followed by a transcript of your interactive session in which you exercise and test your procedures.

Good Programming Style

In its purest form, programming is the art of expressing abstract ideas about computation in language that is as clear, unambiguous, and explicit as possible. To become an expert programmer, it is not enough simply to write programs that work correctly when run on a computer. Your programs must also be easy for other humans to read and understand. Indeed, good programming is as dependent on a deeply-developed sense of aesthetics as is good writing or other types of artistic activity. In short, style matters. Accordingly, programs will be graded with respect to both style and correctness. Good programming style typically includes the following:

a comment at the top of your file with your name, course, and the assignment number
concise comments summarizing each of the main procedures of your program in prose. These should clearly relate how the formal parameters are used and what the procedure returns.
good use of white space to separate sections of code and improve legibility
descriptive variable and procedure names
logically well-organized code
consistent indentation
avoidance of long, wrapped lines
avoidance of overcommenting

Academic Integrity

The utmost level of academic integrity is expected of every student. Under no circumstances may you hand in work done with (or by) someone else under your own name. If in doubt, credit the person(s) with whom you worked or from whom you got help. Discussing ideas and approaches to problems with others on a general level is fine (in fact, encouraged) but you must credit collaborators. Failure to abide by these rules constitutes academic dishonesty, and will be dealt with severely. Please do not put me or yourself in this unpleasant situation. Faculty are required to report academic dishonesty to the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."