Computer Science 151 is a general introduction to the fundamental ideas of computer science: algorithms, data structures, and abstraction. It includes computer programming (algorithm design, documentation, coding, testing, and debugging) in a high-level programming language, Scheme.
Office: Science 2418
Telephone: extension 3181
Office hours: Mondays, Wednesdays, Thursdays, and Fridays, 1:30 to 3:00
p.m; Wednesdays, 9 to 10 a.m.; and by appointment.
Springer, George, and Friedman, Daniel P. Scheme and the art of programming. Cambridge, Massachusetts: The MIT Press, 1994.
Kelsey, Richard, Clinger, William, and Rees, Jonathan, eds. Revised5 report on the algorithmic language Scheme. February 20, 1998.
Chez Scheme version 5 system manual. Bloomington, Indiana: Cadence Research Systems, 1994.
Here is what each student in the course is expected to do:
Prepare for, attend, complete, and reflect on the labs. Almost every class session will include hands-on interaction with the computer, and more specifically with the Scheme interactive interface. This direct experience is an important part of the course -- but it's just as important to understand what you're doing as to do it. This means that you should read over each lab before the class session and write a summary or report about it afterwards. You'll need a notebook for these reports, for logs of errors encountered and corrected during the development of solutions to programming exercises, and for questions raised by your reading and reflection.
Read the assigned chapters in the textbooks and the handouts carefully, understand the ideas and methods that are presented in them, and submit solutions to assigned exercises requiring their application.
You may submit solutions to exercises in hard copy or by electronic mail (to stone@math.grin.edu). Each solution should be submitted as a ``log file'' -- a document that includes both the text of a Scheme program and one or more test runs of the program, showing the output that it generates.
I have arranged the exercises in a sequence. Your final grade will be determined by how far you get in this sequence -- that is, by the number of complete and correct solutions you submit, with the additional provision that you are eligible to receive credit for exercise n + 1 only if you have submitted a complete and and correct solution for exercise n.
You may turn in as many incomplete or tentative solutions as you like; I shall make comments and suggestions on them, but award credit only for solutions that are complete, correct, and in sequence.
The deadline for all exercises is noon on Friday, May 15. I'll try to read and comment on any solutions that I receive after this deadline, but they will not be eligible for credit. Note that under these rules it would be extremely imprudent to wait until the last week of the semester and then submit a large bundle of solutions.
There is no preconceived ``grading curve'' for this course. Students do not compete with one another for a fixed quota of As, for example; instead, I shall award the grade of A to any student who completes the number of exercises that, in my (subjective) judgement, constitutes excellent work in the course, as specified on page 5 of the 1997-1998 Student Handbook. Similarly, I'll give Bs for good work, Cs for satisfactory work, and Ds for passing work.
Since you will receive credit on the basis of your individual performance on the exercises, it would be unethical to submit any work that is not your own or to collaborate on solutions, arrogating the results of other people's intellectual effort. If I encounter any indications of plagiarism, the Committee on Academic Standing will deal with them.
However, the rule against collaboration does not apply (in this course) to labs, which you may do in pairs if you prefer, or to group study and discussion, except in connection with the exercises.
The class is scheduled to meet at 9 a.m. on Mondays, Tuesdays, Thursdays, and Fridays, from January 19 through March 13 and from March 30 through May 8.
Reading: Springer and Friedman, sections 1.1 and 1.2.
January 19. Getting started. Logging in and out of MathLAN workstations. Starting and shutting down the dtterm terminal emulator. Changing one's password. Starting and shutting down the Chez Scheme expression evaluator. Starting and shutting down the Netscape browser. Finding and bookmarking the front-door page for the course.
Reading: Springer and Friedman, section 1.3.
January 20. Beginning Scheme.
Procedure calls. The +, -, *,
/, expt, and abs procedures.
Arithmetic expressions. Definitions.
January 22. Editing Scheme
files. Starting and shutting down the XEmacs text editor. Opening
and saving files in XEmacs. Simple editing operations. The
load procedure.
January 23. Scheme within
XEmacs. Symbols as values. Quote-expressions.
Documentation and strings. Saving .ss files. String literals.
Loading a .ss file from the command line.
Reading: Springer and Friedman, sections 1.4 and 1.5.
January 26. Lists, Booleans, and
predicates. The cons, car, and
cdr procedures. List literals. The empty list. The
list, length, reverse,
append, and list-ref procedures. Type predicates:
number?, symbol?, list?,
null?, and boolean?. Equivalence predicates:
eq?, eqv?, and equal?. Arithmetic
predicates: =, <, >,
<=, >=, even?,
odd?, zero?, positive?, and
negative?. The not procedure.
Reading: Springer and Friedman, sections 2.1 and 2.2.
January 27. Procedure
definitions. Lambda-expressions. Procedural abstraction.
Reading: Kelsey, Clinger, and Rees, section 6.2.
January 29. Numbers. The ``tower of subtypes.'' Built-in arithmetic procedures.
Reading: Springer and Friedman, section 2.3.
January 30. Conditional
evaluation. Cond-expressions.
If-expressions. And-expressions.
Or-expressions.
Reading: Springer and Friedman, section 2.4.
February 2. Recursion: the basics.
Reading: Springer and Friedman, sections 3.1 and 3.2.
February 3. Variations
on recursion. The memq, memv, and
member procedures.
Reading: Chez Scheme system manual, section 7-4.
February 5. Random-number
generation. The random and random-seed
procedures in Chez Scheme.
February 6. Detecting errors.
Testing preconditions. The error procedure.
February 9. Patterns. A pause for breath.
February 10. Project: The martingale.
Reading: Springer and Friedman, section 2.5.
February 12. Side effects and
sequencing. Output during expression evaluation. The
display and newline procedures.
Begin-expressions. Tracing by means of output side-effects.
Reading: Springer and Friedman, sections 4.1 and 4.2.
February 13. Flat recursion.
Reading: Springer and Friedman, section 4.3.
February 16. Deep recursion.
Reading: Springer and Friedman, section 4.4.
February 17. Pairs and pair structures.
The pair? predicate. Pair structures. Box-and-pointer
diagrams. The assq, assv, and assoc
procedures.
February 19. Trees. Structural recursion.
Reading: Springer and Friedman, sections 5.1 and 5.2.
February 20. Local bindings.
Let-expressions. Let*-expressions.
February 23. Indefinite recursion. A pause for breath.
February 24. Project: Mixing organic fertilizers.
Reading: Kelsey, Clinger, and Rees, section 4.2.2.
February 26. Local binding and
recursion. Letrec-expressions.
Reading: Springer and Friedman, section 4.5.
February 27. Tail-call
elimination. Named let-expressions.
Reading: Kelsey, Clinger, and Rees, section 6.3.4.
March 2. Characters. Character
literals. The char? predicate. Ordering predicates for
characters. The char-alphabetic?, char-numeric?,
char-whitespace?, char-upper-case?, and
char-lower-case? predicates. The char-upcase and
char-downcase procedures.
Reading: Springer and Friedman, sections 6.1 and 6.2.
March 3. Strings. String
literals. Zero-based indexing. The string? predicate. The
string and make-string procedures. The
string-length, string-ref,
substring, and string-append procedures.
Ordering predicates for strings.
Reading: Springer and Friedman, sections 6.3 and 6.4.
March 5. Input and output under
program control. Interactive Scheme programs. The
read and write procedures. Using symbols as
sentinels.
Reading: Chez Scheme system manual, sections 3-2 and 3-3.
March 6. Debugging in Chez Scheme. The Chez Scheme interactive inspector.
March 9 and 10. Project: Solving permuted-word puzzles.
Reading: Kelsey, Clinger, and Rees, section 6.6.
March 12. Files. The
open-input-file, open-output-file,
close-input-port, and close-output-port
procedures. Using ports in calls to display,
newline, write, and read. The
read-char, peek-char, and write-char
procedures. The eof-object? predicate. The
current-input-port and current-output-port
procedures.
March 13. Files (continued). The
call-with-input-file and call-with-output-file
procedures.
Reading: Springer and Friedman, sections 7.1 and 7.2.
March 30. Procedures as
values. The procedure? predicate. The
map, for-each, and apply
procedures.
March 31. Procedures as values (continued).
Reading: Kelsey, Clinger, and Rees, section 4.1.4.
April 2. Variable arity.
Alternative forms of the lambda-expression.
Reading: Springer and Friedman, sections 7.3 through 7.5.
April 3. Higher-order procedures. Operator sections. Currying. Procedure composition.
April 6 and 7. Project: Differences between files.
Reading: Springer and Friedman, sections 9.1, 9.2, and 9.3.
April 9. Vectors: the basics. Vector
literals. The vector? predicate. The vector and
make-vector procedures. The vector-length and
vector-ref procedures. The vector-set!
procedure.
Reading: Springer and Friedman, section 9.4.
April 10. Structure
mutation. Applications of the vector-set! procedure.
The string-set!, set-car!, and
set-cdr! procedures.
Reading: Springer and Friedman, sections 11.1 and 11.2.
April 13. Assignment.
Set!-expressions. Global and local variables. Assignments to
parameters.
Reading: Kelsey, Clinger, and Rees, section 4.2.4.
April 14. Iteration.
Do-expressions.
Reading: Kelsey, Clinger, and Rees, sections 6.3.3 and 6.2.6.
April 16. Conversions. The
char->integer and integer->char procedures. The
string->number and number->string procedures.
The string->symbol and symbol->string
conversions.
April 17. Scheme libraries. SLIB.
Reading: Springer and Friedman, sections 10.1 and 10.2.1.
April 20. Sorting methods. The insertion sort.
Reading: Springer and Friedman, section 10.2.2.
April 21. The merge sort.
April 23 and 24. Project: Cellular automata.
Reading: Springer and Friedman, section 10.3.
April 27. Searching methods. Linear and binary search.
April 28. Records. Type predicates. Constructor procedures. Selector procedures. Mutator procedures.
April 30. Metaprogramming.
Reading: Springer and Friedman, sections 12.1 and 12.2.
May 1. Object-oriented programming. Messages. Simple objects.
Reading: Springer and Friedman, section 12.3.
May 4. Stacks and queues. Abstract data types.
May 5 and 7. Project: Constructing World Wide Web documents.
May 8. Summary and review.
Revised5 Report on the Algorithmic Language Scheme
Scheme Repository (Indiana University)
Frequently asked questions about Scheme
Colleges, universities, and secondary schools that use (or are experimenting with) Scheme
Scheme summer workshop at Indiana University (Educational Infrastructure project)
This document is available on the World Wide Web as
http://www.math.grin.edu/courses/Scheme/spring-1998/
created October 24, 1996
last revised June 21, 1998