1. section 1.1 - starting scheme
due Thu Sep 9
- Install either racket or guile with the links in the resources page and as described in class.
- Get a copy of the SICP textbook.
- Read section 1.1.
- Do exercises 1.1 through 1.4 (scheme basics practice).
- If you still have time (4 credits = 12 hrs/week total), do 1.5 & 1.6 (evaluation subtleties).
- And if you still have time, do 1.7 & 1.8. (recursion and conditional practice using Newton's method)
- Describe what you did and how this is going.
2. section 1.2 - recursion
due Thu Sep 16
- Read section 1.2.
- Explain in your own words the difference between what the authors call an "iterative process" and a "recursive process". (Note that both can be coded with a procedure that refers to itself.) Use ,trace on factorial and fact-iter from the text to illustrate the difference.
- Do exercise 1.9. Include a "by hand" application of the "substitution model", and using ,trace to see the execution.
- Do exercise 1.11. Again use ,trace to illustrate the difference between the "iterative process" and "recursive process".
- Do exercise 1.15. (This is a "divide-and-conquer" algorithm, which is a hint for the O() behavior.)
- If you still have time and/or the inclination ...
- exercise 12 asks you to calculate the (n m) element of Pascal's Triangle.
- exercise 16, 17, 18 work through a very cool "logarithmic time multiplication" idea.
- exercises 1.21 - 1.28 look at classic algorithms for testing prime numbers, used in cryptology.
3. lambda, let, cons, car, cdr
due Thu Sep 23
- Read enough of 2.1 and 1.3 (or google to find other explanations) to understand
let. (Yes, the names are terrible. We can find aliases for some ...)
- Explain the relation between
list in scheme. Give an example, with some pictures.
- Explain what
let does, and how it can be implemented with
- What is this trying to do, and why does it fail :
(let ((a 1) (b (+ 1 a))) (+ a b)) ?
- Do exercise 2.2 : a line segment API
- Do exercise 2.17 : find the last pair of a list
- Do exercise 1.34 : subsitution rule ; functions as arguments
- Do exercise 1.35 : the golden ratio as a fixed point
- 2.5 : encoding two numbers into one integer
- 2.6 : encoding numbers with only functions (i.e. Church encoding ... very cool)