Professor Stuart A. Kurtz
Ryerson 152 or 162B
<mailto:stuart@cs.uchicago.edu>
<http://www.cs.uchicago.edu/~stuart>
Office hours by appointment for now, should be regularly scheduled soon.
Text -- SICP
Grading -- 1/2 homework, 1/6 midterm, 1/3 final.
Don't be afraid to ask me questions. Be afraid *not* to ask me questions!
Start by reading Perlis's preface. When he writes "Pascal," feel free to read C, C++, Java, or any other traditional compiled procedural language. Read SICP 1.1
Scheme as a calculator with an unusual syntax. Compound expressions. Definitions of constants. Simple procedures: square, hypotenuse, substitution rule, applicative vs. normal order.
Conditional expressions. abs -- w/ cond, w/if.
Do exercises 1.1, 1.2, 1.3, 1.4, 1.5
Booleans: #t, #f, and, or, not. and and or are special forms, i.e., operations that have special evaluation rules. and and or take any number of arguments, and use short-circuit evaluation. Example:
(define (even? n)
(or (zero? n)
(odd? (- n 1))))
(define (odd? n)
(and (not (zero? n))
(even? (- n 1))))
A more traditional use: defining >= from >, =, <.
(define (>= a b) (or (> a b) (= a b)))
or
(define (>= a b) (not (< a b)))
Square Roots by Newton's method. Flat version. Discussion of names and scope. Nested version.
Exercises 1.6, 1.7, 1.8. You should do 1.7 and 1.8 on the computer, and hand in test runs.
Factorial -- Linear recursion, the "shape of the process." The iterative version of factorial.
Exercise 1.9, 1.10. Read SICP 1.2.
Tree recursion. Fibonacci. Iterative version. Count-change.
Please note adjustments to presentation guidelines!
Exercise 1.11, 1.12. Finish reading SICP 1.2.
Extra-credit 1.13.
Extra-credit (from the 1st edition of A&S): give an iterative solution to the count-change problem. N.B., this is a *hard* problem.